Turing

GRUPO:

HUGO IMPERIANO NÒBREGA LUCAS LUCENA GAMBARRA

10711467 10711005

01 QUESTÃO. c) M=<∑, Γ, S, so, δ> = <{a, b}, {#, Y, N}, {so, s1, s2, s3, s4 }, so, δ>. ∑ Γ S so h δ

= alfabeto de entrada = alfabeto auxiliar, contendo # (símbolo branco) = conjunto finito e não vazio de estados = estado inicial (so ∈ S) = estado de parada (halt), onde h ∉ S = função [determinística] de transição de estados δ: S x (∑ U Γ) → (S U {h}) x (∑ U Γ U {L, R})

δ é dado por: δ( so , a ) = < s1 , R> δ( so , b) = < s3 , R> δ( so , # ) = < h ,Y> δ( s1 , a ) = < s2 , R> δ( s1 , # ) = < h , N> δ( s1 , b ) = < h , N> δ( s2 , a ) = < so , R> δ( s2 , b ) = < h , N> δ( s2 , # ) = < h , N> δ( s3 , b ) = < s4 , R> δ( s3 , a ) = < h , N> δ( s3 , # ) = < h , n> δ( s4 , b ) = < so , R> δ( s4 , a ) = < h , N>

d) M=<∑, Γ, S, so, δ> = <{a, b,c}, {#, Y, N,X}, {so, s2, s3, s4, s5, s6}, so, δ>. ∑ Γ S so h δ δ é dado por:

= alfabeto de entrada = alfabeto auxiliar, contendo # (símbolo branco) = conjunto finito e não vazio de estados = estado inicial (so ∈ S) = estado de parada (halt), onde h ∉ S = função [determinística] de transição de estados δ: S x (∑ U Γ) → (S U {h}) x (∑ U Γ U {L, R})

δ( s0 , a ) = < s2 , X> δ( s0 , b ) = < s1 , R> δ( s0 , c ) = < s1 , R> δ( s0 , X ) = < s0 , R> δ( s0 , # ) = < h , Y> δ( s1 , a ) = < s2 , X> δ( s1 , b ) = < s1 , R>

δ( s1 , c ) = < s1 , R> δ( s1 , X ) = < s1 , R> δ( s1 , # ) = < h , N> δ( s2 , a ) = < s2 , L> δ( s2 , b ) = < s2 , L> δ( s2 , c ) = < s2 , L> δ( s2 , X ) = < s2 , L> δ( s2 , # ) = < s3, R> δ( s3 , a ) = < s3 , R> δ( s3 , b ) = < s4, X> δ( s3 , c ) = < s3 , R> δ( s3 , X ) = < s3 , R> δ( s3 , # ) = < h , N> δ( s4 , a ) = < s4, L> δ( s4 , b ) = < s4, L> δ( s4 , c ) = < s4, L> δ( s4 , X ) = < s4 , L> δ( s4 , # ) = < s5 , R> δ( s5 , a ) = < s5 , R> δ( s5 , b ) = < s5, R> δ( s5 , c ) = < s6 , X> δ( s5 , X ) = < s5 , R> δ( s5 , # ) = < h , N> δ( s6 , a ) = < s6, L> δ( s6 , b ) = < s6, L> δ( s6 , c ) = < s6, L> δ( s6 , X ) = < s6 , L> δ( s6 , # ) = < s0 , R>

Ilustração 1 A figura parece com esta, mas tem que substituir < > por #

02 Questão. Para o item (c) da questão 1 temos o seguinte grafo:

Como convenção para a Máquina de Turing utilizada acima, adotamos o seguinte: ° Podemos executar duas ações de uma só vez (escrita e movimentação) ° Temos três cabeças que começam nas posições 0, 1 e 2 respectivamente (considerando a posição 0 como a posição inicial de uma MT simples) ° Aquilo que não é levado em conta é considerado como uma rejeição da palavra (a máquina finalizaria no estado N)

Para o item (d) da questão 1 temos o seguinte grafo:

Como convenção para a Máquina de Turing utilizada acima, adotamos o seguinte: ° Podemos executar apenas uma ação por vez (escrita ou movimentação) ° Temos três cabeças que começam na mesma posição (a posição inicial de uma MT simples) ° Aquilo que não é levado em conta é considerado como uma rejeição da palavra (a máquina finalizaria no estado N) Explicação adicional: ° Estado S0: Inicialmente, no estado S0, teríamos todas as cabeças apontando para aaa, bbb, ou ccc (### finalizaria no estado YES), pois começam na mesma posição. Logo, caso fosse bbb ou ccc, a primeira cabeça andaria pra direita e a segunda e terceira conservariam o que esta escrito sem mudar de posição, permanecendo ainda no estado S0. Isso continuaria até que fosse achado um abb ou um acc ( o que depende do que foi encontrado na posição inicial ). Assim seria marcado um x no lugar do a e cc ou bb se manteriam e passaríamos para o estado S1. Caso encontrássemos aaa de cara, escreveríamos xxx, pois todas as cabeças apontariam para o mesmo a (todas as cabeças começam na mesma posição) e passaríamos para o estado S1. Quando passamos do estado S2 para o S0, todas as cabeças apontam para xxx (não estão mais na mesma posição). Teríamos então o seguinte procedimento, a primeira cabeça andaria para a direita e as outras escreveriam x onde já existe, permanecendo na mesma posição. Poderíamos encontrar axx, bxx ou cxx. No caso de bxx ou cxx a primeira cabeça andaria novamente para direita e o procedimento se repetiria até que fosse encontrado um

axx. Sendo encontrado axx escrevemos um xxx nas três cabeças, alterando apenas o a e passaríamos para o estado S1. °

Estado S1: A primeira vez que o estado S1 fosse utilizado, teríamos xxx, xbb, ou xcc. Caso tivéssemos xbb, isso significaria que a segunda e a terceira cabeça apontavam para o mesmo b (mesma posição, pois elas ainda não teriam se movido), logo, escreveríamos xxx no lugar de xbb, alterando apenas o b que é apontado pela segunda e terceira cabeças e passaríamos para o estado S2. Caso tivéssemos xxx ou xcc, a segunda cabeça iria se mover para direita e o processo se repitiria até que encontrássemos xbx ou xbc, então escreveríamos xxx ou xxc em cima de xbx ou xbc, respectivamente, e passaríamos para o estado S2. Caso não fosse a primeira vez em que o estado S1 estivesse sendo utilizado, cairíamos sem sombra de dúvidas, na situação xxx, pois em S0 as cabeças apontariam pra xxx (sendo os três distintos) a primeira cabeça acharia um a, ficando assim axx (as outas duas cabeças permaneceriam imóveis) e sendo sobrescrito xxx e passando para S1. Teríamos então a mesma situação descrita para xxx no final do parágrafo anterior. °

Estado S2: No estado S2 teríamos apenas duas possibilidades para o conteúdo das células apontadas pelas cabeças. Seriam: xxc ou xxx, pois caso a terceira cabeça apontasse inicialmente para um a ou um b, já teria sido sobrescrito no estado S0 ou S1, respectivamente, (pois a primeira e a segunda cabeças iniciariam apontando para a mesma posição). A primeira, xxc, poderia ocorrer apenas na primeira vez em que a máquina estivesse neste estado, e essa possibilidade poderia ocorrer somente se a primeira posição da fita contivesse um c. Essa possibilidade seria então sobrescrita por xxx, voltando para o estado S0. Caso tivéssemos xxx (poderia ocorrer na primeira ou nas demais vezes em que a máquina estivesse no estado S2), a terceira cabeça andaria para a direita (as demais cabeças não andariam, apenas sobrescreveriam x, o que não iria alterar nada) e repetiria o procedimento até que fosse encontrado xxc, procedendo da maneira como foi dito no final do parágrafo anterior. °

Estado S3: No estado S3, todas as cabeças apontam para xxx (não estão mais na mesma posição). Teríamos então o seguinte procedimento, a primeira cabeça andaria para a direita e as outras escreveriam x onde já existe, permanecendo na mesma posição. Poderíamos encontrar axx, bxx ou cxx. No caso de bxx ou cxx a primeira cabeça andaria novamente para direita e o procedimento se repetiria até que fosse encontrado um axx. Sendo encontrado axx escrevemos um xxx nas três cabeças, alterando apenas o a e passaríamos para o estado S1. Caso seja encontrado um # na cabeça um, quando a movermos para a direita, passa-se para o estado S4. °

Estado S4: No estado S4 se achássemos um # na segunda cabeça quando a movêssemos para direita, passaríamos para o estado S5.

°

Estado S5: No estado S5, se achássemos um # na terceira cabeça quando a movêssemos para direita, teríamos então ###, o que significaria que não há mais nenhum a, b ou c. Então iríamos para o estado de parada YES.

Conclusão: O funcionamento dessa máquina é o seguinte. As três começam da mesma posição inicial. A primeira irá andar até achar um a e escreverá x no seu lugar. Então a segunda cabeça andará até achar um b e escreverá um x no seu lugar. Então a terceira cabeça cabeça andará até encontrar um c e escreverá um x no seu lugar. O procedimento irá se repetir até que aconteça algo que não foi previsto (o que significa que não temos o mesmo número de a´s, b´s e c´s) e rejeita a palavra ou que seja encontrado ### o que causaria aceitação da palavra. Observe que não precisamos voltar as cabeças de posição, pois a primeira procurar o primeiro a e ficará parada nessa posição até que um c seja encontrado pela terceira cabeça, o que só ocorrerá quando a segunda irá procurar e encontrar um b. Dessa forma as 1º, 2º e 3º cabeças não passaram despercebidas por suas letras. Observe também que caso o 03 Questão. Turing percebeu que os cálculos mentais são constituídos por operações para transformar números em uma série de estados intermediários que alternam de acordo regras fixas, até encontrar uma resposta, onde se usam anotações para não perder os estados. Inicialmente, a folha de papel contém somente os dados iniciais do problema. O trabalho da pessoa pode ser resumido em seqüências de operações simples como segue: Noção Intuitiva. • ler um símbolo de um quadrado; • alterar um símbolo em um quadrado; • mover os olhos para outro quadrado; • quando é encontrada alguma representação satisfatória para a resposta desejada, a pessoa termina seus cálculos. As regras da matemática exigem definições mais rígidas que aquelas descritas nas discussões metafísicas sobre os estados da mente humana, e ele concentrou-se na definição desses estados de tal maneira que fossem claros e sem ambigüidades, para que tais definições pudessem ser usadas para comandar as operações da máquina. A máquina teórica de Turing estabelece tanto um exemplo da sua teoria da computação quanto uma prova de que certos tipos de máquinas computacionais poderiam ser construídas. Efetivamente, uma Máquina de Turing Universal, exceto pela velocidade, que depende do hardware, pode emular qualquer computador atual, desde os supercomputadores até os computadores pessoais, com suas complexas estruturas e poderosas capacidades computacionais, desde que não importasse o tempo gasto. Ele provou que para qualquer procedimento computacional bem definido, uma Máquina de Turing Universal é capaz de simular um processo mecânico que execute tais procedimentos. De um ponto de vista teórico, a importância da Máquina de Turing está no fato de que ela representa um objeto matemático formal. Através dela, pela primeira vez, se deu uma boa definição do que significa computar algo. E isso levanta a questão sobre o que exatamente pode ser computado com tal dispositivo matemático. Noção como Máquina Fita Usada simultaneamente como dispositivo de entrada, de saída e de memória de trabalho; É finita à esquerda e infinita - tão grande quanto necessário - à direita, sendo dividida em células, cada uma das quais armazenando um símbolo. Os símbolos podem pertencer: ⇒ ao alfabeto de entrada; ⇒ ao alfabeto auxiliar; ⇒ # branco;

⇒ marcador de início de fita Inicialmente, a palavra a ser processada ocupa as células mais à esquerda, após o marcador de início de fita, ficando as demais com branco.. Unidade de Controle Reflete o estado corrente da máquina, possui um número finito e predefinido de estados. Possui uma unidade de leitura e gravação (cabeça da fita), a qual acessa uma célula da fita de cada vez. Após a leitura/gravação move-se para a direita ou para a esquerda. Programa ou Função de Transição O programa comanda as leituras e gravações, o sentido de movimento da cabeça e define o estado da máquina. Programa é uma função que, dependendo do estado corrente da máquina e do símbolo lido, determina o símbolo a ser gravado, o sentido do movimento da cabeça e o novo estado.

Questão 04. Máquina de Turing de várias fitas: Suponha que k ≥ 1 seja um inteiro. Uma máquina de Turing de k fitas é um quíntuplo (K, Σ, δ, s, H), onde K, Σ, s e H são as definições da máquina de Turing normal e δ, a função de transição, é a função de (K – H) * Σ^ K para K * (Σ U{←→})^ K . Isto é, para cada estado q e cada k tuplas de símbolos de fita (a1, ..., ak), δ(q, (a1, ..., ak)) = (p, ((b1, ..., bk)), onde p é o novo estado e bj é, intuitivamente, a ação assumida por M na fita j. Temos que se aj = ► para algum j ≤ k, então bj = →. A computação ocorre em todas as k fitas de uma máquina de Turing de k fitas. Correspondentemente, uma configuração de tal máquina deve incluir informações sobre todas as fitas. Correspondência:

Suponha que M = (K, Σ, δ, s, H) seja uma máquina de Turing de k fitas, para algum k ≥ 1. Então, há uma máquina de Turing padrão M´= (K´, Σ´, δ´, s´, H´), onde Σ⊆Σ´, tal que vale o seguinte: para qualquer string de entrada x∈Σ*, M , na entrada x, pára na saída y da primeira fita, se, e somente se, M´, na entrada x, parar no mesmo estado de parada e com a mesma saída y em sua fita. Além disso, se M pára na entrada x, após t passos, então M pára na entrada x após um número de passos, que é O(t* ( |x| + t) ). FITA INFINITA NAS DUAS VIAS Suponha agora uma máquina que tenha uma fita que é infinita em ambas as direções. Todos os quadros são inicialmente espaços em branco, exceto aqueles contendo a entrada: a cabeça da fica inicialmente, digamos, à esquerda da entrada. Não é difícil ver que, como ocorre com fitas múltiplas, fitas infinitas de duas

vias não acrescentam poder substancial às máquinas de Turing. Uma fita infinita de duas vias pode ser facilmente simulada por uma máquina de duas fitas: uma fita sempre contém a parte da fita à direita do quadro que contém o primeiro símbolo de entrada e a outra contém a parte da fita à esquerda dessa ao inverso. A máquina de duas fitas, por sua vez, pode ser simulada por uma máquina de Turing padrão(como foi visto acima). De fato, na simulação precisamos levar apenas um tempo linear, em vez de um tempo quadrático, já que, a cada passo, somente uma das trilhas está ativa. Seria desnecessário dizer, mas as máquinas com várias fitas infinitas de duas vias também podem ser simuladas do mesmo modo.