Turing Machines for dummies why representations do matter

Authors
Publication date 2012
Host editors
  • M. Bieliková
  • G. Friedrich
  • G. Gottlob
  • S. Katzenbeisser
  • G. Turán
Book title SOFSEM 2012: Theory and Practice of Computer Science
Book subtitle 38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012: proceedings
ISBN
  • 9783642276590
ISBN (electronic)
  • 9783642276606
Series Lecture Notes in Computer Science
Event 38th International Conference on Current Trends in Theory and Practice of Computer Science
Pages (from-to) 14-30
Publisher Heidelberg: Springer
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Abstract
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.
Document type Conference contribution
Language English
Published at https://doi.org/10.1007/978-3-642-27660-6_2
Permalink to this page
Back