7
$\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...

Improve this question
$\endgroup$
8
  • 2
    $\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
    Commented May 8, 2015 at 13:54
  • $\begingroup$ Edited the question $\endgroup$
    – Carl Dong
    Commented May 8, 2015 at 14:20
  • $\begingroup$ Natural language, as observed by Chomsky and proven time and again. $\endgroup$
    – Raphael
    Commented May 8, 2015 at 15:22
  • $\begingroup$ How the TM cannot process natural language? I am not talking about speed. $\endgroup$
    – Carl Dong
    Commented May 8, 2015 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
    Commented May 8, 2015 at 17:37

6 Answers 6

Reset to default
7
$\begingroup$

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]

Improve this answer
$\endgroup$
1
  • $\begingroup$ Need to add unlimited time. $\endgroup$
    – vonbrand
    Commented Mar 7, 2020 at 22:12
5
$\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.

Improve this answer
$\endgroup$
6
  • $\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
    Commented May 8, 2015 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
    Commented May 8, 2015 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
    Commented May 8, 2015 at 20:18
  • 1
    $\begingroup$ Then, I'm sorry to say that (in my view) you don't have an answerable question. $\endgroup$
    – André Souza Lemos
    Commented May 8, 2015 at 20:19
  • 1
    $\begingroup$ The counterexamples I used were my best shot at making the point that your question (again, in my view) is not well formulated. As it is, it might find more rich feedback at philosophy.stackexchange.com. $\endgroup$
    – André Souza Lemos
    Commented May 8, 2015 at 20:47
3
$\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.

Improve this answer
$\endgroup$
9
  • $\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
    Commented May 8, 2015 at 16:55
  • 1
    $\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
    Commented May 8, 2015 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
    Commented May 8, 2015 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
    Commented May 8, 2015 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
    Commented May 8, 2015 at 18:00
1
$\begingroup$

Here is a question on Turing completeness of neural networks. In my answer, I also discuss the human brain a bit, and I reference also this question here.

I think allowing for some type of infinite medium for infinite external memory is not so interesting. When you also consider a theoretical human brain without limitation in size, it is obvious that you could encode any possible Turing machine as a human brain, and thus the human brain + external memory is Turing complete.

The more interesting question is when you do not combine it with infinite external memory but just ask about the human brain itself.

You could say then a human brain has finite memory, so it is not Turing complete.

However, consider a standard PC. A physical instance of a PC also has finite memory and thus is not Turing complete. However, there is the concept of an abstract machine. And when you ask the question, is a PC Turing complete, then you don't really want to know about one specific physical instance, but you want to know about the concept of a PC, where you could just add as much memory as needed. It is relatively straightforward how to define such concept of a PC.

So, back to the human brain: I think this is analogue. You are not interested in one specific physical instance of a human brain. The question is about the concept of a human brain. But this is now less straightforward. How do you define such concept of a human brain?

Of course, such concept could just be as large as needed to encode any Turing machine. But then, the most relevant aspect is about the memory. Would such concept of a human brain have infinite memory? I'm not sure there is a clear answer. There many different kinds of memory in the human brain. Some kinds are clearly static (e.g. the current activations, like in a artificial RNN). But then it also has associative memory. The concept of such associative memory can easily be regarded as infinite memory.

Following this argumentation, the concept of a human brain is Turing complete.

Improve this answer
$\endgroup$
0
$\begingroup$

In theory, a Turing machine has enough power to simulate all the molecules in a brain, so there is no doubt that it is as capable.

We can also argue that in some decades, AI will be able to reach human performance and pass the Turing tests successfully, without the need for a detailed physical simulation, just global behavior.

Improve this answer
$\endgroup$
-1
$\begingroup$

My take:

If by Turing Machine you mean "a plane" Deterministic Turing Machine (DTM), then, a human brain would be strictly more powerful as long as a brain can be

  • a non-deterministic TM: in this case, the same set of problems can be solved by both, but for some of them, the running time of the brain is faster ¿P machine = NP brain?

  • a non-deterministic TM using randomized algorithms. Here: the brain can solve, with high probability, problems that a DTM can't.

  • a non-deterministic TM using randomized algorithms and quantum algorithms.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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