Màquina que sempre s'atura

En teoria de complexitat, una màquina que sempre s'atura - també coneguda com a decider o màquina de Turing total - és una màquina de Turing que s'atura per qualsevol entrada.^[1]

Com que sempre s'atura, la màquina és capaç de decidir si la cadena d'entrada pertany o no a un llenguatge formal. La classe de llenguatges formals que es poden decidir per una màquina d'aquest tipus és la dels llenguatges recursius. Tot i això, el problema de la parada, que és decidir si una màquina de Turing arbitrària s'atura per una entrada donada, és un problema indecidible.

A la pràctica, moltes de les funcions interessants son computables per una màquina que sempre s'atura. Una màquina que utilitza només una quantitat finita de memòria per una entrada particular es pot forçar a que s'aturi per cada entrada restringint el flux de control de manera que cap entrada forci la màquina a entrar dins un bucle infinit. Com a exemple trivial, una màquina que implementa un arbre de decisió finit sempre s'atura.

No es requereix que la màquina estigui lliure de bucles, però s'han de garantir que s'aturin. Es poden restringir totes les funcions recursives primitives a que facin ús de bucles a que siguin d'un nombre predictible de passos (com per exemple la construcció FOR en BASIC).^[2]

De fet, es pot definir un llenguatge de programació en que s'asseguri que funcions encara més complexes sempre s'aturin. Per exemple, la funció d'Ackermann, que no és primitiva recursiva, és una funció total computable per un sistema amb reescriptura amb una reducció ben ordenada dels seus arguments.

Una màquina de Turing general pot computar una funció parcial. Es poden plantejar dues qüestions sobre la interdependència entre les màquines de Turing parcials i les totals:

1. Es pot estendre una funció parcial computable per una màquina de Turing parcial fins a ser una funció total computable?
2. És possible canviar la definició d'una màquina de Turing de manera que es pugui trobar una classe particular de màquina de Turing que pot computar totes les funcions computables?

La resposta a totes dues preguntes és que no.

Es pot demostrar que les funcions computables per màquines que sempre s'aturen no inclou les extensions per totes les funcions parcials computables, el que implica que la primera qüestió té una resposta negativa. Aquest fet està fortament relacionat amb la irresolubilitat del problema de la parada.

La segona qüestió es pregunta si existeix un altre model de computació que computi només les funcions totals i les computi totes. Informalment, si aquest model existís llavors cada un dels seus computadors es podria simular amb una màquina de Turing. Per tant, si el nou model consisteix en una seqüència ${\displaystyle M_{1},M_{2},\ldots }$ de màquines, llavors hi hauria una seqüència de màquines de Turing enumerable recursivament ${\displaystyle T_{1},\ldots T_{2},\ldots }$que computen funcions totals de manera que cada funció computable és computa per un de les màquines ${\displaystyle T_{i}}$. Això no és possible, ja que es pot construir una màquina ${\displaystyle T}$ tal que per una entrada ${\displaystyle i}$la màquina ${\displaystyle T}$ retorna ${\displaystyle T_{i}(i)+1}$. Aquesta màquina no pot ser equivalent a cap màquina ${\displaystyle T}$ a la llista: si se suposa que és a la llista a l'índex ${\displaystyle j}$, llavors ${\displaystyle T_{j}(j)=T_{j}(j)+1}$que no retorna un valor enter. Per tant, no pot ser total, però la funció per construcció ha de ser total (perquè son enumerables recursivament), el que és una contradicció. Per tant, la resposta a la segona qüestió és no.

El problema de decisió de saber si la màquina amb índex e s'aturarà per tota entrada és no decidible. De fet, aquest problema està al nivell ${\displaystyle \Pi _{2}^{0}}$de la jerarquia aritmètica. Per tant, aquest problema és estrictament més difícil que el problema de la parada, que pregunta si la màquina amb índex e s'aturarà per l'entrada 0. Intuïtivament, la diferència és notable, ja que cada instància del problema de la màquina total representa un conjunt infinit d'instàncies del problema de la parada.