DECIDABILITY

Question

PLEASE CHECK MY UNDERSTANDING:-

1. Halting Problem:-
a) A turing machine halts after running for exactly k steps on any input
This is DECIDABLE, as the number of steps are finite and we can test it by giving a string whose length is 'k' as input.

b) A turing machine halts after running for atmost k steps on any input
This is DECIDABLE, as the number of steps are finite and we can test it by giving a string whose length is 'k' as input.

c) A turing machine halts after running for atleast k steps on any input
This is SEMI-DECIDABLE, as we can construct a Turing Machine for this problem and it can loop forever.

2. State Entry Problem:-
a) A turing machine visits a particular state "q" exactly k times on any input
We can simulate this problem using Bi-tape or Bi-Track Turing Machine. 1 tape/track can be used to simulate the given turing machine specification and the next track/tape can be used as a counter. We increment the counter whenever we come across that state. But there is chance for looping as that particular state can be visited after very large number of steps. So, this is SEMI-DECIDABLE.

b) A turing machine visits a particular state "q" atmost k times on any input
SEMI-DECIDABLE(Same as above)

c) A turing machine visits a particular state "q" atleast k times on any input
SEMI-DECIDABLE(Same as above)

d) A turing machine visits a particular state "q" after exactly k steps on any input
Number of Steps are finite. So, DECIDABLE.

e) A turing machine visits a particular state "q" after atmost k steps on any inpur
Again, Number of Steps are finite. So, DECIDABLE.

f) A turing machine visits a particular state "q" after atleast k steps on any input
It may visit "q" after a very large number of steps. So, looping possible. Though we can construct a Turing Machine for this. Hence, SEMI-DECIDABLE.

g) A turing machine visits exactly n states on any input
There can be many redundant states and the turing machine might visit only some states for a particular input. For all inputs, it is kinda difficult to decide as we might have to run the turing machine for all possible inputs from the Alphabet set. Though we can simulate the problem statement using a Bi-tape or Bi-Track Turing Machine where the 2nd tape/track acts as the counter. Hence, SEMI-DECIDABLE.

h) A turing machine visits atmost n states on any input
SEMI-DECIDABLE(Same as Above).

i) A turing machine visits atleast n states on any input
SEMI-DECIDABLE(Same as Above).

3. Acceptance Problem:-
a) A turing machine accepts strings of length exactly "n" 
Basically, Halting Problem reduces to this. Hence, SEMI-DECIDABLE.

b) A turing machine accepts strings of length atmost "n" 
SEMI-DECIDABLE(Same as Above).

c) A turing machine accepts strings of length atleast "n" 
SEMI-DECIDABLE(Same as Above).

4. PROBLEM RELATED TO CONTROL OF TURING MACHINE:-
a) The control of a turing machine moves right exactly n times on any input
If it was 1 time, we can easily decide. Also if it was for 1 particular string, we can decide. But for all strings in the Language, it is kinda difficult to decide as we might have to run the turing machine for all possible inputs from the Alphabet set. Though we can simulate the problem statement using a Bi-tape or Bi-Track Turing Machine where the 2nd tape/track acts as the counter. Hence, SEMI-DECIDABLE.

b) The control of a turing machine moves right atmost n times on any input
SEMI-DECIDABLE(same as above).

c) The control of a turing machine moves right atleast n times on any input
SEMI-DECIDABLE(same as above).

5. PROBLEM RELATED TO REPLACEMENT OF CHARACTER IN TURING MACHINE:-
a) A turing machine replaces the characters on the tape exactly n times on any input 
If it was for 1 particular string, we can decide. But for all strings in the Language, it is kinda difficult to decide as we might have to run the turing machine for all possible inputs from the Alphabet set. Though we can simulate the problem statement using a Bi-tape or Bi-Track Turing Machine where the 2nd tape/track acts as the counter. Hence, SEMI-DECIDABLE.

b) A turing machine replaces the characters on the tape atleast n times on any input
SEMI-DECIDABLE(same as above).

c) A turing machine replaces the characters on the tape atmost n times on any input
SEMI-DECIDABLE(same as above).

Comments

I think 1 c) can be DECIDABLE as we can construct a Turing Machine in such a way that it will halt after k steps.

---

Its Semi Decidable because its atleast(means lower bound)..

The TM might halt after kth or K+1th or K+2th iteration ....

We don't know when it halts 

---

1,2,4,5 are totally decidable

---

But State Entry Problem can be reduced to Halting Problem, so how can 2 be Decidable?

---

srestha according to you nothing is partially decidable here?

---

@Balaji

How it will be state entry prolem? What is input here?

@Utkarsh

3 will be :)

---

@srestha 

In this answer it is mentioned that 1 c) is Undecidable

https://gateoverflow.in/225421/decidability-semi-decidability-undecidability-self-doubt?show=225628#a225628

---

@Balaji

https://www.seas.upenn.edu/~cit596/notes/dave/halting6.html

this is state entry problem which has a input w

And also yes state entry problem and halting problem both undecidable

but in ur question, where is any input?

---

srestha I edited the problem statement. Now can u check.

---

2.f) and g) I also think decidable

---

4.a) will be Recursive Enumerable

Because  it is same as "String accepts something"

---

@Balaji

1.c) is undecidable, r u sure about it?

---

we don't know when it will halt, so isn't it semi-decidable srestha ?

---

UPDATE :-

L(M1)= { w | w = {1010}} This is Decidable(FINITE LANGUAGE)

L1= {<M> | M is a TM accepting string 1010} This is Undecidable.

---

@balaeinstein