This site is supported by the advertisements on it, please disable your AdBlocker so we can continue to provide you with the quality content you expect.

Welcome to Our Community

Wanting to join the rest of our members? Feel free to sign up today.

  1. Just a heads up... In the next week or two we will be making some major upgrades to the site to bring the software and server fully up to date. While the upgrade happens the site will be offline for the day. There will be some quirkiness after the upgrade, but we'll get it all sorted out.
    Dismiss Notice

Is the mind more powerful than a Turing Machine?

Discussion in 'The Philosopher' started by Demiurge, Jan 28, 2009.

  1. Demiurge

    Demiurge This user has no title

    Joined:
    Aug 12, 2003
    Messages:
    1,520
    Likes Received:
    8
    Trophy Points:
    38
    Location:
    lunar stonehenge
    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?
     
  2. Blowtus

    Blowtus Member

    Joined:
    Jul 14, 2006
    Messages:
    906
    Likes Received:
    2
    Trophy Points:
    18
    Location:
    Straya
    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?
     
  3. Demiurge

    Demiurge This user has no title

    Joined:
    Aug 12, 2003
    Messages:
    1,520
    Likes Received:
    8
    Trophy Points:
    38
    Location:
    lunar stonehenge
    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.

    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.
     
  4. judas69

    judas69 god is in the radio

    Joined:
    Dec 29, 2005
    Messages:
    2,029
    Likes Received:
    2
    Trophy Points:
    38
    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.
     
  5. Blowtus

    Blowtus Member

    Joined:
    Jul 14, 2006
    Messages:
    906
    Likes Received:
    2
    Trophy Points:
    18
    Location:
    Straya
    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?
     
  6. Demiurge

    Demiurge This user has no title

    Joined:
    Aug 12, 2003
    Messages:
    1,520
    Likes Received:
    8
    Trophy Points:
    38
    Location:
    lunar stonehenge
    First, I am pleased to see this topic generating some interest. :)

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

    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.
     
  7. Demiurge

    Demiurge This user has no title

    Joined:
    Aug 12, 2003
    Messages:
    1,520
    Likes Received:
    8
    Trophy Points:
    38
    Location:
    lunar stonehenge
    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.
     
  8. Blowtus

    Blowtus Member

    Joined:
    Jul 14, 2006
    Messages:
    906
    Likes Received:
    2
    Trophy Points:
    18
    Location:
    Straya
    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.
     
  9. judas69

    judas69 god is in the radio

    Joined:
    Dec 29, 2005
    Messages:
    2,029
    Likes Received:
    2
    Trophy Points:
    38
    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.
     

Share This Page