The Gateway to Computer Science Excellence
+1 vote
141 views
Given a TM, M accepts 100 strings. Is it decidable, semi decidable or fully undecidable??
in Theory of Computation by Junior (939 points) | 141 views
+1
Semi-decidable
0
please explain
0
@vegeta

its semi decidable becz you can say YES and stop your algo when you reach 100 strings..but for saying NO you dont have any definite algo you cant say when machine will stop there may be case in hope that machine will accept more string you will be continously giving strings and may hope that this may get accept if not than you will give another and this process goes on and on...there may be times when machine could fall in a loop..and in hope that will accept you are waiting indefinitely..so for saying NO ,you dont have any algo..so its Semi decidable..!
0
thnk u, what if it would be M accepts exactly 100 strings- it should be totally undecidable, am i correct?
0
@Vegeta Yes.
0
Why..M accepts exactly 100 strings is undecidable, not even semi decidable??

1 Answer

0 votes

What if the problem is like,

Given a TM, M accepts a set of 100 strings.

Is it decidable, semidecidable or partially decidable??

by (191 points)

Related questions

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,833 questions
57,709 answers
199,416 comments
107,605 users