4 ms·
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 p
by IvanK_net 1y ago
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?
- cperciva 1y agoMultitape 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_net 1y agoA single tape machine is still a multi tape machine, only with one tape.
- iNic 1y agoThis 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)
- IvanK_net 1y agoOh okay, that was my second guess.