Is the mind more powerful than a Turing Machine?

[Demiurge]

In essence, a decision problem asks whether we can determine for some input whether or not it falls within some particular set using an algorithm. That is, it asks for any arbitrary x of the input type (could be numbers, formulas, etc), is there is a recursive function f such that f(x) delivers a yes-or-no verdict on whether x is a member of the chosen set? If so, the problem is said to be decidable and if not, undecidable. For example, consider the decision problem for validity in some system of logic. It asks whether there is a recursive function that can determine whether or not an arbitrary formula is valid (falls within the set of valid formulas). This problem is decidable for the propositional calculus and undecidable for the predicate calculus, if just one dyadic predicate is admitted (this is Church's theorem).

A Turing machine can decide any decidable problem. I.e., it can compute the function that tells us whether a given input falls within the chosen set, if the problem is decidable. However, its computations are algorithmic so it cannot decide undecidable problems. In fact, a function is recursive if and only if it is Turing computable. The question asked is: does there exist an undecidable problem for which we can deliver a verdict, thereby elevating ourselves above the deterministic calculations of computers?

 

[Blowtus]

Does there exist an undecidable problem for which we can deliver a decision - isn't that a little contradictory?

Isn't the mind more than a decision maker? Doesn't it set the terms and the questions as well?

 

[Demiurge]

Does there exist an undecidable problem for which we can deliver a decision - isn't that a little contradictory?

No, because an undecidable problem is one such than no algorithmic procedure can solve it. If it can be solved by some other means, it is still undecidable in the sense of the word I'm using.

Isn't the mind more than a decision maker? Doesn't it set the terms and the questions as well?

I suppose that it does, in some sense, but if from a formal POV it is unable to perform any computations that cannot be performed on a Turing Machine, it sets a bound on our ability to solve problems, and that bound is the same as a computer.

I want to say more but I have to go right this moment.

 

[judas69]

Given that the Turing machine outlines the limitations of computation, saying something like the "mind" is beyond this is not something I accept when Alan's model appears to be so very fundamental.

 

[Blowtus]

I am by no means very knowledgeable on the formal logic side of things... but given sufficient decision making software, is it possible for anything to be 'undecidable'? A simple rationale like 'if x question has possible answers a, b, c, but x cannot be otherwise calculated, choose randomly either a, b, or c' would seem to make anything decidable, no?

 

[Demiurge]

First, I am pleased to see this topic generating some interest.

Given that the Turing machine outlines the limitations of computation, saying something like the "mind" is beyond this is not something I accept when Alan's model appears to be so very fundamental.

Well, it would seem to outline the limits of effective computation. For a definition of an effective procedure:

A method, or procedure, M, for achieving some desired result is called ‘effective’ or ‘mechanical’ just in case

1. M is set out in terms of a finite number of exact instructions (each instruction being expressed by means of a finite number of symbols);
2. M will, if carried out without error, produce the desired result in a finite number of steps;
3. M can (in practice or in principle) be carried out by a human being unaided by any machinery save paper and pencil;
4. M demands no insight or ingenuity on the part of the human being carrying it out.

http://plato.stanford.edu/entries/church-turing/

The Church-Turing Thesis is that a function is effectively computable iff it is λ-definable/general recursive/Turing computable. There is no airtight mathematical proof of this thesis, but in its favor is that in the 70+ years since it was formulated, no exceptions have been found.

However, there are plenty of functions that are not effectively computable. The question of the thread is: is there any reason whatsoever to suspect that humans are to perform some of these non-effective computations? There are a variety of arguments to this effect, such as:

We know that any axiomatized theory that is strong enough to represent a minimal amount of arithmetical reasoning (more specifically, Robinson arithmetic or any theory that is an extension of it) is incomplete, if it is consistent. This is the end result of Goedel's first incompleteness theorem, with a little help from Rosser. That is, there is some sentence that the theory cannot prove and such that the theory cannot prove its negation either. The canonical example is basically a sentence which says that it is unprovable in the theory. (If we wish to be more precise, it "says" that the statement having Goedel number n is unprovable in the theory and it is the very statement that has Goedel number n.) Well, we can see that this statement is true. It is unprovable within the theory, like it says. So, it is said, we possess a non-mechanical insight into mathematics. One fairly obvious counterargument is that the argument appears to assume that the mind is both complete and consistent. It's not a big deal to prove the Goedel sentence for some other theory. You can just make a new theory that includes the Goedel sentence of the previous one as an axiom. What would be a big deal is having a theory that captures arithmetic so well that it is both complete and consistent, in violation of the 1st theorem. I.e., it would be a big deal if the mind were able to capture arithmetic in this way.

 

[Demiurge]

I am by no means very knowledgeable on the formal logic side of things... but given sufficient decision making software, is it possible for anything to be 'undecidable'? A simple rationale like 'if x question has possible answers a, b, c, but x cannot be otherwise calculated, choose randomly either a, b, or c' would seem to make anything decidable, no?

I'm not sure that I understand this point. Our method doesn't just have to answer the question with some output for every input, but it has to do it correctly. For example, let us say we're looking for a procedure to answer the question of whether α is valid in first order logic for any formula α. If you give me a procedure that just answers "yes" no matter what the input is, you haven't solved anything.

 

[Blowtus]

Yep, fair enough - so 'undecidable' is really 'not correctly decidable'.
A question such as 'what colour rose do you prefer?' is in some sense 'correctly decidable' for a human I think, would you agree? I think this topic probably comes down to an idea of what correct is, which is probably simple in the formal logic conception that a turing machine operates under, but less simple (I think) when it comes to a real world entity such as a mind.

 

[judas69]

Effective computation is a necessary formality; there is no answer to this that will not dwell in mystery. There is also nothing observably peculiar about the functioning brain that would strongly indicate an occurrence of or a necessity for, either. I'm hard-nosed I know.