patternMajor
Human computing power: Can humans decide the halting problem on Turing Machines?
Viewed 0 times
problemhumancanthehaltingpowerhumansdecidemachinesturing
Problem
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 or general purpose computers?
Note: Obviously, in the strictest sense, you can always say no, because there are Turing Machines so large they couldn't even be read in the life span of a single human. But this is a nonsensical restriction that doesn't contribute to the actual question. So to make things even, we'd have to assume humans with an arbitrary life span.
So we could ask: Given a Turing Machine T represented in any suitable fashion, an arbitrarily long-lived human H and an arbitrary amount of buffer (i.e. paper + pens), can H decide whether T halts on the empty word?
Corollary: If the answer is yes, wouldn't this also settle if any computer has a chance of passing the turing-test?
Note: Obviously, in the strictest sense, you can always say no, because there are Turing Machines so large they couldn't even be read in the life span of a single human. But this is a nonsensical restriction that doesn't contribute to the actual question. So to make things even, we'd have to assume humans with an arbitrary life span.
So we could ask: Given a Turing Machine T represented in any suitable fashion, an arbitrarily long-lived human H and an arbitrary amount of buffer (i.e. paper + pens), can H decide whether T halts on the empty word?
Corollary: If the answer is yes, wouldn't this also settle if any computer has a chance of passing the turing-test?
Solution
It is very hard to define a human mind with a such mathematical rigor as it is possible to define a Turing machine. We still do not have a working model of a mouse brain however we have the hardware capable of simulating it. A mouse has around 4 million neurons in the cerebral cortex. A human being has 80-120 billion neurons (19-23 billion neocortical). Thus, you can imagine how much more research will need to be conducted in order to get a working model of a human mind.
You could argue that we only need to do top-down approach and do not need to understand individual workings of every neuron. In that case you might study some non-monotonic logic, abductive reasoning, decision theory, etc. When the new theories come, more exceptions and paradoxes occur. And it seems we are nowhere close to a working model of a human mind.
After taking propositional and then predicate calculus I asked my logic professor:
"Is there any logic that can define the whole set of human language?"
He said:
"How would you define the following?
To see a World in a grain of sand
And a Heaven in a wild flower,
Hold Infinity in the palm of your hand
And Eternity in an hour.
If you can do it, you will become famous."
There have been debates that a human mind might be equivalent to a Turing machine. However, a more interesting result would be for a human mind not to be Turing-equivalent, that it would give a rise to a definition of an algorithm that is not possibly computable by a Turing machine. Then the Church's thesis would not hold and there could possibly be a general algorithm that could solve a halting problem.
Until we understand more, you might find some insights in a branch of philosophy. However, no answer to your question is generally accepted.
http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Minds_and_machines
http://en.wikipedia.org/wiki/Mechanism_(philosophy)#G.C3.B6delian_arguments
You could argue that we only need to do top-down approach and do not need to understand individual workings of every neuron. In that case you might study some non-monotonic logic, abductive reasoning, decision theory, etc. When the new theories come, more exceptions and paradoxes occur. And it seems we are nowhere close to a working model of a human mind.
After taking propositional and then predicate calculus I asked my logic professor:
"Is there any logic that can define the whole set of human language?"
He said:
"How would you define the following?
To see a World in a grain of sand
And a Heaven in a wild flower,
Hold Infinity in the palm of your hand
And Eternity in an hour.
If you can do it, you will become famous."
There have been debates that a human mind might be equivalent to a Turing machine. However, a more interesting result would be for a human mind not to be Turing-equivalent, that it would give a rise to a definition of an algorithm that is not possibly computable by a Turing machine. Then the Church's thesis would not hold and there could possibly be a general algorithm that could solve a halting problem.
Until we understand more, you might find some insights in a branch of philosophy. However, no answer to your question is generally accepted.
http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Minds_and_machines
http://en.wikipedia.org/wiki/Mechanism_(philosophy)#G.C3.B6delian_arguments
Context
StackExchange Computer Science Q#3271, answer score: 32
Revisions (0)
No revisions yet.