0
$\begingroup$

This question already has an answer here:

I'm currently working on a few turing machine exercises and I can't understand how I can prove whether the below is at least partially decidable:

$\{M \mid L(M) = \{x \mid |x| = 10\}\;\}$ where $|x|$ is the length of word $x$

Can anyone explain to me what the above statement actually means and an idea of how to go about it please?

$\endgroup$

marked as duplicate by Raphael Nov 4 '17 at 20:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ This statement means the set of TM indexes (natural numbers under some fixed encoding) where each TM accepts a language containing all strings of length $10$. $\endgroup$ – fade2black Nov 3 '17 at 19:31
  • $\begingroup$ Usually, positive answers are justified by crafting a semidecider. Negative answers often are justified by Rice-Shapiro (if your course cover that) or explicit reduction from some known non-semidecidable problem (e.g. the complement of the halting problem). $\endgroup$ – chi Nov 3 '17 at 21:16
  • $\begingroup$ Another way to explain it, "$\{x \mid |x| = 10\}$ is the (finite) set of strings of length $10$. $L(M)$ represents the language accepted by $M$. $A = \{ M \mid ...\mbox{ someproperty }... \}$ represents the set of Turing machines that satisfy "someproperty". Your question is: given a Turing machine $M$ does there exist an algorithm that is able to halt if $M$ accepts exactly the strings of length $10$ and rejects all the strings longer or shorter than $10$? If yes then $A$ is partially decidable. $\endgroup$ – Vor Nov 4 '17 at 20:08
  • $\begingroup$ Thank you to all of you, particularly @Vor as the notation was confusing me. I am now assuming that this is provable using the halting problem. $\endgroup$ – Ponsietta Nov 4 '17 at 21:02
  • $\begingroup$ @Ponsietta: or you can directly apply the Rice theorem (if you already studied it) $\endgroup$ – Vor Nov 4 '17 at 23:10