For some machine models of computation there is no question what their input and output is: it's just the contents of some specific "cells", e.g. on a "tape" isomorphic to $\mathbb{N}$.
Consider for example finite automata with a static head: the input can be seen as the time sequence of symbols in cell $0$ until the first occurence (in time) of the blank (= end-of-input) symbol $b$.
Alternatively (when the automaton can move its head to the right), the input can be seen as the symbols in a spatial sequence of cells starting at cell $0$ until the first occurence (in space) of $b$.
For Turing machines (esp. with an $\mathbb{N}$-tape) it is by no means obvious what should be considered as the input and output of a given machine $T$ together with an initial tape $I$ and its corresponding final tape $O$ (assuming that $T$ halts on $I$).
Possible generic "definitions" of what is to be considered as "input" are:
- the complete initial tape $I$
- the shortest sequence starting at cell $0$ that contains all non-blank symbols
- the part of the tape which has been visited, finally
- the visited cells which "made a difference"
By "making a difference" I mean the following: Some cells are visited only to write intermediate results into them, irrespective of their initial contents. The initial contents of those cells don't make a difference and should not be counted as input.
There are also "definitions" based on the occurence of "end-of-input" markers:
- the sequence starting at cell $0$ until the first occurence of the blank symbol $b$
- the sequence starting at cell $0$ until the first occurence of word $w$ (which may contain arbitrary symbols of the tape alphabet)
There are also "definitions" based on the position of the head, e.g. the definitions above with "starting at cell $0$" replaced by "starting at the position of the head".
Some of these "definitions" may – in special cases – coincide with another.
What I've learned so far:
-
"input" and "output" are not an explicit part of the definition of Turing machines.
-
It is sometimes laid down by "convention" how the input has to be given and how the output has to look like (see e.g. Cooper, Computability Theory, p. 37).
The problem with (input) conventions is: If you don't follow them and put some extra figures on the inital tape the Turing machine works nevertheless and eventually yields some output, eventually different from the output without the extra figures.
What I wonder:
- Which role are such conventions supposed to play, and how?
Should we simply neglect non-conventional inputs (and just don't care how a Turing machine processes them)?
Should we simply neglect non-conventional Turing machines (that don't yield conventional outputs for all conventional inputs)?
Regardless of conventions:
- Is there really a conceptual problem with "input" and "output" of Turing machines?
- If not so: why not?
- If so: Where can I learn more about it?
Best Answer
I think that it is not a "real conceptual problem".
But if you want an unamboguous coding, you can see Wang coding, described in George Boolos & John Burgess & Richard Jeffrey, Computability and Logic (5th ed - 2007) : Ch.8.1 Coding Turing Computations, page 88-on.