[Solved]: Can the human brain be considered Turing complete?

Problem Detail: 

I'm not a student in computer science, but from what I understand from the Wikipedia article on the topic, a programming language is Turing complete if it can emulate another Turing complete language's algorithm.

Now if we consider that languages like Java, C, C++ and so on are considered Turing complete, and that all algorithms implemented in programmation are by necessity first formulated in our brain, does this mean the human brain is Turing complete?

Also a human can simulate the processes going on in a processor (or we couldn't have been able to build them), but a processor can't simulate a human brain, so how is the human brain placed in terms of Turing equivalence?

Asked By : user6245072

Answered By : Andrej Bauer

Let's do this in order:

1. We do not say "another Turing complete language's algorithm" because "language's algorithm" is at best a confusing phrase. You might have meant "language's interpreter" but we cannot tell. It would be better to say "a programming language is Turing complete if it can emulate another Turing complete programming language". Note however that this is a circular condition, you need to get started somewhere. The place to start is Turing machine, of course. So: a language is Turing complete if it can be simulated by Turing machines and can simulate Turing machines. We would still have to precisely explain what "simulate" means here.

2. Languages such as C, C++ and Java are not "considered" Turing complete. They are Turing complete.

3. I deny that "all algorithms are by necessity formulated in our brains". For instance, a machine learning algorithm can come up with a new algorithm. Or perhaps an algorithm can be discovered by exhaustive search. Aliens could land and propose a new algorithm for sorting an array. Be that as it may, even if you are correct and all algorithm are formulated in our brains, your conclusion still does not follow. The following situation is in principle possible:

   • human brains are devices which spew out algorithms, i.e., they produce code to be executed, but
   • human brains are not capable of running such code

   In the extreme case a human brain could be nothing but a device which mindlessly produces all possible algorithms. One can in fact build a machine which does this, but this machine would not be Turing complete.

4. Regarding a brain simulating a processor, I highly recommend that you read Turing's original paper, keeping in mind that in 1936 "a computer" was a person performing computations. Turing machines were designed to capture the mental abilities of humans performing calculations!

5. I take issue with your claim that a machine cannot simulate a brain. You have provided no evidence for this, and it seems in principle possible that a sufficiently powerful machine would simply simulate everything that is going on in a brain. It may seem complicated, but so far as we know, the laws of physics do not prevent this possibility.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60168