The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
126 views
Given a TM, M accepts 100 strings. Is it decidable, semi decidable or fully undecidable??
in Theory of Computation by Junior (811 points) | 126 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 (145 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
49,823 questions
54,821 answers
189,571 comments
81,052 users