242 views
1 votes
1 votes

can someone please help to elaborate the given ans for this que?

1 Answer

1 votes
1 votes

First problem is checking finiteness of language. which is undecidable as no turing machine can tell whether another turing machine will accept only a finite number of inputs.

However second is semi decidable. What we can do is take a turing machine and run all the possible inputs one by one on this machine. Any time when this machine accepts more than two inputs, Accept it. those inputs which are not part of the language might be rejected or might loop infinitely. Thus its not recursive but certainly its turing recognizable.

http://stanford.edu/~jbooher/expos/computability_promys.pdf

edited by

Related questions

0 votes
0 votes
0 answers
1
RahulVerma3 asked Apr 2
48 views
Is this the correct Turing machine for the language $0^n 1^n0^n$?assuming $ at the end and begining of the input tape
3 votes
3 votes
2 answers
4