Computabilidade

Computabilidade
Máquinas de Turing e Computabilidade
Máquina de Estados Finitos Uma Máquina de Estados Finitos é um Autômato Finito que a cada transição de estados, tem a capacidade de informar uma saída. Ao contrário do autômato, que só consome entradas, a máquina de estados finitos pode produzir saídas. A notação para uma máquina de estados finitos é idêntica ao do autômato, porém com a informação de qual é a saída para cada uma das transições. Observe que uma transição é definida pela dupla estado + entrada. Desta maneira, podemos verificar que um Autômato Finito é um caso particular de uma Máquina de Estado Finito, onde as saídas são idênticas as entradas. Sabemos que um autômato finito é capaz de reconhecer uma linguagem regular. Na realidade, uma linguagem regular é uma linguagem que pode ser gerada por uma gramática regular, desta maneira uma máquina de estados finitos é capaz de reconhecer as linguagens geradas por uma gramática regular. Não iremos apresentar um modelo de uma máquina de estados finitos pois elas são essencialmente iguais ao comportamento de autômatos finitos, assunto que já foi bastante discutido. Máquina de Turing Introduzida por Alan Turing em 1936, Máquinas de Turing são umas das principais abstrações usadas na moderna Teoria da Computabilidade, que é o estudo do que os computadores são capazes ou não de fazer. Uma máquina de Turing é uma representação de um simples tipo de computador, cujas operações estão limitadas a ler e escrever símbolos em uma fita e mover através desta para a direita ou esquerda. A fita é composta de um número infinito de setores, onde cada um deles pode ser preenchido com no máximo um símbolo. Uma Máquina de Turing poderá ler ou escrever em apenas um destes setores, justamente aquele que está sendo apontado por sua cabeça de leitura. A figura abaixo mostra a fita infinita de uma Máquina de Turing, contendo uma seqüência de símbolos 1 s, Os e bs, onde a letra b representa espaço vazio. O retângulo mais espesso