⟸ pàgina anterior ⟸
Exercici 2 (Tasca 5).
(Turing machines)

Models equivalents de màquines de Turing

Un model de càlcul és Turing-complet si pot ser usat per computar qualsevol funció Turing-computable.

  1. Argumenteu que tota funció parcial computable amb una màquines de Turing amb k cintes pot ser computada per una màquina de Turing d’una cinta.
  2. Argumenteu que tota funció computable en una màquina de Turing indeterminista pot ser computada per una màquina de Turing determinista.
  3. Considereu la variació següent dels PDAs: un que té dues piles en lloc de només una. Aleshores, les transicions depenen de l’estat actual i del símbol del cim de cada pila. A cada pas, l’autòmat pot eliminar el cim de cada pila o empilar nous símbols en cadascuna. Una màquina com aquesta es pot utilitzar per computar funcions: a l’inici de la computació, una de les piles conté l’entrada; al final, la sortida és en una de les piles. Argumenteu que tota funció Turing-computable és computable amb aquesta versió de dues piles dels PDAs.
  4. Considereu la variació següent dels PDAs: un que té una cua en lloc d’una pila. Les transicions depenen de l’estat actual i del primer element de la cua. A cada pas, el primer element de la cua es pot esborrar i es poden encuar nous elements al final. Una màquina com aquesta es pot utilitzar per computar funcions: a l’inici de la computació, la cua conté l’entrada; al final, la sortida és a la cua. Argumenteu que tota funció Turing-computable és computable amb aquesta versió de cua dels PDAs.
Consell

Per mostrar que un cert model de càlcul és Turing-complet, n’hi ha prou a descriure la simulació del comportament d’una màquina de Turing. Per aquest exercici, no cal donar una descripció gaire detallada de les simulacions. Només la idea general és suficient.

Funcions computables

Recordeu que una funció parcial f : \mathbb N^k \to \mathbb N és (Turing-)computable si existeix una màquina de Turing M_f t.q.

  • si f(x_1,\dots,x_k) està definida, llavors, amb entrada (x_1,\dots,x_k) la màquina M_f s’atura i el valor f(x_1,\dots,x_k) està escrit en la memòria;
  • si f(x_1,\dots,x_k) no està definida, la màquina M_f no s’atura amb entrada (x_1,\dots,x_k).