0
$\begingroup$

We define a language $L$:

$\qquad L=\{\langle M,w,k \rangle \mid M(w) \text{ reaches configuration } \alpha q \beta \text{ with } |\alpha \beta| \geq k \}$

with $M$ Turing machines with state set $Q$ and tape alphabet $\Gamma$, $\alpha$ and $\beta \in \Gamma^*$ , and $q \in {Q}$.

A configuration like this : 10q11 or Bq11 are in standardform ,however those configurations BB10q11 or B10q11BB are not , in other words if $\alpha $ starts with many blanks then all the blanls will be one blank , same thing with $\beta$ when it ends with many blanks .

A configuration can be like this : configuration example

I am not sure if the language is decidable , but if i am able to find a machine which decides L then it must be decidable may main thoughts about the contruction of the machine like below:

Let D the machine that decided L

1-after each step check if the configuration $\alpha q\beta$, with $\mid \alpha\beta \mid \geq k$, if yes then accept else go further.

2-if until the i-step no configuration is found that satisfied the condition and D visted the same configuration twice ,which means it will go in a loop and then the condition won t be statisfied, then we will reject
The problem here which i am not really sure about ,for how long do we need to wait until the loop is discovered ?

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Nov 18 '17 at 17:21
  • $\begingroup$ Is $q$ arbitrary in the definition of $L$? $\endgroup$ – Raphael Nov 18 '17 at 23:55
  • $\begingroup$ There are many similar questions on the site: deciding whether $M$ ever moves the head to the right, ever writes a $0$, and so on and so on. All proofs are similar: deciding whether a TM does X is (usually) equivalent to deciding whether it holds, by similar and simple reductions. $\endgroup$ – Raphael Nov 18 '17 at 23:56
  • $\begingroup$ I think the answer to this question depends on where $\alpha,q,\beta$ are quantified. Is there an implicit quantification inside your set definition, or are these variables fixed outside of it? Anyway, you should make the problem statement to be non ambiguous. If I had to guess, I'd guess that there is an implicit $\exists \alpha,q,\beta$ inside. In such case, I'd try to check how many such configurations exist -- if it is a finite or cofinite set, this might be useful. $\endgroup$ – chi Nov 19 '17 at 8:58
  • $\begingroup$ the length of $\alpha$ and $\beta$ depends on how does the machine works , they are actually the symbol of the tape , on which the machine writes .let $q_0$ be the start state and w =1001 as input , and let s say when the machine start and it reads 1 , it writes 0 and go one step in the right and goes to state $q_i$ then it will be like that : $q_0$1001$ \rightarrow$ 0$q_i$001 $\endgroup$ – Mohbenay Nov 19 '17 at 9:18

Your Answer

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

Browse other questions tagged or ask your own question.