Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Non-algorithmic computer capabilities

  1. Jul 9, 2011 #1


    User Avatar
    Gold Member

    (This concerns a general principle about computer hardware/software, not a specific application. I hope this is the correct subforum.)
    One of the arguments that some people (e.g., Roger Penrose) use to posit the superiority of humans to algorithmic computers is to claim (without any solid basis) that the human is a non-algorithmic computer. But suppose the human were a non-algorithmic computer. The only advantage that this would confer, as far as I am aware, is that of speed, so that there would still be no advantage in principle, only in practice in that a non-algorithmic computer could complete calculations more quickly. Is there any other advantage?

    For example, Penrose misuses Gödel's First Incompleteness Theorem, as did Lucas before him; although Fefferman tore Penrose's arguments to pieces, Fefferman did note that the whole argument concerned (the equivalent of) algorithmic processes. So Penrose claimed that the addition of non-algorithmic elements would vindicate his arguments based on Gödel's theorem. But that theorem does not mention time, I do not see that Penrose's claim could have any merit. Is there any substance to the hope that a non-algorithmic (but not mystical) process could add anything of substance besides speed?
  2. jcsd
  3. Jul 9, 2011 #2
    This question is deeply related to the Church-Turing thesis. According to the Church-Turing thesis, everything which is effectively computable can be computed by a Turing machine. Any system which can simulate a Turing machine, and which can be simulated by a Turing machine, is Turing equivalent. As of yet, nobody has been able to describe a mechanism more computationally powerful than the Turing machine (which could actually exist). In other words, if human beings can do more than Turing machines, we don't know how they do it.

    It helps to remember that Turing defined his machines according to a distilled version of the actions of a human computer (i.e., a person with pen and paper doing calculations). That is, Turing machines were originally defined so as to capture what human beings were capable of computing. It's certainly possible that Turing made a mistake and forgot some fundamental action that human computers can perform, but every attempt to extend his machines - or define other machines via a different approach - has failed to yield anything that is more powerful.

    Of course, you can assume the existence of oracles for undecidable problems and, by incorporating these into the model of computation, solve previously undecidable problems. For instance, you could define a TM which solves the halting problem, and use this to construct TMs which solve a variety of otherwise unsolvable problems. However, we can't really find a good way to define this oracle TM... so it's more an exercise in theory than in practice.

    Naturally, alternative formulations of computation can drastically affect the computational complexity. For instance, determining whether a given string is in the language of palindromes (i.e. whether it is a palindrome like "racecar" or "mom") can be solved in linear time in a random access machine (you can write a fairly simple C function to do this), but you can't possible do better than a quadratic TM (somebody correct me if I'm wrong).
  4. Jul 9, 2011 #3


    User Avatar
    Gold Member

    Thank you, aegrisomnia. A very good answer.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook