zlacker

>>makira+(OP)
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_+Ys
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)

>>iNic+4h1
Oh okay, that was my second guess.