Equivalentes da máquina de Turing - Turing machine equivalents

Uma máquina de Turing é um dispositivo de computação hipotético, concebido pela primeira vez por Alan Turing em 1936. As máquinas de Turing manipulam símbolos em uma faixa potencialmente infinita de fita de acordo com uma tabela finita de regras e fornecem os fundamentos teóricos para a noção de um algoritmo de computador.

Embora nenhum dos modelos a seguir tenha demonstrado ter mais poder do que o modelo da máquina de Turing com uma única fita, infinito unidirecional e vários símbolos, seus autores os definiram e usaram para investigar questões e resolver problemas mais facilmente do que poderiam. se eles tivessem ficado com o modelo de uma máquina de Turing .

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

Equivalência de Turing

Muitas máquinas que podem ser consideradas como tendo mais capacidade computacional do que uma simples máquina de Turing universal podem ser mostradas como não tendo mais potência. Eles podem computar mais rápido, talvez, ou usar menos memória, ou seu conjunto de instruções pode ser menor, mas eles não podem computar de forma mais poderosa (ou seja, mais funções matemáticas). (A tese de Church-Turing supõe que isso seja verdade: que qualquer coisa que pode ser "computada" pode ser computada por alguma máquina de Turing.)

Os modelos de máquina sequencial

Todos os itens a seguir são chamados de "modelos de máquina sequencial" para distingui-los dos "modelos de máquina paralela".

Máquinas de Turing baseadas em fita

Modelo de uma máquina de Turing

A máquina de Turing (como ele a chamava) tinha extremidade esquerda, extremidade direita infinita. Ele forneceu símbolos əə para marcar a extremidade esquerda. Um número finito de símbolos de fita era permitido. As instruções (no caso de uma máquina universal) e a "entrada" e "saída" foram escritas apenas em "quadrados F" e os marcadores deveriam aparecer em "quadrados E". Em essência, ele dividiu sua máquina em duas fitas que sempre se moviam juntas. As instruções apareciam em uma forma tabular chamada "5-tuplas" e não eram executadas sequencialmente.

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

Os modelos a seguir são máquinas de Turing de fita única, mas restritos com (i) símbolos de fita restrita {marca, espaço em branco} e / ou (ii) instruções sequenciais semelhantes a computador e / ou (iii) ações de máquina totalmente atomizadas.

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

Emil Post em uma descrição independente de um processo computacional, reduziu os símbolos permitidos ao conjunto binário equivalente de marcas na fita {"marca", "em branco" = not_mark}. Ele mudou a noção de "fita" de infinito unilateral à direita para um conjunto infinito de quartos, cada um com uma folha de papel em ambas as direções. Ele atomizou as 5-tuplas de Turing em 4-tuplas - instruções de movimento separadas das instruções de imprimir / apagar. Embora seu modelo de 1936 seja ambíguo quanto a isso, o modelo de 1947 de Post não exigia a execução de instruções sequenciais.

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

Maquinas Wang

Em um artigo influente, Hao Wang reduziu a " formulação 1 " de Post a máquinas que ainda usam uma fita binária infinita bidirecional, 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 objetivo principal declarado era oferecer, como uma alternativa à teoria de Turing, uma que "fosse mais econômica nas operações básicas". Seus resultados foram "formulações de programa" de uma variedade de tais máquinas, incluindo a máquina Wang W de 5 instruções com o conjunto de instruções

{SHIFT-LEFT, SHIFT-RIGHT, MARK-SQUARE, ERASE-SQUARE, JUMP-IF-SQUARE-MARKED-to xxx}

e sua máquina Wang B de 4 instruções mais severamente reduzida ("B" para "básico") com o conjunto de instruções

{SHIFT-LEFT, SHIFT-RIGHT, MARK-SQUARE, JUMP-IF-SQUARE-MARKED-to xxx}

que não tem nem mesmo uma instrução ERASE-SQUARE.

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

Minsky desenvolveu a noção de Wang com sua versão do modelo de "contra-máquina" (multi-fitas) que permitia o movimento SHIFT-LEFT e SHIFT-RIGHT das cabeças separadas, mas nenhuma impressão. Nesse caso, as fitas teriam a extremidade esquerda, cada extremidade marcada com uma única "marca" para indicar o fim. Ele foi capaz de reduzir isso a uma única fita, mas às custas da introdução de movimento multi-tape-square equivalente à multiplicação e divisão ao invés do muito mais simples {SHIFT-LEFT = DECREMENT, SHIFT-RIGHT = INCREMENT}.

Davis, adicionando uma instrução HALT explícita a uma das máquinas discutidas por Wang, usou um modelo com o conjunto de instruções

{SHIFT-LEFT, SHIFT-RIGHT, APAGAR, MARK, JUMP-IF-SQUARE-MARKED-to xxx, JUMP-to xxx, HALT}

e também considerou versões com alfabetos em fita de tamanho maior que 2.

Linguagem de máquina teórica de Böhm P "

Em consonância com o projeto de Wang de buscar uma teoria equivalente a Turing "econômica nas operações básicas", e desejando evitar saltos incondicionais, uma linguagem teórica notável é a linguagem P de 4 instruções " introduzida por Corrado Böhm em 1964 - o primeiro" GOTO - a menos que a linguagem de programação estruturada "imperativa" seja comprovada como Turing-completa .

Máquinas de Turing multi-fita

Na análise prática, vários tipos de máquinas de Turing com várias fitas são frequentemente usados. As máquinas de fita múltipla são semelhantes às máquinas de fita única, mas há algum número constante k de fitas independentes.

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

Se a tabela de ações tiver no máximo uma entrada para cada combinação de símbolo e estado, a máquina é uma "máquina de Turing determinística" (DTM). Se a tabela de ações contiver várias entradas para uma combinação de símbolo e estado, a máquina é uma "máquina de Turing não determinística" (NDTM). Os dois são computacionalmente equivalentes, ou seja, é possível transformar qualquer NDTM em DTM (e vice-versa ) , embora geralmente tenham tempos de execução diferentes. Isso pode ser comprovado por meio de construção.

Máquinas de Turing esquecidas

Uma máquina de Turing inconsciente é uma máquina de Turing onde, para cada comprimento de entrada, o movimento das várias cabeças é uma função fixa do tempo, independente da entrada. Em outras palavras, há uma sequência predeterminada na qual as várias fitas são digitalizadas, avançadas e gravadas. Os valores reais que são gravados na fita em qualquer etapa ainda podem ser diferentes para cada entrada desse comprimento. Pippenger e Fischer mostraram que qualquer cálculo que pode ser executado por uma máquina de Turing de várias fitas em n etapas pode ser executado por uma máquina de Turing de duas fitas inconsciente em etapas. ${\ displaystyle O (n \ log n)}$

Registrar modelos de máquinas

Peter van Emde Boas inclui todas as máquinas desse tipo em uma classe, "a máquina de registro". No entanto, historicamente, a literatura também chamou o membro mais primitivo deste grupo, ou seja, "a contra-máquina" - "a máquina de registro". E a personificação mais primitiva de uma "contra-máquina" é às vezes chamada de "máquina Minsky".

A "máquina de balcão", também chamada de modelo de "máquina de registro"

A máquina de registro de modelo primitivo é, na verdade, uma máquina de Post-Turing de 2 símbolos com várias fitas, com comportamento restrito, de modo que suas fitas agem como simples "contadores".

Na época de Melzak, Lambek e Minsky, a noção de um "programa de computador" produzia um tipo diferente de máquina simples com muitas fitas da extremidade esquerda cortadas de uma fita Post-Turing. Em todos os casos, os modelos permitem apenas dois símbolos de fita {marca, branco}.

Algumas versões representam os inteiros positivos como apenas strings / pilha de marcas permitidas em um "registro" (ou seja, fita com a extremidade esquerda) e uma fita em branco representada pela contagem "0". Minsky eliminou a instrução PRINT às custas de fornecer a seu modelo uma única marca obrigatória na extremidade esquerda de cada fita.

Neste modelo, as fitas-como-registradores de terminação única são pensadas como "contadores", suas instruções restritas a apenas dois (ou três se a instrução TEST / DECREMENT for atomizada). Dois conjuntos de instruções comuns são os seguintes:

(1): {INC (r), DEC (r), JZ (r, z)}, ou seja

{Aumente o conteúdo do registro #r; Decrementa o conteúdo do registro #r; IF content of # r = Zero THEN Jump-to Instruction #z}

(2): {CLR (r); INC (r); JE (r _i , r _j , z)}, ou seja

{Conteúdo CLeaR do registro r; Conteúdo de incremento de r; compare o conteúdo de r _i com r _j e se for igual, pule para a instrução z}

Embora seu modelo seja mais complicado do que esta descrição simples, o modelo Melzak "seixo" estendeu essa noção de "contador" para permitir adições e subtrações de vários seixos.

O modelo de máquina de acesso aleatório (RAM)

Melzak reconheceu alguns defeitos sérios em seu modelo de registrador / contra-máquina: (i) Sem uma forma de endereçamento indireto, ele não seria capaz de mostrar "facilmente" que o modelo é equivalente a Turing , (ii) O programa e os registros estavam em diferentes "espaços", então os programas de auto-modificação não seriam fáceis. Quando Melzak adicionou endereçamento indireto a seu modelo, ele criou um modelo de máquina de acesso aleatório.

(No entanto, com a numeração de Gödel das instruções, Minsky ofereceu uma prova de que com tal numeração as funções recursivas gerais eram de fato possíveis; ele oferece a prova de que a recursão µ é de fato possível).

Ao contrário do modelo RASP, o modelo RAM não permite que as ações da máquina modifiquem suas instruções. Às vezes, o modelo funciona apenas de registro para registro, sem acumulador, mas a maioria dos modelos parece incluir um acumulador.

van Emde Boas divide os vários modelos de RAM em vários subtipos:

SRAM, o "sucessor RAM" com apenas uma instrução aritmética, o sucessor (INCREMENT h). Os outros incluem "CLEAR h" e um IF igualdade-entre-registrador THEN salto para xxx.
RAM: o modelo padrão com adição e subtração
MRAM: a RAM aumentada com multiplicação e divisão
BRAM, MBRAM: versões booleanas bit a bit da RAM e MRAM
N ****: versões não determinísticas de qualquer um dos itens acima com um N antes do nome

O modelo de máquina do programa armazenado de acesso aleatório (RASP)

O RASP é uma RAM com as instruções armazenadas junto com seus dados no mesmo 'espaço' - ou seja, sequência de registradores. A noção de um RASP foi descrita pelo menos já em Kiphengst. Seu modelo tinha um "moinho" - um acumulador, mas agora as instruções estavam nos registros com os dados - a chamada arquitetura de von Neumann . Quando o RASP tem registros pares e ímpares alternados - o par mantendo o "código de operação" (instrução) e o ímpar mantendo seu "operando" (parâmetro), o endereçamento indireto é obtido simplesmente modificando o operando de uma instrução.

O modelo RASP original de Elgot e Robinson tinha apenas três instruções no estilo do modelo de máquina de registro, mas eles as colocaram no espaço de registro junto com seus dados. (Aqui COPY toma o lugar de CLEAR quando um registro, por exemplo, "z" ou "0" começa com e sempre contém 0. Este truque não é incomum. A unidade 1 no registro "unidade" ou "1" também é útil.)

{INC (r), CÓPIA (r _i , r _j ), JE (r _i , r _i , z)}

Os modelos RASP permitem endereçamento indireto e direto; alguns permitem instruções "imediatas" também, por exemplo, "Carregar acumulador com a constante 3". As instruções podem ser de um conjunto altamente restrito, como as seguintes 16 instruções de Hartmanis. Este modelo usa um acumulador A. Os mnemônicos são aqueles que os autores usaram (seu CLA é "acumulador de carga" com constante ou de registro; STO é "acumulador de armazenamento"). Sua sintaxe é a seguinte, exceto os saltos: "n, <n>, <<n>>" para "imediato", "direto" e "indireto"). Os saltos são por meio de duas "instruções de transferência" TRA - salto incondicional diretamente "n" ou indiretamente "<n>" atolando o conteúdo do registrador n no contador de instruções, TRZ (salto condicional se o acumulador for zero da mesma maneira que o TRA):

{ADICIONE n, ADICIONE <n>, ADICIONE << n >>, SUB n, SUB <n>, SUB << n >>, CLA n, CLA <n>, CLA << n >>, STO <n> , STO << n >>, TRA n, TRA <n>, TRZ n, TRA <n>, HALT}

O modelo de máquina Pointer

Um relativo atrasado é a Máquina de Modificação de Armazenamento de Schönhage ou máquina de ponteiro . Outra versão é a máquina Kolmogorov-Uspensii, e a proposta de "autômato de ligação" de Knuth. (Para referências, consulte a máquina do ponteiro ). Como um diagrama de máquina de estado, um nó emite pelo menos duas "arestas" (setas) rotuladas que apontam para outro nó ou nós que, por sua vez, apontam para outros nós, etc. O mundo externo aponta para o nó central.

Máquinas com entrada e saída

Qualquer uma das máquinas baseadas em fita acima pode ser equipada com fitas de entrada e saída; qualquer uma das máquinas baseadas em registro acima pode ser equipada com registros de entrada e saída dedicados. Por exemplo, o modelo de máquina-ponteiro de Schönhage tem duas instruções chamadas " entrada λ ₀ , λ ₁ " e " saída β ".

É difícil estudar a complexidade do espaço sublinear em máquinas de fitas múltiplas com o modelo tradicional, porque uma entrada de tamanho n já ocupa o espaço n . Assim, para estudar pequenas classes DSPACE , devemos usar um modelo diferente. Em certo sentido, se nunca "gravarmos" na fita de entrada, não queremos nos cobrar por esse espaço. E se nunca "lermos" nossa fita de saída, não queremos nos cobrar por esse espaço.

Resolvemos este problema introduzindo uma máquina de Turing de k -string com entrada e saída. É o mesmo que uma máquina de Turing de k -string comum , exceto que a função de transição $δ$ é restrita para que a fita de entrada nunca possa ser alterada e para que o cabeçote de saída nunca possa se mover para a esquerda. Este modelo nos permite definir classes espaciais determinísticas menores que lineares. As máquinas de Turing com entrada e saída também têm a mesma complexidade de tempo que outras máquinas de Turing; nas palavras de Papadimitriou 1994 Prop 2.2:

Para qualquer máquina de Turing M de k -string operando dentro do limite de tempo, há uma máquina de Turing M 'de -string com entrada e saída, que opera dentro do limite de tempo .

{\ displaystyle f (n)}

{\ displaystyle (k + 2)}

{\ displaystyle O (f (n))}

Máquinas de Turing de k -string com entrada e saída podem ser usadas na definição formal do recurso de complexidade DSPACE .

Outras máquinas e métodos equivalentes

Máquina de Turing multidimensional: Por exemplo, um modelo de Schönhage usa os quatro comandos de movimento da cabeça { N orth, S outh, E ast, W est}.
Máquina de Turing de fita única e várias cabeças: em uma prova de indecidibilidade do "problema da etiqueta", Minsky, Shepherdson e Sturgis descreveram máquinas com uma única fita que podiam ler ao longo da fita com uma cabeça e escrever mais ao longo da fita com outra .

O algoritmo de Markov é outro modelo computacional notavelmente simples, baseado na reescrita de strings, equivalente às máquinas de Turing.
Cálculo lambda
Autômato de fila

Languages

In other projects