10
$\begingroup$

Certain models of computation are technically Turing-Complete, but cannot feasibly simulate a Turing Machine within the usual time constraints we hope for. One example of this is Godel's recursive functions: the computable function $f(x) = 2x$ is implemented by calling the successor function $2x$ times, which intuitively takes $O(2^x)$ time.

So, my question:

What Turing-complete models of computation, or simplistic programming languages (Turing tar pits), can compute every computable function with only a worst-case polynomial-time blowup in time complexity over the fastest Turing machine that computes that same function?

$\endgroup$
  • 1
    $\begingroup$ Aren't there hundreds of examples? This is the robustness of $P$ as a complexity class, that we can often (and indeed usually) simulate a different model of computability in our own, with at most polynomial time cost. $\endgroup$ – Joel David Hamkins Sep 3 '13 at 14:41
  • 2
    $\begingroup$ Well, some Turing machine models are also weak in this way. For example, if you have only two symbols and a single tape, and are forced to use unary notation (so that you know when the input ends), then it will take exponential time to simulate the usual machines, which are more powerful. $\endgroup$ – Joel David Hamkins Sep 3 '13 at 19:48
  • $\begingroup$ Okay, good point - I should've specified that I'm only "counting" the Turing machine models that have sufficient alphabet size to solve all problems as quickly as possible. $\endgroup$ – GMB Sep 3 '13 at 19:56
  • $\begingroup$ On the other side, I can equip a Turing machine with a computable oracle that can compute some complicated function in one step. This souped-up model of computability is Turing equivalent to the standard machines, but even faster than your machines. It seems there is an entire hierarchy here. $\endgroup$ – Joel David Hamkins Sep 3 '13 at 20:05
  • 1
    $\begingroup$ Meanwhile, I would point out that even the ordinary notions of Turing machine are idealized concepts, and not about what we can actually build in the real world. We cannot expect to build a Turing machine in the physical world that would undertake computation of appreciable size, since once the paper tape was large enough, it would be subject to gravitational forces. Is it in orbit? If coiled, once the mass became a certain size it would collapse into a black hole. If uncoiled, it would likely tear. Long story short: Turing computability is a notion of idealized computation. $\endgroup$ – Joel David Hamkins Sep 4 '13 at 12:06
6
$\begingroup$

One of the simplest model that has recently been proved to be an efficient simulator (polynomial time slowdown) of Turing machines are 2-tag systems:

Damien Woods, Turlough Neary, "On the time complexity of 2-tag systems and small universal Turing machines" (2006)

Abstract: We show that 2-tag systems efficiently simulate Turing machines. As a corollary we find that the small universal Turing machines of Rogozhin, Minsky and others simulate Turing machines in polynomial time. This is an exponential improvement on the previously known simulation time overhead and improves a forty year old result in the area of small universal Turing machines.

$\endgroup$
0
$\begingroup$

Because we can easily invent as many small variations of Turing-complete models of computation as we like (see comments below the question), an answer to this question should try to concentrate on relevant (and Turing-complete) models, i.e. models that have either been investigated in illuminating non-trivial ways, or are important for better understanding of actually available computing resources.

I have been exposed in non-trivial ways to tape based Turing machines, register machines and pointer machines. It seem like the wikipedia article on abstract machines is intended to give an overview for related Turing machine equivalent models, but in its current form it is mainly a collection of useful keywords and links.


I'm currently looking for models and investigations related to machines limited to write once read many (WORM) memory for large amounts of data. None of the abstract machine models I found so far investigated these. Is it possible to create a model of such a machine that is equivalent to a Turing machine in the sense of the question above? (Edit: It looks like it was proved recently that Wang B-machines achieve this. I haven't read the paper yet.) This question seems to be both non-trivial and interesting to me, contrary to the comments below the question, which is the main reason why I wrote this answer.

$\endgroup$
  • $\begingroup$ Punchtape Turing machines, for which the machine can mark each cell at most once, punching a hole in the paper tape or not, are like your write-once-read-many machines, and have been investigated. Punchtape machines are Turing complete, and have been investigated, but I find it likely that there is a substantial time cost. $\endgroup$ – Joel David Hamkins Feb 12 '14 at 15:00
  • $\begingroup$ It's not at all clear how this answers the question. It might make sense to make this response CW. $\endgroup$ – Todd Trimble Feb 12 '14 at 22:05

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.