The Gateway to Computer Science Excellence
+1 vote
69 views

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

in Theory of Computation by Active (1.7k points) | 69 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 Active (1.4k points)
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
50,644 questions
56,500 answers
195,544 comments
100,997 users