Acceptable notation.
Stewart Shapiro · Notre Dame Journal of Formal Logic · 1982
Mechanical devices engaged in computation and humans following algorithms 1 do not encounter numbers themselves, but rather physical objects such as ink marks on paper.Since strings are the relevant abstract forms of these physical objects, algorithms should be understood as procedures for the manipulation of strings, not numbers.Furthermore, mathematical automata, such as Turing machines, which are the abstract forms of computation devices, have only appropriately constituted strings for inputs and outputs.It follows that, strictly speaking, computability applies only to string-theoretic functions and not to number-theoretic functions.That is, a string-theoretic function is said to be computable iff there is an algorithm that computes it.Throughout the literature, however, computability is said to apply to number-theoretic functions through notation.A notation d consists of a finite alphabet, a solvable class of strings on this alphabet, called the class of numerals, and a convention which assigns to each numeral x a natural number dx, called the denotation of x.The following are common notations: El.Stroke notation: The alphabet consists of a single character I, called a "stroke".The class of numerals is the entire class of strings on this alphabet, including the null string.That is, a numeral in stroke notation is a finite sequence of strokes.A given numeral is taken to denote the number of strokes it contains.In what follows, for each natural number n, let n be the stroke numeral for n.E2. Arabic_ notation^ The_ alphabet consists of the following ten characters: <0, T, 2, 3, 4, 5, 6, 7, 8, 9).The class of numerals consists of the ten single character strings, together with all multiple character strings which do not *I would like to thank an anonymous referee and the members of the Buffalo Logic Colloquium for helpful comments on earlier versions of this paper.