MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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. – Joel David Hamkins Sep 3 '13 at 14:41
I imagine there are hundreds of examples of languages without this problem (every modern programming language, for instance) but I don't know of any simplified, theory-driven model of computation that doesn't have this problem. Recursive functions, Lambda calculus, tag systems, and brainfuck all have computable functions that they implement in exponential time, but a Turing machine could implement these functions in polynomial time. I'm looking for an example along the lines of these simplified models of computation. – GMB Sep 3 '13 at 19:23
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. – Joel David Hamkins Sep 3 '13 at 19:48
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. – GMB Sep 3 '13 at 19:56
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. – Joel David Hamkins Sep 4 '13 at 12:06

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.

share|cite|improve this answer

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.

share|cite|improve this answer
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. – Joel David Hamkins Feb 12 '14 at 15:00
It's not at all clear how this answers the question. It might make sense to make this response CW. – Todd Trimble Feb 12 '14 at 22:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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