principleMinor
How is the computational power of a human brain comparing to a turing machine?
Viewed 0 times
humanthecomparingcomputationalpowerbrainhowturingmachine
Problem
This seems related to these questions at a glance:
What are some problems which are easily solved by human brain but which would take more time computers?
What would show a human mind is/is not reducible to a Turing machine?
But not quite, I am not asking about "time", but power. Also, I am not interested in the turing test. That said, my question can also be expressed as two parts:
And vice versa. The "language" I am talking about is the "mathematical" language, not only a "human" or "programming" language:
$$L \subseteq \Sigma^*$$
Since this is a question about computational power, I would make the following assumptions:
(here I mean mistakes like copying the wrong character or computing arithmetics incorrectly, typical human errors)
Please give an example if you have an answer. Remember, this is a theoretical question, so practical issues are not in concern.
EDIT 1
OK, as someone pointed out, I will add the following assumptions.
Human is probably not easy to define in precise mathematical words, so let's just assume "you".
About a human recognizing a string in a language, I am talking about performing the same task the turing machine is "programmed" to do. Say, given a string, whether you (a human) can recognize it when it conforms to a set of rules, or decide whether it conforms to a set of rules or not. I am not sure if I can make the point clear enough...
EDIT 2
OK, to clarify, this is a question about model of computation, so yes, like André Souza Lemos mensioned, I am talki
What are some problems which are easily solved by human brain but which would take more time computers?
What would show a human mind is/is not reducible to a Turing machine?
But not quite, I am not asking about "time", but power. Also, I am not interested in the turing test. That said, my question can also be expressed as two parts:
- Is there a language, which cannot be recognized by any turing machine, that can be recognized by a human?
- Is there a language, which cannot be decided by any turing machine, that can be decided by a human?
And vice versa. The "language" I am talking about is the "mathematical" language, not only a "human" or "programming" language:
$$L \subseteq \Sigma^*$$
Since this is a question about computational power, I would make the following assumptions:
- Human do not make mistakes
(here I mean mistakes like copying the wrong character or computing arithmetics incorrectly, typical human errors)
- There is no space limit (turing machine gets infinite tape, you get infinite medium to write)
- There are no time constraints
- However, the recognition/decision must be achieved within finite time.
- And of course, in finite space
Please give an example if you have an answer. Remember, this is a theoretical question, so practical issues are not in concern.
EDIT 1
OK, as someone pointed out, I will add the following assumptions.
Human is probably not easy to define in precise mathematical words, so let's just assume "you".
About a human recognizing a string in a language, I am talking about performing the same task the turing machine is "programmed" to do. Say, given a string, whether you (a human) can recognize it when it conforms to a set of rules, or decide whether it conforms to a set of rules or not. I am not sure if I can make the point clear enough...
EDIT 2
OK, to clarify, this is a question about model of computation, so yes, like André Souza Lemos mensioned, I am talki
Solution
Given that Alan Turing devised the Turing Machine model of computation by abstracting what humans actually do when they compute by hand, I think one would be very hard-pressed to prove that a Turing Machine is more powerful than a human.
[note: by 'human' I assume a person augmented by a writing implement and an unbounded supply of scratch paper (which corresponds to the tape of course). Without that I believe a human is actually a (dynamically self-reconfigurable) finite-state machine with an extraordinarily large number of states]
[note: by 'human' I assume a person augmented by a writing implement and an unbounded supply of scratch paper (which corresponds to the tape of course). Without that I believe a human is actually a (dynamically self-reconfigurable) finite-state machine with an extraordinarily large number of states]
Context
StackExchange Computer Science Q#42311, answer score: 7
Revisions (0)
No revisions yet.