Máquina de Turin

Prévia do material em texto

Faculdade Anhanguera Unidade III
Thiago Henrique Silva; RA: 1566241441
Victor F. Gonzalez; RA: 1575153002
Disciplina: Análise de Comp. e Complexid. de Algoritmos
Curso: Ciência da Computação
 Professora: Regina Fedozzi
Turma: 4° Semestre 
Turno: Noturno
Índice 
Introdução aos conceitos necessários para a compreensão da noção -------------------- 1
de computabilidade.
Máquinas de Turing e elementos de computabilidade ------------------------------------ 2
Máquinas de Turing determinísticas ---------------------------------------------------------2
A tese de Church-Turing -----------------------------------------------------------------------3
Referências -------------------------------------------------------------------------------------- 4
A TEORIA DA COMPUTABILIDADE
Também chamada de teoria da recursão, é um ramo da lógica matemática que foi originado na década de 30 com o estudo das funções computáveis e dos graus de Turing. O ramo se estendeu e passou a incluir o estudo generalizado da computabilidade e definibilidade. Nessas áreas, a teoria da recursão sobrepõe-se à teoria da prova e teoria efetiva de descrição dos conjuntos. As questões básicas envolvidas na teoria da recursão são " O que significa para uma função (N->N) ser computável?" E "Como funções não-computáveis são classificadas em uma teoria baseada nos seus níveis de não-computabilidade?". As respostas para estas perguntas levaram a uma rica teoria que ainda está sendo estudada atualmente. O ramo se aproximou também com relação à ciência da computação. Estudiosos da recursão em lógica matemática frequentemente estudam a teoria da computabilidade relativa, noções de redutibilidade e estruturas de grau descritas neste artigo. Isto contrasta com a teoria das hierarquias subrecursivas, métodos formais e linguagens formais que são comuns no estudo da teoria da computabilidade na ciência da computação. Existe uma sobreposição considerável no conhecimento e nos métodos entre estas duas comunidades de pesquisa. No entanto, não existe uma grande separação entre elas.
A máquina computacional universal, inicialmente apresentada por Alan Turing em 1936, é considerada o modelo lógico de funcionamento em que se baseiam todas as implementações físicas de computadores. Composta conceitualmente por uma fita dividida em células e um cabeçote que a percorre de acordo com regras pré-estabelecida; a Máquina de Turing, como é comumente chamada, é uma máquina de estados finitos que possui poder de expressão computacional turing-completo – ou seja, realiza qualquer operação que um programa de computador pode executar (dado tempo infinito). A Teoria da Computação aborda estes conceitos relativos à Máquina de Turing como parte dos conhecimentos necessários para a compreensão da tese de Turing-Church e teoria da computabilidade. Visando auxiliar os acadêmicos nesse processo de aprendizagem, foi planejada a produção de uma ferramenta didática demonstrativa do funcionamento da Máquina de Turing, com foco na interatividade e capacidade de análise de sua execução.
A forma principal de computabilidade estudada na teoria da recursão foi introduzida por Turing. Um conjunto de números naturais é dito ser um conjunto computável (também chamado de decidível, revursivo ou conjunto Turing computável) se existe uma máquina de Turing que, dado um número n, para com saída 1 se n está no conjunto e para com saída 0 se n não está no conjunto. Uma função f dos números naturais para eles mesmos é uma função recursiva ou (Turing) computável se existe uma máquina de Turing que, com entrada n, para e retorna f(n). O uso de máquinas de Turing aqui não é necessário: existem muitos outros modelos de computação que têm o mesmo poder de computação que máquinas de Turing; por exemplo as funções μ-recursivas obtidas da recursão primitiva e do operador μ.
												1
MÁQUINAS DE TURING
Definição 
A Máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing, muitos anos antes de existirem os modernos computadores digitais. Num sentido preciso, é um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos do seu funcionamento (memória, estados e transições) e não à sua implementação física. Numa máquina de Turing pode-se modelar qualquer computador digital.
Estados
Uma máquina de Turing é uma máquina de estados finitos (alguns deles iniciais ou finais), a semelhança dos autômatos. A diferença reside no seguinte: a fita de entrada é também de saída. Ou seja, dá para ler e para escrever. Fita = memória. Tem um início (a esquerda), mas não tem fim (infinita a direita). Com tal, equipamos a m´máquina com a possibilidade de se deslocar na fita (para a direita ou para a esquerda, quando possível).
Os autômatos com pilha têm acesso a uma memória potencialmente infinita, mas mesmo assim não conseguem reconhecer linguagens como a, b, c. Mas parece simples reconhecer esta linguagem por um processo ”baseado em estados”:
Máquinas de Turing deterministas. 
Se a tabela de ação tem no máximo 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 tabela de ação contém 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 (MTND ou MTN).
							2
A TESE DE CHURCH-TURING
A Tese de Church-Turing consiste em dizer que todo “problema” pode ser computabilizado e solucionado por um algoritmo, desde que este tenha um número finito de etapas para ser solucionado na Máquina de Turing.
3
Referências:
https://pt.wikipedia.org/wiki/Tese_de_Church-Turing
 
https://www.di.ubi.pt/~desousa/2015-2016/TC/turing.pdf
http://revistas.rcaap.pt/boletimspm/article/view/3870
https://pt.wikipedia.org/wiki/M%C3%A1quina_de_Turing#M.C3.A1quinas_de_Turing_determin.C3.ADsticas_e_n.C3.A3o-determin.C3.ADsticas
https://pt.wikipedia.org/wiki/Teoria_da_computa%C3%A7%C3%A3o
4