1
$\begingroup$

Since every deterministic Turing Machine can be translated to a graph of configurations such that $M$ accepts a word $w$ iff there is a path from the initial configuration that matches $w$ to an accept configuration, we can define a decider $D$ for $L$ such that:

$D$ verifies $\langle M \rangle$ is a (deterministic) TM and then builds the configurations graph and checks if the initial configuration of $\epsilon$ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't.

Though this seems simple and valid (to me), there is a well-known result showing that $L$ is undecidable. I can't figure out what is the flaw in the proof and will be happy for any help to figure it out

$\endgroup$
  • 1
    $\begingroup$ How long does it take to build the graph? What if $M$ runs forever, how long will it take to build the graph? $\endgroup$ – Andrej Bauer Nov 27 '19 at 16:58
2
$\begingroup$

$D$ verifies $\langle M \rangle$ is a (deterministic) TM and then builds the configurations graph and checks if the initial configuration of $\epsilon$ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't.

The problem here is that, even if you define the TM so that there are only finitely many accepting configurations (e.g. by requiring that the final tape be empty), the configuration graph itself may have infinitely many vertices. This is because the configuration includes the contents of the tape, and the tape contains however many cells the TM has written to, which is in general unbounded.

Every vertex can be identified by a finite string (the configuration description), and each vertex is connected to only a finite number of other vertices (determined by the transition relation), so the graph is locally finite. But the whole graph may still have an infinite number of vertices that are reachable.

$\endgroup$
0
$\begingroup$

then builds the configurations graph and checks if the initial configuration of ϵ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't.

The above is just another way of saying: run $M$ on $\epsilon$ and wait to see if the machine halts or not. This, hovewer, is not deciding the language $L$.

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