Exemplos de composição de máquinas de Turing. Computabilidade adequada de funções em uma máquina de Turing
A máquina de Turing (MT) é um executor abstrato (máquina de computação abstrata).
Combinações de algoritmos é o nome que foi estabelecido para uma série de métodos específicos para construir novos algoritmos a partir de vários métodos específicos.
Teoremas sobre combinações de algoritmos constituem uma seção importante da teoria geral dos algoritmos. Uma vez comprovados, eles permitem verificar posteriormente a viabilidade de algoritmos complexos e complicados sem realmente escrever os circuitos que os definem.
As combinações de algoritmos para uma máquina de Turing são descritas por operações em máquinas de Turing.
1. Operação de composição.
Sejam M 1 e M 2 máquinas de Turing com o mesmo alfabeto externo A« (a 0 ,a 1 ,...,a p ). Denotemos os conjuntos de seus estados respectivamente como Q1 "(q 0,q 1,...,q n) e Q2 "(q 0",q 1",...,q m").
Definição.
Uma composição de máquinas M 1 e M 2 é uma máquina denotada M=M 1 ×M 2, cujo programa possui um alfabeto A, um conjunto de estados Q« (q 0,q 1,...,q n,q n+1,... ,q n+m) e é obtido a partir dos programas das máquinas M 1 e M 2 da seguinte forma: em todos os lugares do programa da máquina M 1, onde existem “triplos” com o símbolo q 1 ( o estado final da máquina M 1), é substituído pelo símbolo q 0" (o estado inicial da máquina M 2); todos os outros símbolos nos programas das máquinas M 1 e M 2 permanecem inalterados (no final resta renumerar todos os estados da máquina M: (q 0 ,q 1" ,q 2 ,...,q n ,q 0 " ,q 2" ,...,q m" )).
A composição passa a “funcionar” como uma máquina M 1, mas nos casos em que a máquina M 1 deve parar, ela passa para o programa da máquina M 2, devido à substituição de q 1 por q 0". Obviamente, a operação de composição é associativa, mas não comutativa.
Sua operação equivale à operação sequencial das máquinas T1 e T2.
A figura mostra uma composição de máquinas de Turing que implementa o operador de superposição para n=1 e m=1.
Imagem 1.
Definição.
Uma iteração de uma máquina de Turing M será chamada de máquina
2. Operação de ramificação.
Sejam M 1, M 2 e M 3 máquinas de Turing com o mesmo alfabeto externo A« (a 0,a 1,...,a i,...,a j,...,a p) e, consequentemente, conjuntos de estados: Q1 "(q 0 ,q 1 ,...,q n ), Q2 " (q 0 " ,q 1 " ,...,q m " ), Q3 " (q 0 " , q 1 " ,.. ,q eu" ).
Definição.
O resultado da operação de ramificação nas máquinas de Turing M 1, M 2 e M3 é denominado máquina de Turing M, cujo programa é obtido a partir dos programas das máquinas M 1, M 2 e M 3 da seguinte forma: o programa de a máquina M1 é escrita, então os programas das máquinas M 2 e M 3 são atribuídos. Se no estado final q 1 da máquina M1 o símbolo a i for observado, então o controle é transferido para a máquina M 2, ou seja, o símbolo q 1 é substituído pelo símbolo q 0" e a máquina M 2 começa a funcionar. Se no estado final q 1 da máquina M 1 for observado o símbolo a j, então o controle é transferido para a máquina M 3, ou seja, o símbolo q 1 é substituído pelo símbolo q 0" e a máquina M 3 começa a trabalhar. Todos os outros símbolos nos programas das máquinas M 1 e M 2 permanecem inalterados. A máquina M completa seu trabalho no estado final q 1 (em conclusão, resta realizar a renumeração ponta a ponta dos estados da máquina M).
O resultado de uma operação de ramificação nas máquinas de Turing M 1, M 2 e M3 é denotado da seguinte forma:
Para máquinas de Turing de duas letras (máquinas de Turing com alfabeto de duas letras), a operação de ramificação em máquinas de Turing arbitrárias M1, M2 e M3 é denotada da seguinte forma:
aqueles. se quando a máquina M1 estiver operando no estado q 1, o símbolo a 0 for observado, então o controle é transferido para a máquina M2, caso contrário - para a máquina M3.
3. Operação em loop.
Seja M uma máquina de Turing com alfabeto A« (a 0 ,a 1 ,...,a p ) e conjunto de estados Q« (q 0 ,q 1 ,...,q n ).
Definição.
O resultado da operação de loop será chamado de máquina de Turing, denotada por (i=0,2,3,...,n; j=0,1,2,...,p; s=0,2, 3,..., n)
cujo programa é obtido a partir do programa da máquina M substituindo o símbolo q 1 no consequente do comando q i a j ®q 1 a t r, rО(L,R,L), t=0,1,2,.. .p, com o símbolo q s .
2.4 Variantes da máquina de Turing
O modelo da máquina de Turing pode ser estendido. Pode-se considerar máquinas de Turing com um número arbitrário de fitas e fitas multidimensionais com diversas restrições. No entanto, todas essas máquinas são Turing completas e modeladas por uma máquina de Turing comum.
Como exemplo dessa equivalência, considere a redução de qualquer MT a um MT operando em uma fita semi-infinita.
Teorema: Para qualquer máquina de Turing, existe uma máquina de Turing equivalente rodando em uma fita semi-infinita.
Prova:
Consideremos a prova de Yu. G. Karpov. A prova deste teorema é construtiva, ou seja, daremos um algoritmo pelo qual para qualquer máquina de Turing uma máquina de Turing equivalente com a propriedade declarada pode ser construída. Primeiramente, numeramos aleatoriamente as células da fita de trabalho MT, ou seja, determinamos uma nova localização de informações na fita:
Imagem 1.
Em seguida, renumeramos as células e assumiremos que o símbolo “*” não está contido no dicionário MT:
Imagem 1.
2.5 Computabilidade e decidibilidade de Turing
Foi provado acima que as classes de funções computáveis usando funções recursivas, máquinas de Turing ou algoritmos normais de Markov coincidem. Isso nos permite considerar o conceito de “algoritmo computacional” invariante ao método de descrição. As diferenças são observadas apenas no uso de objetos algorítmicos. Se para funções recursivas os objetos são números e funções numéricas, e o processo de cálculo é especificado pelos operadores de superposição, recursão, minimização e iteração, então para máquinas de Turing tais objetos são símbolos dos alfabetos da memória externa e interna, e o cálculo o processo é especificado por um protocolo usando saída, transição e movimentação da cabeça. Para um algoritmo de Markov normal, tais objetos são palavras ou sequências de símbolos, e o processo de cálculo é especificado por regras de substituição ou produções que alteram a composição e estrutura da sequência original de símbolos para o resultado desejado.
Uma função aritmética (numérica) é uma função cujo intervalo de valores é um subconjunto do conjunto N, e seu domínio de definição é um elemento do conjunto N.
Para problemas algorítmicos, uma situação típica é quando você precisa encontrar um algoritmo para calcular uma função numérica f(x 1, x 2, ..., x n), dependendo dos valores inteiros dos argumentos x 1, x 2 , ..., xn.
Chamamos uma função f:N n →N computável se existe um algoritmo que permite que qualquer conjunto de valores de seus argumentos calcule o valor da função (ou indique que a função não está definida em um determinado conjunto). Como a definição de uma função computável usa o conceito intuitivo de algoritmo, o termo “função computável intuitiva” é frequentemente usado em vez do termo “função computável”. Assim, um problema de massa tem solução se a função aritmética correspondente ao problema for intuitivamente computável.
Uma função f(x 1 , x 2 , …, x n) é chamada efetivamente computável se, para determinados valores k 1 , k 2 , …, k n argumentos, for possível encontrar o valor da função f(k 1 , k 2 , …, k n) usando algum procedimento mecânico existente (algoritmo).
Em vez de esclarecer o conceito de algoritmo, podemos considerar esclarecer o conceito de “função computável”. Geralmente eles procedem de acordo com o seguinte esquema:
1. É introduzida uma classe de funções definida com precisão.
2. Certifique-se de que todas as funções desta classe sejam computáveis.
3. Aceite a hipótese (tese) de que a classe de funções computáveis coincide com a classe de funções introduzida.
Uma função é chamada computável se existe um algoritmo que a calcula. “Computabilidade” é um dos conceitos básicos da teoria dos algoritmos, invariante à função e ao algoritmo que está sendo calculado. A diferença entre uma função computável e um algoritmo é a diferença entre a descrição da função e a forma como ela calcula seus valores dados os valores dos argumentos independentes.
A tese de Turing. Qualquer algoritmo intuitivo pode ser implementado usando alguma máquina de Turing.
Resulta da tese de Turing que, se surgirem problemas algorítmicos, eles deverão ser resolvidos com base na construção de máquinas de Turing, ou seja, um conceito suficientemente formalizado de algoritmo. Ao mesmo tempo, em problemas algorítmicos, muitas vezes não estamos falando sobre a construção de um algoritmo, mas sobre a computabilidade de algumas funções especialmente construídas.
Ressalta-se que nestes casos basta utilizar o alfabeto (0,|), onde 0 é o caracter vazio. Por exemplo, os números naturais, incluindo 0, são codificados neste alfabeto da seguinte forma: 0 - |; 1 - ||; 2 -
N - ||…| (n + 1 vezes). Uma função numérica parcial n-local f(x1, x2, ..., xn) é chamada Turing computável se houver uma máquina M que a calcule no seguinte sentido: 1. Se o conjunto de valores dos argumentos
O PROBLEMA DA AUTO-APLICABILIDADE
De acordo com a definição de máquina de Turing, esta é uma tripla T =
P: q eu a um j a ® qr a como a S t a , uma = 1, 2,…, k , Onde S1- R, S2-EU, S3- C . (*)
Neste caso, podemos assumir que existem alguns alfabetos comuns Um 0 E Q 0, em que os caracteres são escritos a E q para todas as máquinas de Turing. Então os símbolos q eu a, um j a, qr a, como a, S t a são símbolos de alfabetos Um 0 E Q 0.
Esta abordagem permite que todas as máquinas de Turing sejam numeradas, ou seja, a cada máquina é atribuído um determinado número (código) exclusivo para esta máquina, pelo qual ela pode ser distinguida de outras máquinas. Aqui consideraremos um dos métodos de numeração.
Numeração Godeliana de máquinas de Turing. Deixar página 1, página 2, página 3 , ... - uma sequência de números primos dispostos em ordem crescente, por exemplo, 2, 3, 5, 7, 11, 13, ...
Número da máquina de Turing com programa (*) número chamado
n(T) = .
Exemplo
Uma máquina que implementa uma função S(x)= x + 1 , tem um programa no alfabeto {0, } . O número deste programa, tendo em conta que um 0 = 0 , um 1= | haverá um número:.
n(T)= 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3 .
Obviamente, nem todos os números naturais são números de máquina de Turing. Por outro lado, se n – o número de alguma máquina, em alfabetos gerais, então seu programa pode ser restaurado exclusivamente a partir desse número.
Carro T, aplicável à palavra n(T)(ou seja, para o código do seu próprio número), chamado autoaplicável .
É possível construir máquinas autoaplicáveis e máquinas não autoaplicáveis. Por exemplo, a máquina do exemplo dado é autoaplicável. Carro T, que não possui símbolo de parada nas partes direitas do programa (no corpo da tabela), não é aplicável a nenhuma palavra e, portanto, à palavra n(T).
Problema de autoaplicabilidadeé o seguinte: indicar um algoritmo que, dada qualquer máquina de Turing, determinaria se ela é autoaplicável ou não.
De acordo com a Tese de Turing, tal algoritmo deveria ser procurado na forma de uma máquina de Turing. Esta máquina deveria ser aplicável aos códigos numéricos de todas as máquinas de Turing e, dependendo do resultado do processamento dos códigos das máquinas em teste, teria configurações finais diferentes.
Deixe, por exemplo, este carro T aplicado ao código n(T * ) . Se o carro T * autoaplicável, então a configuração final da máquina T parece a" q 0 | B", e se o carro T * não é autoaplicável, então a configuração final da máquina T parece a" q 0 0B ". Aqui uma", B", uma", B"- palavras.
Teorema O problema de autoaplicabilidade é algoritmicamente indecidível, ou seja, não existe uma máquina de Turing que resolva este problema no sentido acima.
Segue-se do teorema que não existe um algoritmo geral solucionador de problema autoaplicabilidade. Em casos especiais específicos, tais algoritmos podem existir.
Utilizemos os resultados deste teorema para provar a indecidibilidade do problema de aplicabilidade à palavra inicial.
O problema da aplicabilidade à palavra inicial é o seguinte: crie um algoritmo que, de acordo com a máquina T e a palavra X instalaria, máquina aplicável T por falar nisso X ou não (caso contrário, há um problema de parada).
Em termos de máquinas de Turing, semelhante à formulação do problema de autoaplicabilidade, este problema é formulado da seguinte forma: é possível construir uma máquina que seja aplicável a todas as palavras da forma n(T)0 X , Onde T máquina arbitrária, X – uma palavra arbitrária, e se a máquina T aplicável à palavra X a" q 0 |B" , e se o carro T não aplicável à palavra X , levaria à configuração final a" q 0 0 B" . Aqui uma", B" E um",B"- palavras arbitrárias.
Teorema O problema de aplicabilidade à palavra inicial é algoritmicamente indecidível, ou seja, não existe uma máquina de Turing que resolva este problema no sentido acima.
Conforme afirmado acima para o problema de autoaplicabilidade, o primeiro passo preliminar é a numeração. Portanto, a seguir esta questão é consistentemente considerada e resolvida para algoritmos e seus três principais tipos de modelos algorítmicos.
Numeração de algoritmos
A numeração de algoritmos desempenha um papel papel importante em suas pesquisas e análises. Como qualquer algoritmo pode ser especificado como uma palavra finita (representada como uma sequência finita de símbolos de algum alfabeto), e o conjunto de todas as palavras finitas em um alfabeto finito é contável, então o conjunto de todos os algoritmos também é contável. Isto significa a existência de um mapeamento um-para-um entre o conjunto dos números naturais e o conjunto dos algoritmos, ou seja, a capacidade de atribuir um número a cada algoritmo.
A numeração dos algoritmos é também a numeração de todas as funções calculáveis por algoritmos, e qualquer função pode ter um número infinito de números.
A existência de numeração permite trabalhar com algoritmos da mesma forma que com números. A numeração é especialmente útil no estudo de algoritmos que funcionam com outros algoritmos.
Seja um certo problema de massa com um conjunto de objetos iniciais X e um conjunto de objetos desejados Y. Para que exista uma solução para o problema de massa, é necessário que os elementos dos conjuntos X e Y sejam objetos construtivos. Conseqüentemente, os elementos desses conjuntos podem ser numerados por números naturais. Seja x∈ X algum objeto inicial, vamos denotar seu número por n(x). Se em um problema de massa para o objeto original x é necessário obter o objeto desejado y∈ Y com número n(y), então definimos uma função aritmética f: Nn →N tal que f(n(x))=n (s).
Como exemplo de construção de funções aritméticas para problemas de massa, consideremos problemas de massa.
1. Se uma matriz ] de números naturais for fornecida, então pode ser atribuído a ela o número natural 2x1, 3x2,... p(n)xn , onde p(n) – enésimo primo número. Vejamos um exemplo de uma matriz de comprimento 5:
] 2x13x25x37x411x5.
Esta numeração define a função aritmética f (por exemplo, f(73500) = f(22315372110) = 20315272113 = 4891425).
2. Qualquer número racional possui algum número natural. A numeração do conjunto de objetos requeridos do problema é trivial:
(“sim”, “não”) a (1, 0). Para um determinado problema de massa, você pode construir uma função aritmética de um argumento usando a técnica do exemplo anterior, ou pode considerar uma função de três argumentos (três números de elementos do triplo original).
3. A numeração dos textos do programa pode ser realizada da seguinte forma: qualquer programa pode ser percebido como uma gravação de um número no sistema numérico 256-ário (se caracteres da tabela ASCII foram usados para gravar o programa).
A transição de um problema de massa para uma função aritmética permite-nos reduzir a questão da existência de uma solução para um problema de massa à questão da existência forma efetiva calcular os valores de uma função aritmética a partir de seu argumento (argumentos).
Numeração de conjuntos de números
Na teoria dos algoritmos, difundiu-se uma técnica que permite reduzir o estudo de funções de diversas variáveis ao estudo de funções de uma variável. Baseia-se na numeração de conjuntos de números para que haja uma correspondência bijetiva entre conjuntos de números e seus números, e as funções que determinam a partir de um conjunto de números o seu número e a partir do número o próprio conjunto de números são geralmente recursivas. Por exemplo, para uma função contendo duas variáveis independentes (x, y), este mapeamento h(x, y) poderia ser assim:
Imagem 1.
Deixe os pares (x, y) formarem um conjunto parcialmente ordenado N(2). Se h(x, y) = n for dado, então há um mapeamento inverso: x = h -1 1 (n) e y= h -1 2 (n), ou seja, h(h -1 1 (n), h -1 2 (n)) = n. Isso permite calcular o número n para qualquer par (x, y) e, inversamente, usar o número n para calcular os valores de x e y:
Usando essas regras, você pode calcular a numeração dos triplos h 2 (x, y, z) = h(h(x, y), z) = n e, inversamente, pelo número do triplo - os valores de x, y, z. Por exemplo, se h 2 (x, y, z) = n, então z= h -1 2 (n), y= h -1 2 (h -1 1 (n)), x= h -1 1 ( h -1 1 (n)), h 2 (x, y, z) = h(h(h -1 1 (h -1 1 (n)), h -1 2 (h -1 1 (n)) ) , h -1 2 (n)). Triplos (x, y, z) formam um conjunto parcialmente ordenado N(3). Da mesma forma, para um número arbitrário de números, temos:
h n-1 (x1, x2,…, xn)=h(h…h(h(x1, x2), x3)… x n-1), xn). Se h n-1 (x1, x2,…, xn)=m, então xn = h -1 2 (m), x n-1 =h -1 2 (h -1 1 (m)), ... ...................................., x2 = h -1 2 (h -1 1 (. .. h -1 1 (m)...)), x1 = h -1 2 (h (...h (m)...)).
Tendo a numeração dos conjuntos de conjuntos N (1) , N (2) ,..., N (i) ,..., N(n, onde N (i) é um conjunto de conjuntos (i) de números, é possível estabelecer uma numeração combinada de conjuntos arbitrários de números M = N (1) N (2) ... N (i) .. N(n) , onde M N. Para qualquer n N temos h(x1, x2,..., xn )= h(h n −1 (x1,x2,..., xn), n −1).
Se h(x ,1x ,2..., x)n = m, então h n−1 (x ,1x ,2..., x)n = h -1 1 (m), n= h -1 2 (m)+1. Usando as fórmulas acima, você pode restaurar os valores de x1, x2,…, xn.
Informação relacionada.
Definição, operação e métodos de especificação de uma máquina de Turing
Uma máquina de Turing é entendida como uma certa máquina hipotética (abstrata) que consiste nas seguintes partes (Fig. 3.1.)
1) uma fita infinita em ambas as direções, dividida em células, em cada uma das quais pode ser escrito apenas um caractere do alfabeto, além do caractere vazio l;
2) um dispositivo de controle (cabeça de trabalho), que a qualquer momento pode estar em um dos estados do conjunto. Em cada estado, o chefe é colocado em frente à cela e pode ler (revisar) ou escrever uma letra do alfabeto nela A.
Arroz. 3.1. Máquina de Turing
O funcionamento do MT consiste numa sequência de passos elementares (ciclos). Cada etapa executa as seguintes ações:
1. o chefe de trabalho lê (revê) o símbolo;
2. dependendo do seu estado e do símbolo que está sendo monitorado, o chefe produz um símbolo e o escreve na célula que está sendo monitorada (possivelmente =);
3. a cabeça se move uma célula para a direita (R), esquerda (EU) ou fica parado (E);
4. A cabeça entra em outro estado interno. (possivelmente =).
O estado é denominado inicial e final. Ao entrar no estado final, a máquina para.
O estado completo de MT é chamado configuração . Esta é a distribuição das letras entre as células da fita, o estado da cabeça de trabalho e da célula que está sendo monitorada. Configuração intacta té escrito na forma: , onde é a subpalavra à esquerda da célula que está sendo monitorada, é a letra da célula que está sendo monitorada, é a subpalavra à direita.
A configuração inicial e a configuração final são chamadas de padrão.
Existem 3 maneiras de descrever a operação do MT:
Sistema de comando do formulário
Mesa funcional;
Gráfico (diagrama) de transições.
Vejamos eles com exemplos.
Exemplo 1. Construa um MT que implemente a concatenação de duas palavras do alfabeto. As palavras na fita são separadas por *. A configuração inicial é padrão.
O sistema de comando MT se parece com:
Neste estado, a cabeça se move para a direita até atingir um símbolo vazio.
O caractere mais à direita é apagado.
O asterisco é apagado se a primeira palavra estiver vazia.
A palavra direita é deslocada caractere por caractere para a esquerda em uma posição.
Transição para a configuração final padrão.
Tabela de funções
| a | b | * | eu | |
| - | ||||
| - | ||||
| - | ||||
| - |
Traços na tabela significam que o símbolo l não pode ser encontrado nos estados.
|
|
|||
Configuração final padrão.
Entenderemos o cálculo de uma função de dicionário em MT da seguinte maneira. Deixe a palavra a ser escrita na fita na configuração inicial. Se o valor for determinado, então por um número finito de etapas (ciclos) a máquina deve ir até a configuração final, na qual a palavra está escrita na fita. Caso contrário, o MT deverá funcionar por tempo indeterminado.
Usando MT, você pode descrever o desempenho de operações aritméticas com números. Nesse caso, os números são apresentados na fita como palavras de um alfabeto composto por números de algum sistema numérico e separados por um sinal especial não incluído neste alfabeto, por exemplo, *. O sistema mais comumente usado é o unário, consistindo em um único símbolo –1. O número X na fita está escrito com a palavra (ou abreviado) no alfabeto UMA=(1).
Uma função numérica é adequadamente computável (ou simplesmente computável por Turing) se existir um MT que mapeie a configuração para a configuração quando = sim ou é executado indefinidamente quando indefinido.
Exemplo 2. A operação de adicionar dois números em código unário.
Configuração inicial:
Configuração final: ou seja, adição na verdade se resume a atribuir um número b para o número a. Para fazer isso, o primeiro 1 é apagado e o * é substituído por 1.
Damos uma descrição do MT na forma de uma tabela funcional:
| * | eu | ||
| - | |||
| - | |||
| - |
Os métodos acima para descrever MT podem ser usados praticamente apenas para algoritmos simples, porque para os complexos, a descrição torna-se muito complicada. Da mesma forma, descrever funções recursivas usando apenas as funções e operadores mais simples de superposição, recursão primitiva e minimização seria extremamente complicado. Portanto, a recursividade primitiva ou parcial de uma função é comprovada utilizando outras funções cuja recursividade primitiva ou parcial já foi comprovada.
Da mesma forma, máquinas de Turing para algoritmos complexos podem ser construídas usando MTs existentes. Esta construção é chamada de composição MT.
Descrevemos 4 métodos principais de composição de MT:
Composição sequencial (superposição);
Composição paralela;
Ramificação
Composição sequencial máquinas e funções de dicionário de computação e no alfabeto A, chamou um carro T, que calcula a função. A composição sequencial é representada da seguinte forma:
e é designado.
A composição sequencial é geralmente usada para descrever seções lineares de algoritmos.
Prova do teorema sobre a possibilidade de construção de uma máquina T, que é uma composição sequencial de duas máquinas arbitrárias e é realizada identificando o estado final com o estado inicial.
Exemplo 3. Construa um algoritmo de multiplicação 2*X em código unário usando uma copiadora que traduz a palavra a na palavra a*a e uma máquina de adição. O MT necessário é assim:
| | | |
|||||||||||||
| | |
||||||||||||||
Composição paralela máquinas e funções de dicionário de computação e alfabetos A E EM portanto, a máquina é chamada T, que avalia uma função de dicionário. Aqui o sinal é usado para separar palavras em composição MT paralela.
| |
e é designado: .
Na verdade, uma composição paralela de dois MTs recebe como entrada uma palavra composta por 2 palavras em alfabetos diferentes e produz uma palavra composta por 2 palavras, ou seja, representa duas máquinas que trabalham simultaneamente e de forma independente.
Para implementar uma composição paralela, é utilizada uma máquina com correia de dois andares. A necessidade disso se deve ao fato de que o cálculo e o tempo ocorrem sequencialmente, e, calculado, por exemplo, primeiro, pode exigir mais espaço que a e estragar a palavra b. O gravador de dois andares funciona assim: a palavra b é escrita no segundo andar e apagada no primeiro andar, computada no primeiro andar, computada no segundo andar e depois reescrita no primeiro andar, possivelmente com um turno .
Para implementar composição paralela n máquinas usadas n– fita de chão.
O comando MT com fita de dois andares é escrito da seguinte forma:, onde estão as letras escritas no primeiro e segundo andares, respectivamente.
Exemplo 4. Implementar uma composição paralela de máquinas e funções de cálculo no sistema numérico binário e a+b no sistema unário.
A palavra de entrada tem o formato: .
Descrevemos o funcionamento do MT com um sistema de comandos:
Vá para a direita para a palavra b
Reescrevendo a palavra b para o segundo andar
Mova para a esquerda para a palavra a
Adicionando 1 ao número X.
Vá para a direita para a palavra b.
Censo b para o 1º andar com adição simultânea de números a E b.T em conformidade. Comandos entre chaves adicionados ao sistema de comando
O estado final de todo o MT.
Deve-se notar que em todos os casos, no início do algoritmo, é necessário inserir uma verificação dos dados de origem para valores especiais (na maioria das vezes 0);
A composição MT pode ser usada para construir algoritmos complexos. Surge a questão: qualquer algoritmo pode ser implementado como uma composição de MT? A resposta a esta pergunta é dada por Tese de Turing , um análogo da tese de Church: todo algoritmo pode ser implementado usando máquinas de Turing e vice-versa, todo processo implementado por uma máquina de Turing é um algoritmo.
A tese de Turing não é um teorema; é impossível prová-la, porque contém o conceito informal " algoritmo" No entanto, muitos anos de prática matemática são uma confirmação confiável desta tese: durante 50 anos, nenhum algoritmo no sentido intuitivo foi encontrado que não pudesse ser implementado usando máquinas de Turing.
Objetivo do trabalho: adquirir habilidades práticas na escrita de algoritmos usando a composição de máquinas de Turing.
Informação teórica
Os métodos acima para descrever MT podem praticamente ser usados apenas para algoritmos simples, caso contrário a descrição se torna muito complicada. Máquinas de Turing para algoritmos complexos podem ser construídas usando MTs elementares já existentes, e esta construção é chamada composição MT.
Descrevemos 4 métodos principais de composição de MT:
Composição sequencial (superposição);
Composição paralela;
Ramificação
1. Composição sequencial de máquinas de Turing
Composição sequencial ou sobreposição Máquinas de Turing e 
E 
em alfabeto A, isso se chama carro M, calculando a função 
.
A composição sequencial é representada da seguinte forma:
e é designado 
ou 
.
2. Composição paralela de máquinas de Turing
Composição paralela
carros 
E 
, calculando funções de dicionário 
E 
em alfabetos A E EM, portanto, a máquina é chamada M, que avalia uma função de dicionário. Aqui está o sinal 
usado para separar palavras em composição MT paralela.
Composição paralela MT 
E 
é representado da seguinte forma:
e é designado: 
.
Na verdade, uma composição paralela de dois MTs recebe como entrada uma palavra composta por 2 palavras em alfabetos diferentes e produz uma palavra também composta por 2 palavras, ou seja, representa duas máquinas que trabalham simultaneamente e de forma independente. Para implementar uma composição paralela, é utilizada uma máquina com correia de dois andares.
A máquina de cinto de dois andares funciona da seguinte forma:
1) palavra 
reescrita no segundo andar da fita e apagada no primeiro,
2) calculado 
no primeiro andar,
3) calculado 
No segundo andar
4)
reescrito para o primeiro andar, possivelmente com um turno.
O comando MT com fita de dois andares é escrito da seguinte forma:
,
Onde 
– cartas escritas no primeiro e segundo andares, respectivamente. Vamos denotar os comprimentos das palavras 
, respectivamente, 
.
Vamos demonstrar o funcionamento de uma máquina de Turing com uma fita de dois andares. Em geral, comprimentos de palavras 
E 
não coincidem entre si, mas para simplificar a imagem assumimos que são iguais. Em seguida, a implementação dos pontos 1)-4) em um MT com fita de dois andares é realizada da seguinte forma:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Para implementar composição paralela n Máquinas de Turing são usadas n– fita de chão.
3. Ramificação ou transição condicional em composições de máquinas de Turing
Se as máquinas de Turing forem dadas 
E 
, calculando funções de dicionário 
E 
e o carro 
, que avalia algum predicado P(
)
com restauração (ou seja, sem apagar a palavra
),
então uma máquina de Turing pode ser construída para implementar ramificações 
, calculando a função:
A ramificação das máquinas de Turing nos diagramas de composição é representada a seguir:
e é designado 
, Aqui 
- o resultado da operação da máquina 
, assumindo os valores "1" se o predicado P(
)=
”verdadeiro”
e "0" se o predicado P(
)=
“falso”
,
– uma máquina de Turing que implementa a cópia da palavra de entrada 
.
4 . Ciclo na composição das máquinas de Turing
Ciclo na composição, o MT é implementado de acordo com os mesmos princípios da ramificação.
" Tchau P(
)=
”verdadeiro”
, completar 
»,
Onde
– palavra gravada antes da primeira execução 
e após a próxima execução .
Para representar o ciclo, introduzimos alguma notação, seja:
– uma máquina de Turing que implementa o cálculo de um predicado P(
)
;
–MT, que implementa a cópia da palavra de entrada 
;
–MT, executado em loop e implementando 
;
–MT, executado ao sair do loop e implementar 
.
Então, a composição cíclica das máquinas de Turing, ou ciclo, pode ser representada da seguinte forma:
Programação com composições de máquinas de Turing:
1) construção de diagramas de blocos de algoritmos complexos com tal nível de detalhe que seus blocos correspondem a MT elementares;
2) construção de MTs elementares que implementam blocos simples;
3) combinar MTs elementares em uma composição de MT.
Exemplo. Construa uma composição MT que implemente 
.
–Máquina de Turing, que implementa a cópia da palavra de entrada;
–MT, que implementa a função de definir o zero constante;
–MT, predicado de computação com restauração 
;
– MT que implementa a função de seleção 
-esse argumento de 
argumentos;
–MT, implementando a função de redução de argumentos 
por 1 em código unário (apaga o caractere mais à esquerda);
– MT, que realiza a adição de dois números em código unário.
Deve-se notar que em qualquer caso, é necessário verificar a exatidão dos dados de entrada no início da execução do algoritmo (por exemplo, a igualdade do argumento a 0 durante a divisão).
Figura 1.6
As seguintes notações são usadas na Figura 1.6:
T 1, T 2 - Máquinas de Turing;
ST 1, ST 2 - sistemas de comando das máquinas T 1 e T 2, respectivamente;
x - informações iniciais da máquina T 1;
T 1 (x) - resultado da operação da máquina T 1;
T 2 (T 1 (x)) - o resultado da operação da máquina T 2.
Como exemplo, considere a composição de duas máquinas, sendo que a primeira realiza uma operação de cópia e a segunda realiza a operação de adição de números em código unário. Um diagrama da combinação de máquinas e um exemplo de fita com os resultados obtidos são mostrados na Figura 1.7.
Figura 1.7
A composição mostrada na Figura 1.7 permite realizar a operação de duplicação de um número utilizando máquinas copiadoras e de adição já conhecidas. Assim, tendo composto algoritmos para máquinas de Turing para resolver um conjunto de operações específicas (por exemplo, operações aritméticas), composições de máquinas de Turing podem então ser compostas para resolver problemas mais complexos. Neste caso, o desenvolvimento de um algoritmo geral se resume à sua compilação a partir daquelas operações para as quais já são conhecidos algoritmos para execução em uma máquina de Turing. Esta abordagem é semelhante ao uso de procedimentos e funções em programação.
Porém, o uso da composição de máquinas pressupõe que sejam conhecidos os algoritmos para execução das operações elementares, a partir dos quais é composto o algoritmo geral. Portanto, ao resolver problemas arbitrários, esta abordagem não exclui a necessidade de compor novos algoritmos e, consequentemente, desenvolver máquinas de Turing com diferentes unidades de controle. É possível implementar qualquer algoritmo sem alterar a estrutura da unidade de controle usando uma máquina de Turing universal.
1.2.2.Máquina de Turing universal
Se alguma máquina de Turing for fornecida (ou seja, os alfabetos de sinais e estados de entrada, saída, a posição inicial da cabeça e o estado inicial da máquina são conhecidos, bem como uma tabela de operação da máquina e uma fita com informações iniciais ), então você pode realizar manualmente todas as transformações de informações passo a passo, para as quais esta máquina se destina. Na verdade, neste caso, é realizada uma simulação de uma máquina de Turing.
Ao analisar as operações que são realizadas na modelagem de uma máquina de Turing, pode-se estabelecer que a modelagem se resume a repetir as seguintes ações em cada etapa:
ÄLer um caractere da célula da fita sobre a qual a cabeça está localizada.
ÄProcure um comando na tabela de operação da máquina. A pesquisa é realizada com base no estado atual da máquina e no valor do símbolo lido.
ÄSelecionar o símbolo do comando que deve ser gravado na fita e gravá-lo.
ÄSelecione o símbolo de movimento da cabeça no comando e mova-o.
ÄSelecionar um novo estado da máquina no comando e alterar o estado atual para um novo. Isso é seguido por passar para a próxima etapa e repetir essas etapas.
|
|
 |
|||||
 |
|||||
Figura 1.8
A natureza dessas ações elementares é tal que todas elas podem ser realizadas usando alguma outra máquina de Turing, que simulará a operação da máquina original. A essência da modelagem é explicada na Figura 1.8.
Se a máquina T possui um sistema de comando ST e processa uma fita com a informação X, então seu funcionamento pode ser simulado por outra máquina U, que possui seu próprio sistema de comando SU. Para simular a entrada da máquina U, é necessário enviar não apenas uma fita com informações X , mas também o sistema de comando (mesa de trabalho) ST. Este sistema de comando pode ser gravado na mesma fita que as informações originais.
 |
Figura 1.9
Recurso importante máquina de modelagem é que seu sistema de comando SU (e, consequentemente, a estrutura da unidade de controle) não depende do algoritmo de operação da máquina simulada T. Uma máquina de Turing que pode simular a operação de qualquer outra máquina de Turing é chamada de universal. Uma variante da estrutura de uma máquina de Turing universal (UMT) é mostrada na Figura 1.9.
A fita UMT é dividida em três zonas: uma zona de dados, uma zona de modo e uma zona de comando.
A zona de dados contém as informações iniciais que devem ser processadas pela máquina de Turing simulada. Na mesma zona são registrados os resultados da operação UMT.
A zona de modo registra o estado atual Qt e o símbolo de entrada atual Xt, que é lido da célula da zona de dados em um determinado ciclo.
A zona de comando contém o sistema de comando da máquina simulada. Os comandos são organizados em grupos. O primeiro grupo inclui comandos começando com o símbolo Q 0, o segundo - com o símbolo Q 1, etc. Dentro de cada grupo, os comandos são ordenados pelo valor do símbolo X t . Assim, os comandos na fita ficam localizados como estão na tabela de operação da máquina simulada.
A leitura das informações da fita e a gravação na fita são realizadas usando três cabeçotes: G d - cabeçote de dados, G r - cabeçote de modo, G k - cabeçote de comando. Cada cabeça pode se mover ao longo de sua própria zona do cinto.
Antes de iniciar a operação UMT, as informações relevantes devem ser gravadas em cada zona da fita. As cabeças devem ser instaladas acima do símbolo esquerdo em cada zona.
O funcionamento do UMT ocorre em ciclos, em cada ciclo é simulada a execução de um comando da máquina simulada. O gráfico de operação do UMT é mostrado na Figura 1.10.
 |
Figura 1.10
As seguintes notações são usadas na Figura 1.10:
Q G para P (G para L, G r P, G r L, G d P, G d L) - movendo uma das cabeças
direita ou esquerda;
Q (G k), (G d), (G r) - informação lida por um dos chefes;
Q (G k) à (G r) - lendo dados pelo cabeçote de comando e escrevendo esses dados
transferido usando o cabeçote de modo para a zona de modo de fita;
Q a é uma variável auxiliar que assume o valor 1, es-
se os caracteres lidos pelas cabeças Гк e Гр coincidem;
Q in é uma variável auxiliar que assume o valor 1, es-
se os símbolos dos estados atual (Q t) e final (Q z)
Q p - um sinal que assume o valor 1 se o comando head quando
mover-se para a esquerda ultrapassou os limites da zona de comando;
Em cada ciclo de operação do UMT são realizadas as seguintes etapas:
você procura por zona de comando;
você procura um time na zona;
você simulação de execução de comando.
A busca pela zona de comando começa comparando o estado atual Qt da zona de modo com o estado Qi registrado no início do primeiro comando na zona de comando. Se esses estados não forem iguais, o comando head se move para o início do próximo comando, para o qual cinco passos do head são executados para a direita (estados U 0 - U 4). Se os símbolos Qt e Qi corresponderem, o cabeçalho de comando estará no início do primeiro comando da zona desejada. A seguir, inicia-se a busca por um comando correspondente aos símbolos Q t e X t da zona de modo. Para fazer isso, o cabeçalho do modo é colocado acima do símbolo X t da zona de modo e o cabeçalho do comando é colocado acima do símbolo X i no comando atual.
Procurar um comando em uma zona é semelhante a procurar uma zona de comando. Neste caso, o comando se move cinco passos para a direita (indica U 5 - U 9) até que os caracteres X t e X i sejam comparados.
A execução do comando (estados U 10 - U 17) começa com o movimento do cabeçalho do comando um passo para a direita, após o qual o símbolo Y t lido do comando encontrado é gravado na zona de dados usando o cabeçalho de dados em vez do leia anteriormente o símbolo X t . Após a próxima etapa do cabeçote de comando para a direita, o símbolo de movimento do cabeçote de dados (Y d) é lido do comando encontrado e o cabeçote de dados é movido de acordo com este símbolo (R, L). Abaixo dele está o próximo símbolo processado (X t +1), que, usando o cabeçalho de modo, é gravado na zona de modo para preparar o próximo ciclo. Em seguida, os cabeçotes de comando e modo são instalados para que o próximo estado Q t +1 (estados
U 14, U 15). No estado U 16, a condição para encerrar a solução é verificada. Se o símbolo do próximo estado não coincidir com o símbolo do estado final da máquina modelada (Q z), então a solução do problema não está concluída e no estado U 17 o cabeçote de comando se move para sua posição original ( ao início do primeiro comando da primeira zona). Neste caso, o UMT está pronto para realizar o próximo ciclo, ou seja, para simular a execução do próximo comando.
Quando os símbolos Q t e Q z coincidem, a solução do problema termina e o UMT entra no estado final U z .
Ao analisar o processo de operação do UMT, pode-se tirar uma conclusão importante de que o algoritmo de operação do UMT não depende de qual problema específico a máquina de Turing simulada resolve. Portanto, a estrutura da unidade de controle UMT não muda ao modelar máquinas diferentes, ou seja, não depende das tarefas a serem resolvidas. É por isso que o UMT é verdadeiramente uma máquina universal, com a qual você pode executar qualquer algoritmo sem alterar sua estrutura.
Como o processo de seleção do próximo comando UMT e sua execução está associado à enumeração sequencial das células da fita, a solução de problemas no UMT requer muito tempo. Portanto, uma máquina de Turing, inclusive universal, nunca foi construída, mas não é difícil ver nela um análogo dos computadores modernos. Assim, o sistema de comando na zona de comando UMT é semelhante a um programa de máquina, com um par de símbolos Qt e Xt desempenhando a função de endereço do comando de máquina.
No entanto, a máquina de Turing é uma ferramenta bastante conveniente para descrever algoritmos e é amplamente utilizada na teoria dos algoritmos.
Perguntas de controle
ü1.Qual é a composição das máquinas de Turing?
ü2.Para que é utilizada a composição das máquinas de Turing?
ü3.Uma máquina de Turing pode simular a operação de outra máquina?
Turing?
ü4.Quais ações são executadas neste caso?
ü5.Explicar a estrutura da máquina de Turing universal?
ü6.Quais informações são gravadas nas áreas da fita UMT?
ü7.Qual é o sistema de comando de uma máquina de Turing?
ü8.Quais etapas contém o ciclo de trabalho UMT?
ü9.Explicar o conteúdo da etapa “procurar zona de comando”.
ü10.Explicar o conteúdo da etapa “execução do comando”.
ü11.Quais recursos o processo de processamento de informações usando
O diagrama se parece com um gráfico:
Valor da tabela de máquinas
tabela 1
Algumas operações em máquinas de Turing
A operação de uma máquina de Turing é completamente determinada pelos dados de entrada e pelo sistema de comando. Contudo, para compreender como uma determinada máquina resolve um problema, via de regra, há necessidade de explicações significativas do tipo que foram dadas para a máquina. 
. Muitas vezes, essas explicações podem ser tornadas mais formais e precisas usando diagramas de blocos e algumas operações da máquina de Turing. Lembre-se de que a composição das funções 
E 
função chamada 
, que é obtido ao usar 
para o resultado do cálculo 
. A fim de 
foi determinado neste 
, é necessário e suficiente para 
foi determinado em 
, A 
foi determinado em 
.
Teorema 1. Se 
E 
são Turing computáveis, então sua composição 
também é Turing computável.
Deixar 
- uma máquina que calcula 
, A 
- uma máquina que calcula 
, e o conjunto de seus estados, respectivamente 
E 
.
Vamos construir um diagrama de transição de carro 
de diagramas 
E 
da seguinte forma: identificamos o vértice inicial 
diagramas de máquina 
com vértice terminal 
diagramas de máquina 
(para sistemas de comando isto é equivalente ao fato de que o sistema de comando 
atribuído ao sistema de comando 
e para isso 
Em equipes 
substituir com 
). Obtemos um diagrama com ( 
) afirma. Estado inicial 
vamos anunciar 
e final 
. Para simplificar a notação, assumiremos 
E 
funções numéricas de uma variável.
Deixar 
determinado. Então 
E
. Carro 
passará pela mesma sequência de configurações com a diferença que em vez de 
acontecerá em 
. Esta configuração é a configuração inicial padrão para a máquina 
, É por isso 
. Mas como todas as equipes 
contido em 
, Que
e portanto 
. Se 
não está definido, então 
ou 
não para e portanto o carro 
não vai parar. Então o carro 
calcula 
.
A máquina assim construída 
chamaremos isso de composição de máquinas 
E 
e designar 
(ou 
(
)), e também representado em um diagrama de blocos:
Composição das máquinas de Turing
Deixar 
,
,
- três máquinas de Turing com o mesmo alfabeto externo 
, com alfabetos de estados internos 
,
,
e programas 
,
,
respectivamente.
Composição
carros 
E 
chamado carroT
, cujo programa é a união de conjuntos 
E
, Onde 
denota um conjunto de comandos recebidos de 
substituindo tudo 
sobre 
.
Ramificação das máquinas de Turing
Máquinas de ramificação
,
,
Por 
, simbolicamente
chamado carroT
, cujo programa é obtido da seguinte forma: de 
equipes estão excluídas 
E 
Para 
, o conjunto resultante será chamado 
; Então.
Máquina de Turing universal
O sistema de comando de uma máquina de Turing pode ser interpretado tanto como uma descrição da operação de um dispositivo específico quanto como um programa, ou seja, um conjunto de instruções que levam claramente a um resultado. Ao analisar exemplos, a segunda interpretação é involuntariamente aceita, ou seja, agimos como um mecanismo que pode reproduzir o trabalho de qualquer máquina de Turing. A confiança de que todos farão isso da mesma maneira (se não cometerem erros, o que, aliás, também é assumido quando uma máquina de Turing opera) é essencialmente confiança na existência de um algoritmo para reproduzir a operação de uma máquina de Turing. máquina de acordo com um determinado programa, ou seja, sistema de comando. Na verdade, não é difícil dar uma descrição verbal de tal algoritmo. Sua ação principal se repete ciclicamente e consiste no seguinte: “Para a configuração atual 
encontre o comando com o lado esquerdo no sistema de comando 
. Se o lado direito deste comando estiver no formato 
, em seguida, substitua na configuração atual 
sobre 
(acontece que a configuração 
); se o lado direito tiver a forma 
, então substitua 
sobre 
. Uma descrição verbal do algoritmo pode ser imprecisa e precisa ser formalizada. Como a máquina de Turing está sendo atualmente discutida como uma formalização do conceito de algoritmo, é natural colocar o problema de construir uma máquina de Turing que implemente o algoritmo de reprodução descrito. Para máquinas de Turing que calculam funções de uma variável, a formulação deste problema é a seguinte: construir uma máquina de Turing 
, calculando uma função de duas variáveis e tal que para qualquer máquina 
com sistema de comando 
, Se 
definido (ou seja, se a máquina 
pára nos dados iniciais 
) E 
não para se 
não para. Chamaremos qualquer máquina que possua esta propriedade máquina de Turing universal. Não é difícil generalizar esta formulação para qualquer número de variáveis.
O primeiro problema que surge ao construir uma máquina universal 
, é devido ao fato de que 
como qualquer outra máquina de Turing, deve ter um alfabeto fixo 
e um conjunto fixo de estados 
. Portanto, o sistema de comando 
e os dados iniciais de uma máquina arbitrária 
você não pode simplesmente transferi-lo para a correia da máquina 
(sempre há um carro 
, alfabetos 
E 
que é superior em poder 
E 
ou simplesmente não coincidem com ele).
A solução é ter os personagens de 
E 
codificado por símbolos no alfabeto 
. Deixar 
,
. Sempre assumiremos que 
E 
(estes dois símbolos estão sempre no alfabeto de qualquer máquina que trabalhe com números). Vamos denotar os códigos 
E 
através 
E 
e defini-los como 
; para qualquer outra pessoa 
; para o estado final 
, Se 
. Código 
para este carro 
sempre tem um comprimento (formato) 
, e o código 
- formato 
. Símbolos 
,
vamos entrar 
, ou seja 
,
,
. Código do caractere 
, formado pelos códigos dos caracteres que compõem esta palavra, denotamos 
. Assim, o refinamento final da formulação do problema de uma máquina universal 
resume-se ao fato de que para qualquer carro 
e palavras 
alfabeto 
.
A existência de uma máquina de Turing universal significa que o sistema de instrução 
qualquer carro 
pode ser interpretado de duas maneiras: ou como uma descrição do funcionamento do dispositivo original 
, ou como um programa para uma máquina universal 
. Para um engenheiro moderno que projeta um sistema de controle, essa circunstância é natural. Ele sabe muito bem que qualquer algoritmo de controle pode ser implementado em hardware - construindo um circuito apropriado, ou em software - escrevendo um programa de computador de controle universal.
No entanto, é importante perceber que a ideia de um dispositivo algorítmico universal não tem nenhuma relação com o desenvolvimento de meios técnicos modernos para sua implementação (eletrônica, física sólido etc.) e não é um fato técnico, mas matemático, descrito em termos matemáticos abstratos, independentes de meios técnicos e, além disso, baseado em um número extremamente pequeno de conceitos iniciais muito elementares. É característico que os trabalhos fundamentais sobre a teoria dos algoritmos (em particular, o trabalho de Turing) tenham surgido na década de 30, antes da criação dos computadores modernos.
Esta dupla interpretação preserva no nível abstrato os principais prós e contras das duas opções de implementação de engenharia. Carro específico 
funciona muito mais rápido; além disso, o dispositivo de controle da máquina 
bastante complicado (ou seja, o número de estados e comandos é grande). Contudo, seu valor é constante e, uma vez construído, é adequado para implementar algoritmos arbitrariamente grandes. Tudo o que é necessário é um grande volume de fita, que é naturalmente considerada mais barata e de construção mais simples do que o dispositivo de controle. Além disso, ao alterar o algoritmo, você não precisará construir novos dispositivos, basta escrever um novo programa;