patternMinor
Given a TM $T$ does $T$ ever leave the initial state when start tape is blank?
Viewed 0 times
theleavestartblanktapestatedoesinitialwhenever
Problem
I want to determine whether this decision problem is decidable. I have tried to establish reductions from Halt and "Accepts empty-string", but I've not yet found a solution.
Can someone help me out?
Can someone help me out?
Solution
I would say it is decidable.
If I understood correctly, here's what I think.
First of all a TM starts from some initial state $s_0$. How can it change the state? In your transition function you have something like $(s_0, x) \to (s_i, y, m)$ where $s_i$ is a state and $x$, $y$ are symbols and $m$ is the head move (left right or stay). So, if it leaves the initial state there should be a transition from $(s_0, \_)$ to some state not $s_0$. Easy to see that it is if and only if. Thus, you can construct another Turing machine which has the input as a TM in some encoding, goes through the transition function and checks the condition above, and the problem is decidable.
If I understood correctly, here's what I think.
First of all a TM starts from some initial state $s_0$. How can it change the state? In your transition function you have something like $(s_0, x) \to (s_i, y, m)$ where $s_i$ is a state and $x$, $y$ are symbols and $m$ is the head move (left right or stay). So, if it leaves the initial state there should be a transition from $(s_0, \_)$ to some state not $s_0$. Easy to see that it is if and only if. Thus, you can construct another Turing machine which has the input as a TM in some encoding, goes through the transition function and checks the condition above, and the problem is decidable.
Context
StackExchange Computer Science Q#47118, answer score: 4
Revisions (0)
No revisions yet.