Linked Questions
9 questions linked to/from Human computing power: Can humans decide the halting problem on Turing Machines?
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 ...
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:
...
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 ...
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.
...
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 ...
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 ...
0
votes
0answers
123 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 ...