The Gateway to Computer Science Excellence
+1 vote
75 views

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

in Theory of Computation by | 75 views

1 Answer

+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

by
edited by
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
52,345 questions
60,481 answers
201,803 comments
95,280 users