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.
$\begingroup$
$\endgroup$
1
asked Nov 25, 2016 at 17:42
-
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$– PartialOrderCommented Nov 25, 2016 at 21:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
answered Dec 2, 2018 at 6:32