<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-09-22T22:41:38.603Z
Thanks a lot! I just wanted to know how people feel about this. I'll do as you say. No paper though, only curiosity ;)
stsampas
CC BY-SA 3.0
2014-09-22T22:05:44.660Z
2014-09-22T22:05:44.660Z
Jeffrey Shallit
<p>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.</p>

<p>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$".</p>

<p>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.</p>

<computability><turing-machines>
Conflicting definitions regarding TM and Recursively Enumerable languages
stsampas
# Conflicting definitions regarding TM and Recursively Enumerable languages

(Asked by: username_0 on 2014-09-22)

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.

**Tags:** computability, turing-machines

---

## 1 answers

### Answer by username_1 on 2014-09-22. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks a lot! I just wanted to know how people feel about this. I'll do as you say. No paper though, only curiosity ;)  

---

