patternMinor
Does "output" always imply halting in computability?
Viewed 0 times
implyalwayshaltingoutputcomputabilitydoes
Problem
$L = \{P : P(n)$ outputs $n^2$ for all $n \in N \}$
In questions of this nature, are we supposed to assume that "outputs" means "halts and outputs"? In modern programming languages, I can certainly "output" using a print statement and then have the program go into a loop after that.
In questions of this nature, are we supposed to assume that "outputs" means "halts and outputs"? In modern programming languages, I can certainly "output" using a print statement and then have the program go into a loop after that.
Solution
The output of Turing machine is the content of the tape when it halts.
This is the standard definition. If a machine has written some string $s$ to its tape but hasn't halted yet, a straightforward reduction from the undecidability of the halting problem means that you have no way of knowing if it will ever write more characters to its tape, so you can't know if $s$ will be the "final" output. That means, for example, that you can't say that, if a non-halting computation never changes the string on the tape after the $t$th step, then the output is that unchanging tape string.
However, see Andrej's answer for a way of getting a well-defined output from a non-halting machine. The key point there is that the output tape is read-only so once a bit of the output has been written, you know that bit will never change.
This is the standard definition. If a machine has written some string $s$ to its tape but hasn't halted yet, a straightforward reduction from the undecidability of the halting problem means that you have no way of knowing if it will ever write more characters to its tape, so you can't know if $s$ will be the "final" output. That means, for example, that you can't say that, if a non-halting computation never changes the string on the tape after the $t$th step, then the output is that unchanging tape string.
However, see Andrej's answer for a way of getting a well-defined output from a non-halting machine. The key point there is that the output tape is read-only so once a bit of the output has been written, you know that bit will never change.
Context
StackExchange Computer Science Q#29383, answer score: 5
Revisions (0)
No revisions yet.