The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+4 votes
635 views

Please tell whether the following is Decidable, Semi-decidable or Undecidable

  1. A turing machine halts after running for exactly k steps

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

  3. A turing machine halts after running for atleast 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

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

  7. A turing machine visits a particular state "q" exactly k times

  8. A turing machine visits a particular state "q" atmost k times

  9. A turing machine visits a particular state "q" atleast k times

  10. A turing machine visits a particular state "q" exactly k times on input "x"

  11. A turing machine visits a particular state "q" atmost k times on input "x"

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

asked in Theory of Computation by Active (3.1k points) | 635 views
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...

Thanks in advance :)

+1
Check the complete answer.

1 Answer

+6 votes

      1. A turing machine halts after running for exactly k steps

      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.



3. A turing machine halts after running for atleast k steps

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 by Boss (19.5k points)
edited by
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.

This is troubling me since very long..please help.. 

0
As substrings of length k strings are accepted by Turing machine therefore all strings greater than length k as well as of almost length k would be accepted and more over  it is talking that Turing machine will halt within k steps I think those strings greater than length k would also be valid as they are accepted as TM halts because of substring concept
0
@Arjun Sir

Can u plz check it?

I think some error is there

Related questions

+2 votes
0 answers
2


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,575 questions
48,564 answers
155,453 comments
63,584 users