search

OpenLogicProject / OpenLogic

An open-source, customizable intermediate logic textbook
http://openlogicproject.org/
Creative Commons Attribution 4.0 International
1.06k stars 240 forks source link

Turing machine continuity w/ other definitions #221

Open BassP97 opened 4 years ago

BassP97 commented 4 years ago

Hi all! Sipser (and other TOC sources) use a 7-tuple definition of a turing machine:

  1. Start State
  2. Reject State
  3. Accept state
  4. Transition function
  5. Tape Alphabet
  6. Input alphabet
  7. Set of states

The open logic chapter on computation, in contrast, uses a 4-tuple definition. Is there a reason for this (maybe a difference in philosophy/computer science's respective disciplinary norms?) or should I (or someone else) rewrite the definition using the more conventional 7-tuple?

rzach commented 4 years ago

There is no single universally accepted definition. Eg, the OLP definition uses a one-sided tape and a tape-end marker, and allows the tape head to not move (so it is like the definition in Papadimitriou's Complexity Theory, for instance). Since the OLP (as of yet, in any case) has no content that would require separate input and tape alphabets, or a baked-in requirement that every machine has an accept and a reject state, I don't think that's necessary or useful. The sections comparing definitions could be expanded though. Let's keep the simpler definition for now, I'd say.