3
$\begingroup$

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?
  1. Should we simply neglect non-conventional inputs (and just don't care how a Turing machine processes them)?

  2. 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?
$\endgroup$
  • $\begingroup$ "Making a difference" is conceptually not good, since then there is no obvious way to determine whether two inputs are "the same." $\endgroup$ – André Nicolas Sep 30 '14 at 14:02
  • $\begingroup$ That depends on what the two inputs are. $\endgroup$ – Hans-Peter Stricker Sep 30 '14 at 14:19
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1 for the hint to Wang coding. (Could you explain, why you think that it's not a real problem.) $\endgroup$ – Hans-Peter Stricker Sep 30 '14 at 15:54
  • 1
    $\begingroup$ @HansStricker - If I understood well your concern, the issue is that different "not-formal" definition of input/output leave room to an "human interpretation", that is "conceptually" unsatisfactory in this context. But we have way to "standardize" the definition (see Kleene, Davis, Hermes textbooks). $\endgroup$ – Mauro ALLEGRANZA Sep 30 '14 at 16:10
  • $\begingroup$ I believe to know which textbooks you mean with Kleene's and Davis', but which one do yo mean with Hermes'? $\endgroup$ – Hans-Peter Stricker Sep 30 '14 at 17:00
  • $\begingroup$ @HansStricker - Hans Hermes, Enumerability, decidability, computability (German ed - 1961) - I've read the Italian translation. $\endgroup$ – Mauro ALLEGRANZA Sep 30 '14 at 19:16
1
$\begingroup$

You can also check C.Papadimitriou, Computational Complexity where Turing Machines are defined unambiguously, in my opinion.

What do you mean by "real conceptual problem'? I don't get it. But since Turing Machines can solve any, solvable problem I'll say there is.

Turing Machines (TM) are used in nowdays literature as theoretical computational model to measure a problem's complexity and requirements in time or space. Don't expect to see one in front of you. Except maybe here. So, we do not elaborate much on the details of a TM. Usually a TM has one separate input, one output tape and several working tapes. The robustness of a TM is based on that one working tape can simulate finite many tapes in polynomial time.

After similar other theorems can be proven you realize that the details of a TM do not matter. For example, given a SAT formula written in the input tape then the instance if the formula is your input. Nothing to do with the entire initial tape or visited cells or anything. Is just the formula. Maybe, the SAT formula converted to binary, but that's all.

The side of the head, the number of the states and any other information has nothing to do with what your size of the input is.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.