zlacker

I am confused. If a single-tape turing machine receives a digit N in binary, and is supposed to write N ones on the tape, on the right side of the digit N, it performs N steps.

If you expect N ones at the output, how can this machine be simulated in the space smaller than N?

This machine must decrement the digit N at the beginning of the tape, and move to the end of the tape to write "1", so it runs in time O(N^2), not O(N)? (as it takes N "trips" to the end of the tape, and each "trip" takes 1, 2, 3 .. N steps)

Since turing machines can not jump to any place on a tape in constant time (like computers can), does it have any impact on real computers?

>>IvanK_+(OP)
Multitape Turing machines are far more powerful (in terms of how fast they can run, not computability) than single-tape machines.

But to answer your question: "space" here refers to working space, excluding the input and output.

>>IvanK_+(OP)
This paper looks exclusively at decision problems, i.e. problems where the output is a single bit.

EDIT: This makes sense because if you look at all problems with N outputs then that is just the same as "gluing together" N different decision problems (+ some epsilon of overhead)

>>cperci+p
A single tape machine is still a multi tape machine, only with one tape.

>>iNic+6O
Oh okay, that was my second guess.