I have a deterministic finite automaton which behaves mostly like a Turing machine, with following difference (relevant to this question):

  • The tape is initially finite.
  • The automaton can insert and delete cells from the tape.
  • Actions are associated with states rather than with transitions (this includes head shift and tape manipulation).
  • The automaton has no accepting/final state. The computation is only terminated when the machine exits the tape. The final state of the tape is the machine's output.

I know most of the states in the machine are redudant (equivalent to other states). However the good old DFA minimization algorithm won't work here, because it starts its work on the final states (which I don't have).

The algorithm should be efficiently computable (the machines in question have hundreds of thousands to millions of states).

Is this possible in the general case? Every algorithm I make up fails in some cases.


1 Answer 1


What exactly is the difference between your machine and a TM? (apart from not having accepting states, which is quite meaningless since you have an output)

It sounds like this is a very powerful model, and its halting problem will be undecidable, let alone minimization.

EDIT: Minimizing TMs is undecidable (actually, not in $RE\cup coRE$). It is easy to reduce the universality problem to it: given a TM, if you could minimize it, then the minimal TM will consist of a single, accepting state iff its language is $\Sigma^*$.

  • $\begingroup$ I coulnd't find any information about minimization of Turing machines, so I don't know if that is decidable. Of course if Turing machine minimization is undecidable, this will be too (the lack of accepting states is the only real difference, as I outlined it in my post). I figured that the DFA minimization algorithm would work on regular TMs just fine. $\endgroup$ Mar 1, 2013 at 15:11
  • 1
    $\begingroup$ I edited the answer to include minimization undecidability. As for DFA minimization - it is crucial that the state space is finite. In TMs, there are infinitely many possible states (configurations), so minimization doesn't work. $\endgroup$
    – Shaull
    Mar 1, 2013 at 15:15
  • $\begingroup$ Thank you, I guess I will not be able to do it for the general case then. $\endgroup$ Mar 1, 2013 at 17:37
  • 3
    $\begingroup$ Damn computers... Can't do anything useful :) $\endgroup$
    – Shaull
    Mar 1, 2013 at 17:40
  • 1
    $\begingroup$ Yes, Rice's theorem tells you that ;) $\endgroup$
    – Dan
    Mar 1, 2013 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.