2
$\begingroup$

I want to figure out if the following language is Turing decidable, Turing acceptable but not turing decidable, or neither. The language is

{ρ(M) : |L(M)| ≤ 10}  

My question for this problem is what does |L(M)| ≤ 10 mean? At first, I thought it meant that the language will only accept strings that are less than or equal to 10 in length, but I am not sure

$\endgroup$
2
$\begingroup$

... what does $|L(M)| \leq 10$ mean?

This means that the size of the language accepted by the TM $M$ is less than or equal to $10$. In other words, TM $M$ accepts no more than $10$ strings (inputs), while the length of any accepted input may be greater than $10$.

$\endgroup$
  • $\begingroup$ Quick follow up to that: How does the size of the language play in a role in figuring out if a language is turing decidable or acceptable? $\endgroup$ – Zebs Nov 15 '17 at 1:12
  • $\begingroup$ By $\{\rho(M) : |L(M)| \leq 10\}$ you probably mean the set of TM $M$ indexes (under a fixed enumeration) such that $M$ accepts no more than $10$ strings. That is, this language consists of TM indexes, not the elements of $L$. $\endgroup$ – fade2black Nov 15 '17 at 1:17
  • $\begingroup$ @Zebs Roughly, 10 is an arbitrary value. Proving that there are at least 10 thing can be done by searching until you find 10, and is more likely to be acceptable (or even decidable, sometimes). Proving that there are at most 10 is harder, because you can't perform a finite amount of tests and claim that, in general -- it turn out often to be non-accpetable (or sometimes decidable, if the property is easy). $\endgroup$ – chi Nov 15 '17 at 12:59
-2
$\begingroup$

if the problem is knowing if a TM accepts (or recognices) less than 10 words, then it can be acceptable or decidible, coz to recognize only 10 or less words you need to test the entire language associated to the original alphabet and determinate the "non-recognotion" of almost all words...

so neither

respecting the question of the matter of the size of the accepted words in relation to the fact of being decidible or not... usually is easier to recognice have more than N words than less than N... because "more than" means you only need to find the first N words and finish. On the other side, "less than" means you need to check all words to be sure that there are only N words and no more(wich means infinite cases to check)

$\endgroup$
  • $\begingroup$ There are infinitely many strings over any alphabet so, no actually, you can't just test if every one of them is in the language. Indeed the undecidability of the halting problem means you can't even decide if one of them is in the language. $\endgroup$ – David Richerby Nov 15 '17 at 11:12
  • $\begingroup$ thats why i said it cant be decidible if you need to explore infinite options $\endgroup$ – sean guinovart Nov 16 '17 at 14:59
  • $\begingroup$ You wrote "then it can be acceptable or decidible". $\endgroup$ – David Richerby Nov 16 '17 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.