6
$\begingroup$

In many formal definitions of Turing machines, the Greek letter $\Gamma$ is used to denote the tape alphabet of the TM.

What is the origin of using $\Gamma$ for this? I'm having a hard time imagining what this might stand for.

$\endgroup$
  • 2
    $\begingroup$ As far as I am aware, the earliest use of Γ representing a symbol alphabet is with regard to PDAs (stack alphabet). See Ginsburg & Greibach, 1966, Deterministic Context Free Languages. My guess is that it may have its origins in Chomsky & Schutzenberger, 1963, Algebraic Theory of Context Free Languages (dx.doi.org/10.1016/S0049-237X(08)72023-8) and that it made its way into usage for definitions of TMs from there. Why Γ and not, say T? I don't know, and alas, I don't have the Chomsky & Schutzenberger handy. I'd check there. $\endgroup$ – PartialOrder Nov 25 '16 at 21:45
1
$\begingroup$

Following up on @PartialOrder's comment, while $\Gamma$ is not used in Chomsky & Schutzenberger or in Chomsky's 1962/1963 papers on PDAs, it is used in Ginsburg and Greibach 1966 as follows:

A pushdown automaton (abbreviated pda) is a 7-tuple $M=(K,\Sigma,\Gamma, \delta, Z_0, q_0, F)$ where [...]

Here $K$ is the set of states and $q_0$ is the start state. $\Gamma$ is the finite nonempty set of auxiliary symbols. $F$ is the set of final states. $\Sigma$ is the finite nonempty set of inputs. Etc.

Nowadays we would call the set of states $Q$ if the start state is called $q_0$. I think this just indicates that not too much consistency and reason was required for these letter choices.

This is "original research" but I figure $\Gamma$ may just have been used since it is the first capital Greek letter (to indicate the same type as $\Sigma$) which looks distinctly greek (A and B looking Roman as well).

$\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.