38
$\begingroup$

Are there any theoretical machines which exceed Turing machines capability in at least some areas?

$\endgroup$
  • 5
    $\begingroup$ Questions like "is X a defining characteristics of out(sic) universe?" is a physics question since physics is exactly the study of "the laws of the universe". Computer science is about mathematical objects which sometimes happen to be implementable through physical means. $\endgroup$ – Bakuriu Apr 5 '16 at 15:18
  • 2
    $\begingroup$ I'd recommend looking into "super turing machines", especially those as proposed by Have Siegelmann: umass.edu/newsoffice/article/… and binds.cs.umass.edu/papers/1995_Siegelmann_Science.pdf $\endgroup$ – nobillygreen Apr 5 '16 at 16:09
  • $\begingroup$ 1. We ask that you ask only one question per post, please. If you have other questions, you can post them separately, after seeing answers to this. Also, questions about the defining characteristics of our universe are physics questions, and are off-topic here. I'm editing out the supplemental questions, to help you focus on a single question. You can post them separately (see the revision history to find them again). 2. What research have you done? What are your thoughts? A one-sentence question is too short. Try to edit it to flesh it out; that will help give you better answers. $\endgroup$ – D.W. Apr 5 '16 at 19:03
  • $\begingroup$ 3. "Can we assume that...." -- no, of course not. Why would you think that you can assume it? You can't just assume something because it would be nice if it were true, or it seems like it might be true, or because we don't immediately see a reason why it would be false. Computer science is about proof, not about just assuming things. What is your real question? $\endgroup$ – D.W. Apr 5 '16 at 19:05
26
$\begingroup$

The Church–Turing thesis (in one formulation) states that everything that can be physically computable can also be computed on a Turing machine. Assuming you believe this theses, and given that you're interested in functions which such machines could compute (and not in, say, interactive computation), then no hypercomputation is possible.

The Church–Turing thesis only concerns itself with what is computable, but not with the efficiency of computation. It is known that Turing machines are not so efficient, though they polynomially simulate classical computers. Quantum computers are believed to be exponentially more efficient than Turing machines. In this sense, you can beat Turing machines (if you could only build a scalable quantum computer).

Scott Aaronson probably has more to say about this — I'll let you look this up on your own.

$\endgroup$
  • $\begingroup$ Actually I have Scotts blog already bookmarked. :) Anyway since the CT thesis still holds today (unless something happened I am unaware of) all that remains is to talk about definition of computable or look for machine that somehow disproves CT. $\endgroup$ – user1561358 Apr 5 '16 at 13:51
  • 3
    $\begingroup$ "As discussed in this essay, complexity theory has by now branched out far beyond deterministic Turing machines, to incorporate (for example) quantum mechanics, parallel and distributed computing, and stochastic processes such as Darwinian evolution." (Why Philosophers Should Care About Computational Complexity, by Scott Aaronson, p. 49) $\endgroup$ – reinierpost Apr 5 '16 at 16:29
  • 1
    $\begingroup$ I think it's also noteworthy that quantum computers don't speed up an arbitrary task AFAIK. And they "only" speed it up by a maximum of 2^N where N is the number of quantum bits. $\endgroup$ – HopefullyHelpful Apr 7 '16 at 7:45
37
$\begingroup$

Yes, there are theoretical machines which exceed the Turing machines in computational power, such as Oracle machines and Infinite time Turing machines. The buzzword that you should feed to Google is hypercomputation.

$\endgroup$
13
$\begingroup$

The Church–Turing thesis doesn't need to be taken as an article of faith; it probably makes more sense to regard it as stating a description, a definition, of what we mean by the term "computation", and it is quite a narrow notion of computation, too: computation by a single processor executing steps strictly sequentially without external interference. Certain aspects of computation we need to reason about aren't covered by this notion, and many additional pieces of mathematical theory have been developed within computer science to address such concerns.

So the Church–Turing thesis is not so much a defining characteristic of our universe as it is a defining characteristic of a particular way of doing certain things in our universe.

In this respect, it can be likened to Euclidean geometry. Is our universe inherently Euclidean? Why are our methods of measuring land limited by its principles? Can't we have hypergeometry that allows more powerful land measurement? The answer is: we can and we do, but we don't always call the results "land measurement" or "geometry".

Similarly, our theory and practice regarding computation extend beyond what Turing machines can describe (e.g. there are process calculi for describing concurrent systems), but we don't necessarily call those extensions "computation".

$\endgroup$
  • $\begingroup$ by "computation by a single processor executing steps strictly sequentially without external interference", do you mean that if a computer has external interference, or can work in parallel, it's much more powerful than a turing machine? $\endgroup$ – kate Dec 2 '17 at 18:49
  • 1
    $\begingroup$ Not quite. If all you want to know is which mappings from finite inputs to finite outputs can be computed, then adding these won't give you more power: you won't be able to compute more mappings than before. $\endgroup$ – reinierpost Dec 4 '17 at 10:20
5
$\begingroup$

One theoretical weakness of a Turing machine is its predictability. An all powerful and omniscient opponent could exploit this weakness when playing some game against the Turing machine. So if a theoretical machine had access to a random source which its opponent could not predict (and could conceal its internal state from its opponent), then this theoretical machine would be more powerful than a Turing machine.

The problem with this type of theoretical machine in real life is not whether the random source is perfectly random or not (assuming it to be perfectly random is a harmless idealization), but that we can never be sure whether we were successful in concealing our internal state from our opponent. So in the concrete case, one can never be sure whether it is valid to idealize the current instance of a situation by such a machine. This is only slightly better than the situation for most types of hypercomputation, where it is unclear to me which idealized situations should be modeled by those (I once replied: So I need some type of all-knowing miracle machine to solve "RE", I didn't know that such machines exists.)

I was recently surprised to find out that one can consistently accept the existence of Turing machines, and reject the existence of Turing machines with access to an oracle for deciding the halting problem problem of a Turing machine. This is because the oracle can lie (but one cannot prove that it lies) and claim that a non-halting computation would actually halt, and then taking forever while answering with an infinite number, when asked for a bound on the number of steps. (I realized this after writing a technical justification for the excuse: Then I might justify my doubts about $\Pi_2^0$ sentences by explaining that I'm unsure about how to separate finite inputs from infinite inputs, and hence am unsure whether quantification over the inputs is well defined. That excuse itself arose from a conversation with another Thomas, namely Thomas Chust.)

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.