456 views
1 1 vote

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

1 Answer

1 1 vote

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
Position:
Show:

Related questions

3 3 votes
1 1 answer
292
292 views
Rakesh_Srikanth asked Dec 2, 2025
292 views
ANSWER IS 5. Option D.But Don't Know How To Solve It.
0 0 votes
0 0 answers
353
353 views
Aditya_Singh 1 asked Dec 4, 2024
353 views
how to make turing machine for 1^n0^n1^n
0 0 votes
0 0 answers
190
190 views
dispatch asked Dec 1, 2024
190 views
Create a transducer turing machine that computes this function: