902 views
0 votes
0 votes
Which of the following statements is/are TRUE?
S1: Suppose L is Turing recognizable but not Turing decidable. Then any Turing machine that recognizes L must fail to halt on an infinite number of strings.
S2: The language A'TM={⟨M,w⟩ | M does not accept w} is Turing recognizable.

1 Answer

1 votes
1 votes

S1 : If a language is turing recognizable, then it must either say "YES" and loop forever instead of saying "NO" and vice versa. A TM can fail to halt iff input is infinite, if it is finite then utilmately it will stop and the language will become turing decidable and not turing recognizable(as TM will say "YES" when it accepts the lang and eventually it will say "NO" when it reaches the end of the string ). If the input is finite there is no scope for looping  forever. So S1 is true.

S2 : TMs that doesnot accept w, so the machine accepts w, we can rightway say "NO" and halt  and if it doen't accept w and goes to some dead state, then we can rightway say that "YES" TM doesn't accept w. So , this is turing decidable. So, S2 is False

Related questions

2 votes
2 votes
1 answer
2
ankit_thawal asked Jan 18, 2018
480 views
#include<stdio.h>void main(){printf("Hello\b\b\b\b\b");printf("Hi!\b\b\bBye");}