Máquinas de Turing equivalentes

Máquina de Turing
Máquina
Máquina de Turing universal Máquina de Turing alternada Máquina de Turing quântica Máquina de Turing não determinística Máquina de Turing somente de leitura Máquina de Turing movimentação à direita Máquina de Turing probabilística Máquina de Turing multifita Máquina de Turing de Várias Faixas Máquinas de Turing equivalentes Exemplos de Máquinas de Turing
Ciência
Alan Turing Categoria:Máquina de Turing

Uma máquina de Turing é um dispositivo teórico com uma capacidade de memória infinita, inicialmente concebida por Alan Turing em 1936. A máquina manipula símbolos em células de uma fita potencialmente infinita de acordo com uma função de transição, e pode ser adaptada para simular a lógica de qualquer algoritmo de computador.

Embora nenhum dos seguintes modelos tenha sido demonstrado ter mais poder que o modelo de máquina de Turing de uma fita — infinita e multi-símbolo —, seus autores definiram e usaram tais máquinas para investigar questões e resolver problemas mais facilmente do que eles poderiam ter ao usar o modelo tradicional da máquina de Turing.

Máquinas equivalentes ao modelo da Máquina de Turing

Turing-equivalência

Muitas máquinas que possam ser imaginadas a ter maior capacidade computacional do que uma simples máquina de Turing universal podem ser mostradas não ter mais poder (Hopcroft and Ullman p. 159, cf Minsky). Elas podem computar mais rapidamente, ou talvez usar menos memória, ou o seu conjunto de instruções pode ser menor, mas elas não podem computar de forma mais poderosa (i.e. mais funções matemáticas). (A tese de Church-Turing levanta a seguinte hipótese: tudo que pode ser “computado”, pode ser computado por alguma máquina de Turing).

Os modelos de máquina sequencial

Todos os modelos a seguir são chamados de "modelos de máquina sequencial" para distingui-los dos "modelos de máquina paralela" (van Emde Boas (1990) p. 18).

Máquinas de Turing baseadas em Fita

Máquinas de uma fita com símbolos e/ou instruções restritos

Os seguintes modelos são máquinas de Turing de fita única, mas restringidos com (i) símbolos de fita restritos { "marcado", "desmarcado" }, e/ou (ii) instruções sequenciais e/ou (iii) ações de máquina completamente atomizadas.

Modelo de computação "Formulação 1" de Post

Ver artigo principal: Máquina de Post-Turing

Emil Post (1936) em uma descrição independente de um processo computacional, reduziu os símbolos permitidos ao conjunto binário equivalente de marcas na fita { "marcado", "desmarcado"=vazio}. Ele mudou a noção de "fita", partindo de uma fita infinita pelo lado direito para um conjunto infinito de caixas, cada uma com um conjunto de instruções para ambas as direções. Ele atomizou as 5-uplas de Turing em instruções de 4-uplas separadas das instruções de imprimir/apagar símbolos. Embora seu (1936) modelo seja ambíguo em respeito a isso, o modelo de Post (1947) não exige a execução de instruções sequenciais.

Seu modelo extremamente simples pode simular qualquer máquina de Turing, e embora sua "Formulação 1" de 1936 não use a palavra "programa" ou "máquina", ela é efetivamente uma formulação de um computador programável muito primitivo e associada a linguagem de programação, com ações em caixas como uma memória ilimitada e o conjunto de instruções constituindo um programa.

Máquinas Wang

Ver artigo principal: Máquina Wang-b

Em um influente artigo, Hao Wang (1954, 1957) reduziu a "formulação 1" de Post para máquinas que ainda usam uma fita binária infinita pelos dois lados, mas cujas instruções são mais simples — sendo os componentes "atômicos" das instruções de Post — e são por padrão executadas sequencialmente (como um "programa de computador"). Seu principal objetivo declarado foi o de oferecer, como uma alternativa a teoria de Turing, uma que é "mais econômica em operações básicas". Seus resultados são "formulações de programas" de uma variedade de tais máquinas, incluindo a máquina de Wang-W com o conjunto de instruções

{ DESLOCA-ESQUERDA, DESLOCA-DIREITA, MARCA-QUADRADO, APAGA-QUADRADO, PULE-SE-QUADRADO-MARCADO-PARA xxx }

e seu ainda mais reduzido conjunto com 4 instruções da Máquina Wang-b

{ DESLOCA-ESQUERDA, DESLOCA-DIREITA, MARCA-QUADRADO, PULE-SE-QUADRADO-MARCADO-PARA xxx }

que não tem sequer uma instrução APAGA-QUADRADO.

Muitos autores mais tarde introduziram variantes das máquinas discutidas por Wang:

Minsky (1961) evoluiu a noção de Wang com sua versão de modelo de "máquina contadora" (multi-fita) que permitiu os movimentos de DESLOCA-ESQUERDA e DESLOCA-DIREITA de cabeças separadas mas não imprimindo em todas elas. Neste caso, as fitas seriam não-finitas pelo lado esquerda, onde cada fim é marcado com uma única "marca" para indicar o final. Ele foi capaz de reduzir isso para uma única fita, mas à custo da introdução de movimentos de multi-fita equivalentes para multiplicação e divisão em vez do muito mais simples { DESLOCA-ESQUERDA = DECREMENTA, DESLOCA-DIREITA = INCREMENTA }.

Davis, adicionando uma instrução explícita PARE (Halt) em uma das máquinas discutidas por Wang, utilizou um modelo com o conjunto de instruções

{ DESLOCA-ESQUERDA, DESLOCA-DIREITA, APAGA, MARCA, PULE-SE-QUADRADO-MARCADO-PARA xxx, PULE-PARA xxx, PARE }

e também tendo considerado versões com alfabetos de fita de tamanho maior do que 2.

Linguagem Teórica P" de Böhm

Ver artigo principal: P''

De acordo com o projeto de Wang para buscar uma teoria Turing-equivalente que seja "econômica em operações básicas", e desejando evitar saltos incondicionais, uma notável linguagem teórica é a linguagem P'', de 4 instruções, introduzida por Corrado Böhm em 1964 — a primeira linguagem de "programação estruturada" imperativa, "sem GOTO", a ser provada Turing completa.

Máquinas de Turing multi-fita

Em análise prática, vários tipos de máquinas de Turing multi-fita são frequentemente utilizados. Máquinas multi-fitas são semelhantes às máquinas com uma única fita, mas há um número constante k de fitas independentes.

A função de transição tem controle independente total sobre todas as cabeças, incluindo qualquer movimento e escrita de símbolos em suas próprias fitas (cf Aho-Hopcroft-Ullman 1974 p. 26). A maioria dos modelos tem fitas não-finitas pelo lado esquerdo, e finitas pelo lado direito.

Este modelo intuitivamente parece ser muito mais poderoso que o modelo de uma única fita, mas qualquer máquina multi-fita, não importa quão grande seja o k, pode ser simulada por uma máquina com uma única fita usando apenas um tempo quadraticamente maior (Papadimitriou 1994, Thrm 2.1.). Assim, máquinas multi-fitas não podem calcular quaisquer funções a mais que as máquinas de fita única, e nenhuma das classes robustas de complexidade (tal como tempo polinomial) são afetadas por uma mudança entre máquinas de fita única e multi-fita.

Máquina de Turing de duas pilhas

Máquinas de Turing de duas pilhas tem uma entrada de somente leitura e duas fitas de armazenamento. Se uma cabeça se mover para a esquerda de qualquer fita, um "branco" é impresso nesta fita, mas um símbolo de uma "biblioteca" também pode ser impresso.

Definição formal: máquina de Turing multi-fita

Uma máquina de Turing de k-fitas pode ser descrita como uma 6-upla $M=\langle Q,\Gamma ,s,b,F,\delta \rangle$ onde

• $Q$ é um conjunto finito de estados
• $\Gamma$ é um conjunto finito de alfabeto da pilha
• $s\in Q$ é o estado inicial
• $b\in \Gamma$ é o simbolo em branco
• $F\subseteq Q$ é o conjunto de estados de aceitação ou rejeição
• $\delta :Q\times \Gamma ^{k}\rightarrow Q\times (\Gamma \times \{L,R,S\})^{k}$ é uma função parcial chamada de função de transição, onde L é deslocamento à esquerda, R é deslocamento à esquerda, S é nenhum deslocamento.

Máquinas de Turing determinísticas e não-determinísticas

Ver artigo principal: máquina de Turing não-determinística

Se a função de transição tiver exatamente uma entrada para cada combinação de símbolo e estado, então a máquina é uma "Máquina de Turing determinística" (MTD). Se a função de transição contiver múltiplas entradas para uma combinação de símbolo e estado, então a máquina é uma "Máquina de Turing não-determinística" (MTN). Os dois são computacionalmente equivalentes, isto é, é possível transformar qualquer MTN em uma MTD (e vice-versa).

Máquinas de turing oblivious

Uma máquina de Turing oblivious é uma máquina de Turing onde o movimento de várias cabeças são funções constantes de tempo, independente da entrada. Em outras palavras, há uma sequência pré-determinada em que várias fitas são varridas e escritas. Pippenger and Fischer (1979) mostrou que qualquer computação que pode ser executada por uma máquina de Turing multi-fita em n passos pode ser executada por uma máquina de Turing oblivious de duas fitas em O(n log n) passos.

Máquinas com entrada entrada e saída

Qualquer uma das máquinas baseadas em fita acima pode ser equipada com fitas de entrada e saída.

É difícil estudar complexidade de espaço sublinear em máquinas multi-fita com o modelo tradicional, porque uma entrada de tamanho n já toma um espaço n. Assim, para estudar pequenas classes DSPACE, nós devemos usar um modelo diferente. Em certo sentido, se nós nunca escrevemos na fita de entrada, nós não queremos carregar a máquina com esse espaço. E se nós nunca lemos da nossa fita de saída, nós também não queremos carregar a máquina com esse espaço.

Nós resolvemos esse problema ao introduzir uma máquina de Turing de k-cadeia com entrada e saída. Isso é o mesmo que uma máquina de Turing de k-cadeia ordinária, exceto que a função de transição $\delta$ é limitada, de modo que a fita de entrada nunca pode ser alterada, e assim como a cabeça de saída nunca pode se mover para a esquerda. Este modelo nos permite definir classes de espaço determinísticas menores do que a linear. Máquinas de Turing com entrada-e-saída também tem a mesma complexidade de tempo que as outras máquinas de Turing; em outras palavras de Papaditriou 1994 Prop 2.2:

Para qualquer máquina de Turing de k-cadeia M operando dentro do limite de tempo f(n)), há uma máquina de Turing de (k+2)-cadeia com entrada e saída que opera dentro do limite de tempo O(f(n)).

Máquinas de Turing de k-cadeia com entrada e saída são frequentemente usadas em definições formais de recursos de complexidade DSPACE em, por exemplo, Papadimitriou 1994 (Def. 2.6).

Outras máquinas equivalentes e métodos

• Máquina de Turing multidimensional: Por exemplo, um modelo de Schönhage (1990) usa as quatro instruções de movimentos de cabeça { Norte, Sul, Leste, Oeste }.
• Máquina de Turing de uma fita e multi-cabeça: Em uma prova de indecidibilidade do "problema da etiqueta", Minsky (1961) e Shepherdson and Sturgis (1963) descreveram máquinas com uma única fita que poderia escrever ao longo da fita com uma única cabeça e ler adicionalmente ao longo da fita com uma outra cabeça.
• Algoritmo de Markov (1960) é outro notável modelo computacional simples, baseado na reescrita de cadeias, equivalente à máquinas de Turing.
• Cálculo Lambda
• Autômato de fila
• Modelos de máquina de registro

Bibliografia

• Stephen A. Cook e Robert A. Reckhow (1972), Time-bounded random access machines, Journal of Computer Systems Science 7 (1973), 354-375.
• Calvin Elgot e Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Languages, Journal of the Association for Computing Machinery, Vol. 11, No. 4 (October, 1964), pp. 365–399.
• Peter van Emde Boas, Machine Models and Simulations, pp. 3–66, localizado em:
  • Jan van Leeuwen, ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT Press/Elsevier, 1990. ISBN 0-262-72014-0 (volume A). QA76.H279 1990.
• J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.
• Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine', Zeitschrift fur mathematische Logik und Grundlagen der Mathematik:5 (1959), 366-379.
• John Hopcroft e Jeffrey Ullman (1979). Introduction to Automata Theory, Languages and Computation 1st ed. [S.l.]: Addison–Wesley, Reading Mass. ISBN 0-201-02988-X. 
• Hopcroft, John E.; Rajeev Motwani, Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages, and Computation 2 ed. Reading Mass: Addison–Wesley. ISBN 0-201-44124-1 
• Joachim Lambek (1961, recebido em 15 de Junho de 1961), How to Program an Infinite Abacus, Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295-302.
• Andrey Markov (1954) Theory of algorithms. [Translated by Jacques J. Schorr-Kon and PST staff] Imprint Moscow, Academy of Sciences of the USSR, 1954 [i.e. Jerusalem, Israel Program for Scientific Translations, 1961; available from the Office of Technical Services, U.S. Dept. of Commerce, Washington] Description 444 p. 28 cm. Added t.p. in Russian Translation of Works of the Mathematical Institute, Academy of Sciences of the USSR, v. 42. Original title: Teoriya algerifmov. [QA248.M2943 Dartmouth College library. U.S. Dept. of Commerce, Office of Technical Services, number OTS 60-51085.]
• Z. A. Melzak (1961, recebido em 15 de Maio de 1961), An informal Arthmetical Approach to Computability and Computation, Canadian Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 279-293.
• Marvin Minsky. 1961, received August 15, 1960. «Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines». Annals of Mathematics. Annals of Math. 74 (3): 437–455. JSTOR 1970290. doi:10.2307/1970290 
• Marvin Minsky, Computation: Finite and Infinite Machines, Prentice–Hall, Inc., N.J., 1967. See Chapter 8, Section 8.2 "Unsolvability of the Halting Problem."
• Christos Papadimitriou (1993). Computational Complexity 1st ed. [S.l.]: Addison Wesley. ISBN 0-201-53082-1  Chapter 2: Turing machines, pp. 19–56.
• Pippenger, Nicholas; Fischer, Michael J. (1979) Relations Among Complexity Measures, Journal of the Association of Computing Machinery (JACM) 26 (3): 361–381, doi:10.1145/322123.322138
• A. Schonhage (1980), Storage Modification Machines, Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980.
• John C. Shepherdson e H. E. Sturgis (1961) Computability of Recursive Functions, Journal of the Association of Computing Machinery (JACM) 10:217-255, 1963.