Linked Questions

43
votes
2answers
14k views

How to show that a function is not computable?

I know that there exist a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
0
votes
0answers
110 views

Halting problem and simulation of intelligence [duplicate]

According to halting problem, there is no algorithm which can decide if another algorithm and its input will halt or not. Suppose human intelligence can be simulated in a computer. Also suppose than ...
148
votes
12answers
49k views

Why, really, is the Halting Problem so important?

I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia [article][1] correctly explains that a deterministic ...
59
votes
10answers
10k views

Human computing power: Can humans decide the halting problem on Turing Machines?

We know the halting problem (on Turing Machines) is undecidable for Turing Machines. Is there some research into how well the human mind can deal with this problem, possibly aided by Turing Machines ...
22
votes
6answers
3k views

Algorithm to solve Turing's “Halting problem‍​”

"Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist" Can I find a general algorithm to solve the halting problem for ...
18
votes
5answers
890 views

Is it possible to solve the halting problem if you have a constrained or a predictable input?

The halting problem cannot be solved in the general case. It is possible to come up with defined rules that restrict allowed inputs and can the halting problem be solved for that special case? For ...
0
votes
4answers
254 views

Is effective solvability a coherent and/or useful concept? [closed]

I am aware of Turing's proof of the undecidability of the halting problem (and I think I understand it). What I'm asking is quite different. I shall define what I mean by "effectively solvable": ...
11
votes
1answer
622 views

Program synthesis, decidability and the halting problem

I was reading an answer to a recent question, and sort of a strange, ephemeral thought came to mind. My asking this might betray either that my theory chops are seriously lacking (mostly true) or that ...
6
votes
1answer
570 views

Machine Learning to predict the Halting Problem

I seem to recall an academic paper from some years ago which used machine learning (possibly genetic or evolutionary programming) to predict whether a Turing Machine would halt. By predict, I mean ...
4
votes
1answer
457 views

If the Halting Problem was solvable, and we solved it, what would be its implications?

Perhaps a way to better understand the Halting Problem's importance is to know what would happen or what could be possible if this was solved. What would be the Halting Problem's implications in ...
4
votes
1answer
1k views

Does the Halting Problem prove that true Artificial Intelligence is impossible?

The Halting Problem demonstrates that there are things that a machine can never be programmed to do. Is this proof that true Artificial Intelligence - that is, the ability for a machine to think and ...
5
votes
1answer
309 views

Possible to construct a probabilistic halting problem solver?

I'm a CS undergrad so my math/CS knowledge is not that deep so please correct me if my premise is flawed or I have made some incorrect assumptions. So I was thinking, much in the way that some ...
0
votes
1answer
347 views

Using AI / Machine learning to find the most time and space efficient solutions to an algorithm [duplicate]

As programmers, we are always trying to find the most efficient space and time complexity solutions to algorithms. Is it forseeable in the future that we have languages or techniques such as AI/...