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

## Funcions compatibles amb les màquines de Turing totals

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 cal 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).
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.

## Relació amb màquina de Turing parcials

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:
* Es pot estendre una funció parcial computable per una màquina de Turing parcial fins a ser una funció total computable?
* É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 $M_{1},M_{2},\ldots$ de màquines, llavors hi hauria una seqüència de màquines de Turing enumerable recursivament $T_{1},\ldots T_{2},\ldots$que computen funcions totals de manera que cada funció computable és computa per un de les màquines $T_{i}$. Això no és possible, ja que es pot construir una màquina $T$ tal que per una entrada $i$la màquina $T$ retorna $T_{i}(i)+1$. Aquesta màquina no pot ser equivalent a cap màquina $T$ a la llista: si se suposa que és a la llista a l'índex $j$, llavors $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 conjunt d'índex de màquines de Turing totals

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

## Referències

* ↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.
* ↑ Meyer, Albert R.; Ritchie, Dennis M. «The Complexity of Loop Programs». Proceeding ACM '67 Proceedings of the 1967 22nd national conference. ACM [Nova York, NY, USA], 1967, pàg. 465–469. DOI: 10.1145/800196.806014.
Teoria d'autòmats: llenguatge formals i gramàtica formals :
Jerarquia de ChomskyGramàtiquesLlenguatgesMàquines abstractes
Tipus-0
Tipus-1
Tipus-2
Tipus-3
Sense restriccions
(sense nom)
Sensitiva al context
Concatenació de rang
Indexada
Sistema lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
No recursives
Enumerable recursivament
Decidible
Sensible al context
Concatenació de rang$^*$
Indexat$^*$
Llenguatge lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
Lliure d'estrella
Finit
Màquina de Turing
Decider
Linealment acotat
Màquina de Turing PTIME
Pila anidada
Autòmat per subprocessos
Autòmat amb pila d'arbre restringit
Pila incrustada
Autòmat amb pila no-determinista
Autòmat amb pila determinista
Visibly pushdown
Finit
Sense comptadors(amb monoides finits aperiòdics)
Finit acíclic :
Cada categoria de llenguatges, excepte aquells marcats per $^*$, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia. :