Linked Questions

30
votes
7answers
7k views

What are the simplest examples of programs that we do not know whether they terminate?

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. ...
25
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 ...
32
votes
2answers
5k views

What are very short programs with unknown halting status?

This 579-bit program in the Binary Lambda Calculus has unknown halting status: ...
1
vote
2answers
153 views

If we spoke in TM-computable English, what would it look like?

We know that any "effectively computable" process is computable by a Turing machine (Turing-Church thesis). Although it seems that "effectively computable" is still open to discussion, the intuitive ...
8
votes
1answer
4k views

Why can't we solve the Halting Problem by using Artificial Intelligence? [duplicate]

Yesterday I was reading about Computability and they mention the Halting Problem. It got stuck in mind all day until I remember that some weeks ago, when learning Java, the IDE (Netbeans) show me a ...
3
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 ...
0
votes
1answer
2k views

What is Turing's main argument in “Computing Machinery and Intelligence”?

I read Alan Turing's paper "Computing Machinery and Intelligence" a few times and it isn't clear what exactly is he arguing for. He proposes the imitation game, but doesn't form a concrete conclusion. ...
0
votes
0answers
129 views

How to accomodate decision trees with infinite options

I know that once I have a graph or decision tree representation of a problem, there are many different ways I can get a computer to solve the problem. They're called search algorithms, and go by names ...
0
votes
0answers
140 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 ...