5
$\begingroup$

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:

  • 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 talking about "given a word $w$ and a language $L$, is sentence $w\in L$ decidable". I am not talking about a physical computer.

EDIT 3

OK, this is another idea I came up with. Does model of computation theory include inputs that are volatile by itself? That is, the input changes itself? That is probably not the "language recognition" problem though...

$\endgroup$
  • $\begingroup$ How do you know, from a theoretical point of view (your choice) whether a language is recognized or decided by a human? What is your formal, theoretical definition of a human? $\endgroup$ – babou May 8 '15 at 13:54
  • $\begingroup$ Edited the question $\endgroup$ – Carl Dong May 8 '15 at 14:20
  • $\begingroup$ Natural language, as observed by Chomsky and proven time and again. $\endgroup$ – Raphael May 8 '15 at 15:22
  • $\begingroup$ How the TM cannot process natural language? I am not talking about speed. $\endgroup$ – Carl Dong May 8 '15 at 15:26
  • 1
    $\begingroup$ penrose asserts humans are more powerful than computers because they can work with proofs of undecidability. wrt the general question, would say its essentially an open question under active research (eg deep learning etc) related to AGI, artificial general intelligence etc $\endgroup$ – vzn May 8 '15 at 17:37
3
$\begingroup$

The computational problem of defining a language has led science to the concept of model of computation.

It is within the context of a model of computation that problems such as "given a word $w$ and a language $L$, is the sentence '$w \in L$' decidable?" can be tackled. The computer I am using now to write this answer is not a model of computation, per se. Which languages can be decided by my computer (or by any computer that has the same specifications), is a question that cannot be answered from a purely theoretical point of view. If my computer had unlimited memory, it would not be my computer, it would be something else, completely different.

Should you (or anybody else) formulate a model of computation that is inspired on how the human brain (or body) works $-$ and models like this exist $-$ it could possibly help answering some version of your question, but probably not in a way that could satisfy your fundamental curiosity.

Finally: a computational system can solve a problem by learning from its mistakes. Mistakes can be an essential part of the computational process, as defined by some models of computation.

$\endgroup$
  • $\begingroup$ Well, by "mistake" I mean mistakes like writing down the wrong number or reading the wrong characters... That kind of I/O errors $\endgroup$ – Carl Dong May 8 '15 at 16:38
  • $\begingroup$ You say that you are not talking about physical computers. Are you talking about human beings as physical (concrete) entities? If that is not the case, then the burden is upon you to express (yes, in mathematical terms) how this abstract computational entity you call "human" functions. As I said, this is not a new subject. Even though it is an extremely complex system, the human brain has been studied as a computational model for a while now. $\endgroup$ – André Souza Lemos May 8 '15 at 20:15
  • $\begingroup$ I don't know how to define 'human' in this question using precise terms, sorry. I would say just a physical, normal human plus the assumptions made in the question. I know this statement is not quite 'mathematical', but that's all I can say. $\endgroup$ – Carl Dong May 8 '15 at 20:18
  • $\begingroup$ Then, I'm sorry to say that (in my view) you don't have an answerable question. $\endgroup$ – André Souza Lemos May 8 '15 at 20:19
  • $\begingroup$ Well, I am just looking for a simple/intuitive example which may make the point clear, not necessarily a rigorous proof. $\endgroup$ – Carl Dong May 8 '15 at 20:29
1
$\begingroup$

Theorem:

Given the hypotheses of the question, and experimental evidence, the human brain is as powerful as a Turing Machine.

Proof

Experience shows that given enough paper, the human brain is capable of simulating on paper the computation of a Turing machine that is fully described on paper. By hypothesis, it does it without errors. Hence it can compute anything some TM will compute. It is actually a universal TM.

So we humans can show that we can do as much as a TM.

Now you should ask Turing Machines whether they can do as much as the human brain.

If they do not answer, it is either because you did not ask politely enough (Turing Machines are very picky on that), or because that is one thing we do that they do not do. But make sure you ask all Turing Machines, as some of them may not be knowledgeable on the topic (like humans about computability). Best is to ask on whatever they use for the TM equivalent of the human Stackexchange.com site.

Given that we can, theoretically of course, build Turing Machines with Lego pieces, this also shows that the above theorem also applies to Lego sets. Then since humans can build Lego sets, that should prove that the Human brain is at least as powerful as Lego sets, though Lego sets are serious contenders for Turing Power.

$\endgroup$
  • $\begingroup$ it makes no sense to call this a theorem, except maybe facetiously, it could never be mathematically proved. its more like a "thesis" or a "conjecture" $\endgroup$ – vzn May 8 '15 at 16:55
  • $\begingroup$ @vzn It makes as much sense as the question does. You should notice that it makes reference to experimental evidence, which is not too standard in mathematical proofs. and even less so in theorem statements. Furthermore, I never said it is mathematical, with reference to a fully formalized theory. My text may be facetious, though I left out any hint. But since you feel it is worth disputing and downvoting, you should adress the proof more precisely in disputing it: that could possibly bring some understanding. If you want to address the logic of my answer, I think it is not its weakest point. $\endgroup$ – babou May 8 '15 at 17:15
  • $\begingroup$ quite to the contrary of the assertions, supercomputers are capable of doing things that [individual] human brains cant. also human calculators were replaced with computers, such that the meaning of the word "calculator" has completely shifted. in comparison to electronics humans are unreliable/ inconsistent. etc! math proofs have no "experimental evidence" thats kind of the point. $\endgroup$ – vzn May 8 '15 at 17:33
  • 1
    $\begingroup$ @vzn All that may well be true, but the question was about Turing Machines, not supercomputers. Regarding the fact that "humans are unreliable/ inconsistent", that may well be true too, especially where I am concerned, but it was ruled out by the hypotheses of the question, which I do include explicitly in the statement of my "theorem". I was only addressing the question as asked, not stating a universal and unconditional truth. $\endgroup$ – babou May 8 '15 at 17:42
  • $\begingroup$ @vzn I have already double or triple emphasized that this question is not about time, but about power. Also, the question is not about pure mathematics, but more on logic and insight. Again, I can understand what this answer emphasizes, although it does not answer my question. On the other hand, you apparently misunderstood my question. I assumed that all computation happen in finite but unlimited time with finite but unlimited space, ignoring any human I/O or calculation mistakes. Therefore, this answer does make sense although it does not complete my question. $\endgroup$ – Carl Dong May 8 '15 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.