The Church-Turing is a hypothesis about the nature of computable functions. It states that a function on the natural numbers is computable by a human being following an algorithm, ignoring resource limitations, if and only if it is computable by a Turing machine.

In wikipedia (https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis), explains some of the philosophical interpretations of it:

  1. The universe is equivalent to a Turing machine; thus, computing non-recursive functions is physically impossible. This has been termed the strong Church–Turing thesis, or Church–Turing–Deutsch principle, and is a foundation of digital physics.

  2. The universe is not equivalent to a Turing machine (i.e., the laws of physics are not Turing-computable), but incomputable physical events are not "harnessable" for the construction of a hypercomputer. For example, a universe in which physics involves random real numbers, as opposed to computable reals, would fall into this category.

  3. The universe is a hypercomputer, and it is possible to build physical devices to harness this property and calculate non-recursive functions. For example, it is an open question whether all quantum mechanical events are Turing-computable, although it is known that rigorous models such as quantum Turing machines are equivalent to deterministic Turing machines. (They are not necessarily efficiently equivalent; see above.) John Lucas and Roger Penrose have suggested that the human mind might be the result of some kind of quantum-mechanically enhanced, "non-algorithmic" computation

The third interpretation is the one that seems more interesting to me. I know that there is evidence against the possibility of hypercomputation, but it is still interesting to consider the universe as a hypercomputer.

However there is no reference of who developed that interpretation.

So my questions are: Who did develop that interpretation? Is there any paper about it?

  • $\begingroup$ The part you quote has references (currently "[58][59]") which you removed from the quote. Why don't you start by reading those references? That seems like an natural place to start learning more. Those references are pretty accessible. (Caution: be warned that many computer scientists tend to be pretty critical of those arguments.) $\endgroup$
    – D.W.
    Feb 10 '19 at 2:04
  • $\begingroup$ Yeah, but it says that Penrose and John lucas have suggested that the mind is uncomputational and then add the references. I did not read those references since they seemed to adress to that question instead of mine (which has to do more with the whole universe than the brain) I was thinking that maybe Turing or Church were the ones who did that interpretation. It not, then, were Penrose and Lucas? @D.W. $\endgroup$
    – sztorwi
    Feb 10 '19 at 11:12
  • 1
    $\begingroup$ I don't know that there's any literature on it. I mean, either the universe can be simulated by a computer or it can't; it's kind of an obvious thing to say once you are aware of the concepts of decidability etc., so it's not something I'd expect you to find a reference for. Who first had that realization? I don't know, probably many people. So I'm not sure there is going to be a literal answer to the actual question you asked. You might try pondering why you want to know the answer and whether there's perhaps some way to get at that, other than "who first had this thought?". $\endgroup$
    – D.W.
    Feb 10 '19 at 18:08
  • 1
    $\begingroup$ In other words, you're calling it an "interpretation" like it's some big deal, but it's just one rather obvious possibility. Perhaps you might enjoy reading Scott Aaronson's thoughts on this; he's written a bunch about hypercomputation. Church-Turing, etc. $\endgroup$
    – D.W.
    Feb 10 '19 at 18:09
  • $\begingroup$ Well, if Penrose argues that the mind is not computable, that implies an answer to your question, because our minds are parts of the universe. So if there is some processes in our mind, which cannot be computed, there are some processes in the universe, which cannot be computed. In "Shadows of the Mind" Penrose first gives a rather mathematical proof for the existence of this kind of process; in a second part he goes into physics and speculates why and where this non-computability may come from. $\endgroup$ Mar 8 '19 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.