0
$\begingroup$

In Lewis's and Papadimitriou's book "Elements of the Theory of Computation" the transition table is a function $\delta: Q \setminus F \times \Gamma \rightarrow Q \times (\Gamma \cup \{L,R\})$. However, according to Wikipedia (and pretty much everywhere else) it's $\delta: Q \setminus F \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$. The difference is that in the first case you can't write and move at the same time.

In the same book, a language $L$ is recursively enumerable if there is a TM so that: $w \in L \iff$ the TM halts on $w$. Note that in this book the TM only has halting states. In wikipedia, halting states are actually also accepting states. I also came across TM definitions where there is a distinction between accepting and rejecting states. In these cases, the definition of a recursively enumerable language changes to "... the TM accepts $w$".

Now it's obvious that in both cases all definitions are obviously perfectly equivalent. I'd like to know which defintions have prevailed so that I can follow those.

$\endgroup$
4
$\begingroup$

I wouldn't say that one definition has "prevailed". If you look at the literature and textbooks, you'll see a large variety of definitions.

Different definitions might be useful in different contexts. For example, if you're actually trying to program up a TM (for whatever reason) then the more expressive they are, the easier to program. On the other hand, if you're trying to prove a lower bound or uncomputability result, picking the weakest TM might make life easier. And the busy beaver function, for example, is usually defined relative to a fairly weak model.

I'd just recommend you use any model you feel comfortable with and tell the reader of your paper that is what you are using.

$\endgroup$
  • $\begingroup$ Thanks a lot! I just wanted to know how people feel about this. I'll do as you say. No paper though, only curiosity ;) $\endgroup$ – stsampas Sep 22 '14 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.