- Turing Machines for dummies: why representations do matter
- Lecture Notes in Computer Science
- Pages (from-to)
- Document type
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
Various methods exists in the litearture for denoting the configuration of a Turing Machine. A key difference is whether the head position is indicated by some integer (mathematical representation) or is specified by writing the machine state next to the scanned tape symbol (intrinsic representation).
From a mathematical perspective this will make no difference. However, since Turing Machines are primarily used for proving undecidability and/or hardness results these representations do matter. Based on a number of applications we show that the intrinsic representation should be preferred.
- go to publisher's site
- Proceedings title: SOFSEM 2012: Theory and Practice of Computer Science: 38th Conference on Current Trends in Theory and Practice
of Computer Science, Špindleruv Mlýn, Czech Republic, January 21-27, 2012: proceedings
Place of publication: Berlin
Editors: M. Bieliková, G. Friedrich, G. Gottlob, S. Katzenbeisser, G. Turán
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.