Máquinas de Turing equivalentes: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Página proposta para eliminação rápida (regra R1) (usando FastButtons) |
|||
Linha 1:
Uma [[máquina de Turing]] é um dispositivo hipotético 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 mais 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, em branco }, 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 ====
{{details|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 ====
{{details|Máquina Wang-b}}
Em um influente artigo, [[Hao Wang (acadêmico) |Hao Wang]] (1954, 1957) reduziu a "[[Máquina de Post-Turing#1936: Modelo de Post|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====
{{details|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 fita 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 [[P (complexidade)|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 qualquer fita, um "branco" é impresso nesta fita, mas um símbolo de uma "biblioteca" 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 <math>M=\langle Q, \Gamma, s, b, F, \delta \rangle</math> onde
*<math>Q</math> é um conjunto finito de estados
*<math>\Gamma</math> é um conjunto finito de alfabeto da pilha
*<math>s \in Q</math> é o estado inicial
*<math>b \in \Gamma</math> é o simbolo em branco
*<math>F \subseteq Q</math> é o conjunto de estados de aceitação ou rejeição
*<math>\delta: Q \times \Gamma^k \rightarrow Q \times (\Gamma \times \{L,R,S\})^k</math> é uma função parcial chamada de função de transição, onde L é deslocamento a esquerda, R é deslocamento a esquerda, S é nenhum deslocamento.
===Máquinas de Turing determinísticas e não-determinísticas===
{{details|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 computacional|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 <math>\delta</math> é 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).
''k''-string Turing machines with input and output are used in the formal definition of the complexity resource [[DSPACE]] in, for example, 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 { '''N'''orte, '''S'''ul, '''L'''este, '''O'''este }.
* 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
== Referências ==
* [[Stephen Cook|Stephen A. Cook]] and Robert A. Reckhow (1972), ''Time-bounded random access machines'', Journal of Computer Systems Science 7 (1973), 354-375.
* [[Calvin Elgot]] and [[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, located in:
**[[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.
* {{cite book|author = [[John Hopcroft]] and [[Jeffrey Ullman]] | year = 1979| title = Introduction to Automata Theory, Languages and Computation| publisher = Addison–Wesley, Reading Mass| edition = 1st | isbn = 0-201-02988-X.}}
* {{cite book | last = Hopcroft | first = John E.| coauthors = Rajeev Motwani, Jeffrey D. Ullman| title = Introduction to Automata Theory, Languages, and Computation| edition = 2nd | publisher = Addison–Wesley | location = Reading Mass | year = 2001 | isbn = 0-201-44124-1}}
* [[Joachim Lambek]] (1961, received 15 June 1961), ''How to Program an Infinite Abacus'', Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295-302.
* [[A. A. 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, received 15 May 1961), ''An informal Arthmetical Approach to Computability and Computation'', Canadian Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 279-293.
* {{cite journal|author=[[Marvin Minsky]]
|title=Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines
|journal=Annals of Math
|year=1961, received August 15, 1960
|volume=74
|pages=437–455
|doi=10.2307/1970290|issue=3|publisher=Annals of Mathematics|jstor=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."
* {{cite book|author = [[Christos Papadimitriou]] | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1}} Chapter 2: Turing machines, pp. 19–56.
* {{Citation|first=Nicholas|last=Pippenger|authorlink=Nick Pippenger|first2=Michael J.|last2=Fischer|authorlink2=Michael J. Fischer|title=Relations Among Complexity Measures|journal=JACM|year=1979|volume=26|issue=3|pages=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]] and [[H. E. Sturgis]] (1961) received December 1961 ''Computability of Recursive Functions'', Journal of the Association of Computing Machinery (JACM) 10:217-255, 1963.
[[Categoria:Teoria da computação]]
[[en:Turing machine equivalents]]
| |||