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?

Improve this question
$\endgroup$
10
  • 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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 12:06

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
$\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.

Improve this answer
$\endgroup$
2
  • $\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, 2014 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, 2014 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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