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
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.

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