[Solved]: Turing Decidable

Problem Detail: 

M = (Q, Σ, Γ, δ, q1, qaccept, qreject), where Q ={q1, q2, qaccept, qreject},  Σ = {0, 1},  Γ = {0, 1, U},  

and transition function δ is as follows:

δ (q1, U) = (q1, U, R) δ (q1, 0) = (q2, U, R) δ (q1, 1) = (q2, U, R) δ (q2, U) = (qaccept, U, R) δ (q2, 0) = (q1, U, R) δ (q2, 1) = (q1, U, R) 

is L Turing - decidable? From what I know, a language L is turing decidable if there is a turing machine M such that M decides L (M is a decider and L=L(M)).

What would be the language that M recognises? I am very new to Turing languages so not quite sure how to read the transition function. I know that a language is decidable if it halts (rejects or accepts) for every input string, but thats about it.

Asked By : Zambot

Answered By : Rick Decker

You're in luck here: since every transition of your TM moves the head right, the state of this machine will never depend on the previous contents of the tape. This means that your TM will act as if it were a finite automaton, basing its transitions only on the current input symbol. In other words, your TM is essentially equivalent to this FA:

It's easy enough to define the language accepted by this FA. It consists of all strings of the form:

• (an arbitrary number of U's) followed by (any even-length string of 0's and 1's),
• repeated an arbitrary number of times,
• ending with 0u or 1u.

As a regular expression, this language is denoted by $$ (U + 00 + 01 + 10 + 11)^*(0 + 1)U $$ Where $r + s$ represents the union of the sets denoted by the regular expressions $r$ and $s$. This, then, is the language, $L(M)$, of your original machine. Since the language is regular, it is certainly decidable, since a finite automaton will always eventually halt.

The question of whether your TM is a decider will depend on your local definition of what that means. Customarily, a TM is defined to be a decider if it eventually halts on every possible input. This machine will certainly do that, even though it will never enter $q_{\text{reject}}$, so under this definition your TM is indeed a decider. Be aware, though, that some authors require that a decider must eventually enter $q_{\text{accept}}$ or $q_{\text{reject}}$ and halt for any possible input, so under that definition, your TM wouldn't be a decider. Look at your notes to see which definition applies (from what you wrote, it seems to be the latter).

---

Another reasonable interpretation of this problem is that 'U' is intended to represent the blank character. Under this interpretation, the TM is definitely not a decider, since when given the empty string as input, namely when faced with a tape initially containing nothing but blanks, the TM will loop in state $q_1$ forever, thereby never halting. No matter which definition of a decider you choose, it's universally agreed that a decider must halt on all inputs, hence under this interpretation, the TM isn't a decider.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/25813

3.2K people like this

 Download Related Notes/Documents