[Solved]: Minimizing Turing machine-like automaton with no final states

Problem Detail: 

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.

Asked By : Matěj Zábský

Answered By : Shaull

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10175