Finding regular expressions for which a given Turing machine halts and accepts, halts and rejects, and diverges.

Question

Consider the Turing machine M = (Q,Σ,Γ,δ,q,F)

F = {t} Q = {q,r,s,t,v,x} Σ = {a,b,c} Γ = {B,a,b,c}

δ = [q,a,q,a,R] [q,b,q,b,R] [q,c,v,b,R] [q,B,r,B,L]

[r,a,s,B,L] [r,b,s,B,L] [r,c,s,B,L]

[s,a,x,a,L] [s,b,t,b,L] [s,c,x,c,L]

[v,B,v,B,R] [v,a,v,B,R] [v,b,v,B,R] [v,c,v,B,R]

can you guys give me some general pointers to finding where this machine halts and accepts, halts and rejects, and diverges.

for acceptance I have (a u b)* (a u b)b(a u b) the rest I have trouble generating.

Answer 1

I think for acceptance the expression is $(a\cup b)^*b(a\cup b)$. You don't need to read something before the last $b$ but one. (for example $ba$ is accepted by your machine).

For the halting and reject notice that you cannot halt in $q$ nor in $v$ since you can read anything from there. Hence the only possibility to halt and reject are:

1. be in $r$ and read a $B$
2. be in $s$ and read a $B$
3. be in $x$.

The expression for the last case is quite similar to the acceptance expression. And the two first cases are quite easy.

For the divergence notice that once you reach $r$ the run are always finite, hence the only way to diverge is to stay in $q$ or to go to $v$ since from $v$ you can read anything and always stay in $v$.

I don't know if you allow infinite word, if you do the expression to stay in q is $(a\cup b)^\omega$. Otherwise I let you find the expression to reach $v$.

If something is not clear please ask.