1
$\begingroup$

$M=(Q,\sum,\Gamma, \delta, q_{0}, q_{accept}, q_{reject})$ is a TM with one tape. let $c_{1}, c_{2}$ be two configurations of $M$.

A configuration is defined like this:

$uqv$ where $(q\in Q; u,v\in \Gamma^{*} )$

we say that $c_{1}$ is reachable from $c_{2}$ in $M$, if when $M$ is in configuration $c_{1}$ it can reach the configuration $c_{2}$ in a finite number of steps that is greater than 0.

Is the following language TR (Turing Recognizable), is it Decidable?

$L=\{\langle M, c \rangle \mid M\text{ is a TM; configuration }c\text{ is reachable from configuration }c\text{ in }M\}$?

I know that the answer to this is no, $L$ is not Decidable. I just fail to see the logic behind that.

See I thought $L$ is Decidable because of the following justification:

$L$ is decided by the structure of $M$ it's self with no regards to whatever language $M$ accepts so it is intuitive.

Let's run $M$ non diterministically on any letter of it's alphabet until we get to cofiguration $d\ne c$ then again to reach another config. and so on until we get to configuration $c$ it's self after a threshold number of steps, let's say $N^{q}$ number of steps, where $N$ is the number of configurations in $M$ and $q$ is the number of letters in alphabet.

Kindly explain why language $L$ is TR and not Decidable.

Thank you in advance.

$\endgroup$
  • 1
    $\begingroup$ $c$ already contains the input, so what you describe does not make sense. You can only "run $M$ on $c$" until $M$ reaches again the $c$ configuration, stop and accept in that case. However at a first glance it looks like TR. You just run $M$ on $c$, if it ever ends up going back to $c$ you halt and accept otherwise if $M$ halts you go into an infinite loop and if $M$ does not halt you do not halt too. In otherwords you end up with a machine that halts and accepts iff $<M, c> \in L$ and otherwise does not halt hence $L$ is TR (but not decidable). But it's been a while for me... $\endgroup$ – Giacomo Alzetta Aug 24 '18 at 13:18
  • $\begingroup$ You know what, it's my bad I do think the language is TR but not decidable! $\endgroup$ – Anwar Saiah Aug 24 '18 at 16:21
0
$\begingroup$

Since no answer has been posted I will attempt the answer my self: Since Giacomo explained why $L$ is TR(I thank him for that) I won't talk about it.

I will prove $L$ is not decidable:

We do that by building a machine $K$ that will decide the halting problem $L_{1}$ using $G$ the decider of $L$ that we assume exists.

$L_{1}$={< $R$, $w$ > | $R$ is a TM; $w \in \Sigma^{*} $; $R$ halts on $w$ }

Description of $K$:

Build TR $H$ that has a configuration $c$ as follows:

  • "Configuration $c$": On input <$R$, $w$ > if $R$ halts on $w$ go to configuration $d$ which on any input goes back to configuration $c$.

  • else go to configuration $e$ and loop forever.

Run $G$ on input <$H$,$c$ > if $G$ accepts, accept else reject.(if $H$ accepts $K$ accepts and vice-versa)

Giving < $R$,$w$> to $K$ as input, $K$ will decide if $R$ halts on $w$ if and only if (iff) $G$ decides if $c$ is reachable from $c$ in $H$.

But we know that the halting problem is not decidable in contradiction to what we have assumed in the first place, so $G$ cannot exist there for $L$ is not decidable.

$\endgroup$

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.