Actually Yinsheng, NP Complete is solved by Turing Machines, NP Hard may not be. We don't actually know because they haven't completed yet. Theoretically they might complete, but we don't know that they will.

Instead of butting our heads against intractable problems we need to rethink our approach, to find a solution. One thing that TM is not capable of doing very often is starting over with a new approach to an old problem that it almost but not quite solved.

This is because TM doesn't think about the intractability of problems, it just processes them as they are presented. Theoretically this can be got around we just need to find a way of having the computer quit working on NP Hard problems and rethink them, but as yet that has only been achieved in the optimization problem.

@ Joachim Pimiskern‘s answer：

A neuron activity is not a function computation. When neurons compute a function, cannot the function be computed by a Turing Machine?

The only function that I know of that can't be done by a turing machine is self negation.

A = NOT A This is because self negation breaks consistency and would therefore be illegal in any formal mathematical system. It is because of this that The incompleteness theorem was formed. There might also be some NP hard functions that the brain does that a Turing machine would not complete.

Roger Penrose claimed that there are mathematical poblems that can be solved by humans, which are uncomputable in a Turing architecture and gave as an example his proof that certain polygons will tile the universe but in a never-repeating way. What is not clear to me is whether these are 'computed', however, if computation is defined in relation to Turing machine architecture - although of course Turing originally defined a computer as a human being, with an electronic device being merely an attempt at simulating a computer (if I remember rightly).

@ Graeme Smith

Concerning A=NOT A.

Although Turing Machine can't compute it ,human  cannot do it too,I think. It contradict identical law.

 @ Jonathan Edwards

In the question, "computation" refers to Turing computation.

Could you remember the reference of Roger Penrose you mentioned?  Thank you very much!

 @ Joachim Pimiskern

You mean that chaos or randomness in neurong(s) iis not computed by Turing Machine. Do you think we can abstract a higher leve of neurons, determinacy, as to calculate neccesarily 1+1=2 rather than 3?

@ Cristian Chilipirea

Turing thought Godel number is not computed by Turing Machine (TM, say "computer" in Turing's paper ). And some functions such as the Diagonal Function (as Cantor showed) are found uncomputabke by TM too. I guess that all the these functions , uncomputable functions by TM, cannot be computed by human being. Could I say human's computation (or human's intelligence) equals TM if no one can find a function which only computed by human rather than by TM?

I think your idea is simuliar with me.

Yinsheng, A = not A is a paraphrase of godels impossible formula that proved that formal systems are not complete, because they can express but not compute everything that they can express.

@ Graeme Smith

So，the paraphrase A = not A  is not computable for both human and TM. It seems , all functions which cannot be computed by TM, cannot be computed by humam too. Right?

Yinsheng,

Are you asking a tautological question then? If 'computable' or 'computing' is defined by what a Turing machine can achieve then nothing can compute anything beyond this because it would then not be 'computing'. The argument appears to be circular.

Penrose's claim is discussed in detail in his 1994 book 'Shadows of the Mind' - which I understand as the best known discussion of the human mind's ability to do things a Turing machine cannot do and its relevance to consciousness.

 What I think has become more widely recognised since Penrose wrote this is that the human brain does not 'compute' in anything like the way a Turing machine does. It makes use of time for coding in a continuous fashion through complex phase matching relations and so is not even algorithmic. It is neither serial nor parallel, but massively convergent/divergent at every step. It works on an inference by best fit principle, etc. etc. What may be most significant is that because the brain uses real dynamic processes in spacetime to derive its conclusions it is in a position to test and confirm ideas about the nature of real dynamic processes in spacetime directly. A computer cannot begin to do that because it operates in a code system which makes no use of real dynamics - i.e. distances and times within the architecture do not figure in the coding as continua but only indirectly as determinants of discrete values. The brain is also endowed with a genetic programme that may act as 'look up tables' for a whole range of non-computable questions, allowing it to solve without computing.

At the end of the day I think there are some rather tricky questions about what it means to 'solve a problem'. We talk about what machines or humans 'can' do, but in reality we are talking about what they 'will' do. A human will conclude that it has totally proven a particular theorem and for some theorems she cannot build a computer that will 'run' such a proof. But as to what that implies, do we really understand?

@ Jonathan Edwards

We can define "computation" as operation that Turing Machine (TM) does. In the case, there would not be circle-unlimited.

Then it seems, we can't say human's consciousness have difference with TM.Although great amount neutrons are random (like ice mountain under level), but we can neglect them, to focuns on their deterministic activity (above water level), which corresponds to TM. Although brain has continious activity, but in nutron even quantum level, they are descrete.

This is nowadays things not "will-do" things.

Computing pre-existed Turing Machines, Yinsheng. Even Turing did not claim that it didn't. It is Church that claimed that anything that can be computed can be computed by a Turing Machine eventually. Turing then went on to describe NP Hard problems that would not complete eventually, which tends to limit TM computability.

Although we can choose to neglect those things that don't fit the theory, this is known as whistling in the dark. When the greater weight of things falls under water level, choosing to blind ourselves to them, is simply silly. It's one reason why the ocean is dying we have been neglecting it because it is under water level. 2/3 of the earth is under water we simply cannot afford to ignore it.

So it is with science, whistling in the dark, just doesn't work in science. There are too many things that are missed in this way.

@Graeme Smith

NP is hard solved by TM and by human beings too.So Here, TM=human beings. Up to now, we can't find even one function which can't computed by TM yet by human beings.

Altough,  @ Cristian Chilipirea says, random of neutrons  can't be computed or similated, but it is under counsciousness rather than consciousness itself. The certianty above  random  activity,is described by TM too.

The  random  activity of neurons is not computed by human beings too, for that there is not a function expressed in the brain, so TM =human beings about computing  random  activity in brains of human beings.

Actually Yinsheng, NP Complete is solved by Turing Machines, NP Hard may not be. We don't actually know because they haven't completed yet. Theoretically they might complete, but we don't know that they will.

Instead of butting our heads against intractable problems we need to rethink our approach, to find a solution. One thing that TM is not capable of doing very often is starting over with a new approach to an old problem that it almost but not quite solved.

This is because TM doesn't think about the intractability of problems, it just processes them as they are presented. Theoretically this can be got around we just need to find a way of having the computer quit working on NP Hard problems and rethink them, but as yet that has only been achieved in the optimization problem.

@Graeme Smith

 Thanks！I'll try to think about your new words.

A Logical Journey, From Gödel to Philosophy – Hao Wang

any one here familiar with Wang's B Machine?