The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
654 views

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 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) 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).

posted Sep 14 in Theory of Computation by Active (2,237 points)
edited Sep 18 by | 654 views
2
Like
0
Love
0
Haha
0
Wow
2
Angry
0
Sad

12 Comments

@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?
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

40,813 questions
47,492 answers
145,722 comments
62,251 users