Information Technology Reference
In-Depth Information
Chapter Notes
Alan Turing introduced the Turing machine, gave an example of a universal machine and
demonstrated the unsolvability of the halting problem in [
338
]. A similar model was inde-
pendently developed by Post [
255
]. Chomsky [69] demonstrated the equivalence of phrase-
structure languages. Rice's theorem is presented in [
280
].
Church gave a formal model of computation in [
72
]. The equivalence between the partial
recursive functions and the Turing computable functions was shown by Kleene [
168
].
For a more extensive introduction to Turing machines, see the topics by Hopcroft and
Ullman [
141
] and Lewis and Papadimitriou [
200
].
Search WWH ::
Custom Search