Linked Questions

0
votes
0answers
117 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 ...
0
votes
0answers
12 views

undecidable problems solvable for humans? [duplicate]

are undecidable problems also unsolvable for humans? I mean I would think I could tell by reading the code of a program if it will halt for a certain input (which would solve the haltingproblem). ...
28
votes
7answers
6k 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. ...
23
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
4k views

What are very short programs with unknown halting status?

This 579-bit program in the Binary Lambda Calculus has unknown halting status: ...
7
votes
1answer
3k 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 ...
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. ...
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 ...
1
vote
2answers
147 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 ...
0
votes
0answers
53 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 ...