5
$\begingroup$

One problem with Turing machines is that the universal Turing machine $U$ can simulate any machine $M$ but with a $\log$ slowdown, meaning $U(\#M,x)$ runs in time $O(T(n)log(n) + O(n))$, where $n=|\#M|+ |x|$, $\#M$ is a representation of $M$, and function $T$ is the running time of $M$. This $\log$ factor can get quite annoying sometime because you have to fiddle around it in definition like $K^t$ complexity (time bounded kolmogorov complexity), nowadays some paper just consider the $RAM$ model or change around the definition of $K^t$ (for instance considering actual steps in the machine $M$ instead of simulation steps by $U$) to cater to their need. They also often spend a paragraph saying how their paper shouldn't be rejected because they sightly changed around the definitions.

My question then is : what are models of computation with only a constant slowdown factor ? Preferably realistic (in the sense explained below). I know the $RAM$ model but it jumps around registers at infinite speed. Then there is the boolean circuit model which I believe would have a constant slowdown (although simulation of a circuit by a circuit is not something I think I've ever come accross) but it is non uniform. As far as i'm concerned the Turing machine model is realistic in the sense that it can be implemented in real life without breaking the laws of physics (the infinite tape can be replaced by an ever-expanding one)

Second follow-up question : why do we care about Turing machine ? Why not just do everything in $RAM$ and say goodbye to those pesky $\log$ factors. I suspect it is because of historical developments but I may be wrong.

Third follow-up question : would people be interested in a realistic computation model with only a constant slowdown (I think that I can get that with a slight modification of the definition of Turing machines)

Improve this question
$\endgroup$
4
  • $\begingroup$ (if the universe is infinite :) $\endgroup$
    – cody
    Commented Jul 13 at 19:59
  • $\begingroup$ I mean if it is not then every language is finite so everything is in O(1). Or at least we have to severely revise the definition of time complexity lol $\endgroup$
    – ULechine
    Commented Jul 13 at 20:33
  • $\begingroup$ What do you mean by the RAM model jumping between registers at infinite speed? $\endgroup$
    – Command Master
    Commented Jul 14 at 11:32
  • $\begingroup$ In the RAM model (unless i'm mistaken) you can jump at a location in memory in constant time. In some definitions RAM models have infinitely many registers and you can access the content of a register in constant time $\endgroup$
    – ULechine
    Commented Jul 14 at 14:55

2 Answers 2

Reset to default
5
$\begingroup$

A key idea that enables this is data as code: we want to execute the encoding of a machine directly, rather than indirectly via an interpreter. Some ways to turn that idea into a formal model of computation:

  • A basic variant of modern computer architectures: registers, basic arithmetic, read and write in memory, and jumps. Then you can write a program in memory and jump to it.

  • If we want to stick to Turing machines (state machine + tape), we can add a new type of transition that, when taken, loads a Turing machine, encoded on the tape, into wherever the currently running Turing machine is stored, and continues by running as the new machine. Homoiconicity is sometimes used to refer to such a feature in programming languages.

why do we care about Turing machine ? Why not just do everything in RAM and say goodbye to those pesky log factors. I suspect it is because of historical developments but I may be wrong.

Turing machines are simple and intuitive.

For a different model than Turing machines to become the standard, it should at least make it no harder to re-prove existing results in the field, many of which aren't affected by log factors to begin with.

For example, the Cook-Levin theorem proves that SAT is NP-complete by encoding the execution of a Turing machine as a boolean formula. This encoding relies crucially on a kind of "locality" of Turing machine operations which would be broken by the addition of "jump" or "eval" operations as in the alternative models above.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the homoiconicity, I had the same idea and started writing about it but now I see that's it's been thought of before. Do you have a reference to homonoic Turing machines ? I think it needs the possibility to add tapes in order to be of constant slowdown. $\endgroup$
    – ULechine
    Commented Jul 17 at 15:59
9
$\begingroup$

For any fixed k > 1, the k-tape Turing machine model has a universal Turing machine with only linear slow down. This is a result due to Martin Fürer: The Tight Deterministic Time Hierarchy. STOC 1982: 8-16.

The proof is technically involved, and presumably the reson why people don't use this model when (for instance) defining $K^t$, is because they don't want to argue that 3-tape Turing machines (or 8-tape Turing machines, etc.) is the model they want to use.

The RAM model is simple, but in its simplest form it's not terribly realistic, and modifying the model to make it more realistic seems to make the resulting model unpalatably complicated.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you I didn't know about this result. I realize now that my grievances with TM go beyond just this one issue. The inexistence of arrays, the strange lower bounds for sorting amongst other things are really annoying to deal with when designing algorithms for lower bounds proofs. For instance this problem "given a list of m numbers between [1;n], output a number in [1;n] different from the m ones" is solvable in O(m) time by a RAM machine but for Turing machine the lower bound is not clear at all. $\endgroup$
    – ULechine
    Commented Jul 17 at 16:20
  • $\begingroup$ The Turing machine model is also not "terribly realistic". After all, it suggests that SAT-solving is infeasible, yet we use SMT-solvers like Z3 all the time in real-world verification of hardware and software. $\endgroup$
    – Martin Berger
    Commented Jul 18 at 18:12
  • 2
    $\begingroup$ The comment regarding SAT solvers really says nothing about the Turing machine model. It's really a comment regarding the relevance of the supposed worst-case complexity of SAT (on any "realistic" model). Cryptographic tasks can easily be translated into SAT instances that on which SAT solvers fail miserably. So the worst-case complexity of SAT on "realistic" models is relevant for some tasks. That said, I'm not going to argue that the Turing machine model is a "realistic" programming model. But at least it can be translated into hardware fairly efficiently. $\endgroup$
    – Eric Allender
    Commented Jul 19 at 20:25
  • $\begingroup$ @EricAllender Good point regarding worst-case complexity. Thanks. However, the TM model does not map well to modern hardware, such as GPUs with their extreme parallelism, and they also don't map well to what is costly in modern processors (data movement). $\endgroup$
    – Martin Berger
    Commented Jul 21 at 16:06

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.