M is a Determinstic TM with one tape, c2 is c1 reachable, if it's reachable within finite positive time

Question

$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.

Answer 1

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.