+1 vote
319 views

12. ### A turing machine visits a particular state "q" atleast k times on input "x"

0
1. D

2. D

3. UD

4. D

5. D

6,7,8,9,10,11,12 : UD
0

Deepakk Poonia (Dee)  3 is UD because we don't know whether the TM after running for k steps will actually halt or not in the future?

And for 1 and 2..we don't have to check for all the inputs right? Can you please share your approach for all the statements? I face problems in these..one of the ways that i have seen is separating all the strings of length=k and run them on TM. If all of them take exactly k steps then we can say that other strings(length>k) having their substrings in the 1st partition will also take exactly k steps.. if this is so i have doubts...

+1

### 2. A turing machine halts after running for atmost k steps

4. A turing machine accepts a string "x" after running for exactly k steps

### 5. A turing machine accepts a string "x" after running for atmost k steps

These are informal statements. So, before answering them, let me make them formal as they should have been asked.

$L=$ $\left \{ ⟨M⟩|M\,\, is\,\, a\,\, TM\,\, which\,\, halts\,\, for\,\, every\,\, input \,\,in\,\, at\,\, most \,\,K \,\,steps \,\,for\,\, some\,\, K \geq 1 \right \}$

It is Decidable. Because  if the machine $M$ halts after at most $K$ steps, then only the cells $0,1,…,K−1$ on the tape are significant. Then it suffices to simulate the machine $M$ on all input strings of the form $x∈Σ^K$, of which there are a finite number.

• If any of these simulations fail to enter a halting state by the $K^{th}$ transition, this indicates that any input string starting with $x$ is one for which the machine does not stop within the first $K$ steps.
• If all of these simulations halt by the $K^{th}$ transition, then $M$ halts within $K$ steps on all inputs of any length (of which the substring of length $K$ is all that it ever acts on).

NOTE that similar logic can be applied for any of the following combinations :

$\left \{ For \,\,all\,\, strings, For \,\,some \,\,string, for\,\, no \,\,string, \,\,for\,\, the\,\, given\,\, string \right \} \times \left \{ at\,\, most\,\, K\,\, steps, exactly \,\,K\,\, steps, exactly\,\, after\,\, K\,\, steps \right \}$

Every such pair will be Decidable by the similar logic as above explained.

### 6. A turing machine accepts a string "x" after running for atleast k steps

It is Undecidable as We can easily see that If it were Decidable then Halting Problem would also be Decidable. Put $K = 1$ and this problem is nothing but the standard Halting Problem of TM.

We know that "whether or not a Turing machine will reach the Halt state for some initial tape" is known as the Halting Problem. i.e.  It asks, "given a computer program and an input, will the program terminate or will it run forever? " is halting Problem and It is Undecidable.

For Problem statements $7 \,\,to\,\,12$, First let's see the following Problem :

$L =$ {$⟨M,q,x⟩| M\,\, is\,\, a\,\, Turing\,\, machine\,\, and \,\,q \,\,is\,\, a\,\, particular \,\,state\,\, of\,\, M\,\, and \,\,running\,\, of\,\, M\,\, on\,\, w\,\, visits\,\, q$}

Moreover, It is one of the Standard Undecidable Problems and also known as State Entry Problem. It is Undecidable Because if you can decide if $⟨M,q,x⟩$ is in your language, then you can decide if the machine $M$ stops on input $x$, by testing if $⟨M,h,x⟩$ is in your language ($h$ is the halting state). So you can decide the halting problem. And this problem is undecidable, so is the language $L$.

Problem Statements $7 \,\,to\,\,12$ are all Undecidable as we can see. Just Put $K = 1$ and all those statements will become State Entry Problem Statements.

answered ago by Boss (16.6k points)
edited ago
0

If all of these simulations halt by the Kth transition, then M halts within K steps on all inputs of any length (of which the substring of length K is all that it ever acts on).

I have some doubts.. suppose there is a TM which is made to accept strings on {a,b} of all length up to 4. Now let's take k=2.

So when we run strings {Epsilon,a,b,aa,ab,ba,bb} on TM, it halts(accepts the strings) after at most 2 steps (after getting the blank symbol at the end). Now we conclude that all strings of length>2 having substrings as mentioned above will also take 2 steps to halt.

Won't strings of length=3 or 4 take more than 2 steps to halt? But without running them on TM we say that they would also take at most 2 steps as they have their substrings present there in {Epsilon,a,b,aa,ab,ba,bb} .

That means the TM will halt in at most 2 steps on strings like {aaaaa,aababa..} also which are of length>4 as they have substring "aa". But these are the invalid strings for this TM.