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

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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$.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Nov 15, 2017 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
    Commented Nov 15, 2017 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
    Commented Nov 15, 2017 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)

Improve this answer
$\endgroup$
3
  • $\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
    Commented Nov 15, 2017 at 11:12
  • $\begingroup$ thats why i said it cant be decidible if you need to explore infinite options $\endgroup$
    – sean guinovart
    Commented Nov 16, 2017 at 14:59
  • $\begingroup$ You wrote "then it can be acceptable or decidible". $\endgroup$
    – David Richerby
    Commented Nov 16, 2017 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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