COMPUTABILIDADE
Entende-se
por computabilidade como
a habilidade de resolver problemas de forma efetiva. Números reais cuja a
expansão decimal pode ser calculada em tempo finito, através de recursos
finitos termo proposto por Alan Turing (1936). A
tese de Church-Turing, que afirma que qualquer função que é computável por um
algoritmo é uma função computável. Sabe-se que nem todos os problemas podem ser
resolvidos através do computador (teorema da incompletude, Godel 1931). Por
mais extenso que seja um programa só terá utilidade se este for finito podendo
assim apresentar a solução para um determinado problema.
Compreende-se
que a maquina de turing consiste em fita que é divida em
células, a onde cada celula contem um simbolo de algum alfabeto finito, o
alfabeto comtem um simbolo especial branco e/ou mais simbolos adicionais. Um
cabeçote que pode ler e escrever simbolos na fita e se move para a esquerda e para
a direita.
Contem-se também um
registrador de estados que armazena o estado da maquina, o numero de estado
diferente é sempre finito e ha tambem um estado especial tambem chamado de
estado inicial com o qual o registrador e inicializado. Pode-se perceber que a
função de transição por sua vez diz a maquina qual simbolo escrever, para onde
movera o cabeçote( direita/esquerda ) e qual sera o seu novo estado, não
havendo mas entrada a máquina para.
MÁQUINA DE
TURING DETERMINÍSTICA
Entende-se por máquina de
Turing determinística aquela que possui uma função de transição que, dado um
estado e um símbolo na posição de execução da fita, especifica três coisas: um
novo símbolo a ser escrito na posição de execução da fita, a direção para o
qual a fita deve mover-se e um novo estado para o controle finito, ou seja,
pode-se imaginar um X na fita no estado 3 pode fazer a máquina determinística
escrever um Y na fita, mover a cabeça uma posição para a direita e mudar para o
estado 5. Todavia verifica-se que a
máquina de Turing não-determinística difere-se, pois um estado e um símbolo de
fita não mais definem estas três coisas de forma única, mais de uma ação pode
ser aplicável dado um estado e um símbolo.
Sendo assim a tabela de ação tem no máximo uma entrada
para cada combinação de símbolo e estado então constata-se que 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).
A TESE DE CHURCH-TURING
Nota-se que a tese leva o
nome dos matemáticos Alonzo Church e Alan Turing. E ao visualizar-se o artigo
"On Computable Numbers, with an Application to the Entscheidungsproblem
", de 1936, percebe-se Alan Turing tentar capturar a noção de algoritmo
até então chamado computabilidade efetiva, com a introdução de máquinas de
Turing o que a seguir em seu artigo mostrou-se que o 'Entscheidungsproblem' não
pode ser resolvido. Alguns meses antes Alonzo Church, como ilustra-se pela
história, provou um resultado similar em "A Note on the
Entscheidungsproblem", mas como apresenta-se ele usou as noções de funções recursivas e funções
lambda-definíveis para descrever formalmente a computabilidade efetiva. Por
meio destes dois formalismos descrevem-se o mesmo conjunto de funções, como
mostrado no caso de funções de inteiros positivos por Church e Kleene (Church
1936a, Kleene 1936). Ao ouvir-se a proposta de Church, Turing logo foi capaz de
mostrar que suas máquinas de Turing descrevem o mesmo conjunto de funções.
Desde aquela época
observa-se muitos outros como formalismos foram propostos para descrever a
computabilidade efetiva, incluindo funções recursivas, o cálculo lambda,
máquinas de registros, sistemas de Post, lógica combinatória e algoritmos de
Markov. Foi-se mostrado que todos esses sistemas computam essencialmente o
mesmo conjunto de funções que as máquinas de Turing; sistemas como esses são
chamados Turing completos. Como todas as diversas tentativas de formalizar o
conceito de algoritmo levaram a resultados equivalentes, geralmente assume-se
que a tese de Church-Turing é correta. No entanto, a tese é uma definição, e
não um teorema, e portanto não pode ser provada. Ela poderia, no entanto, ser
refutada se alguém descobrisse um método que fosse universalmente aceito como
um algoritmo efetivo mas que não pudesse ser executado por uma máquina de
Turing.
No início do século XX como
avalia-se os matemáticos freqüentemente usaram o termo informal efetivamente
computável, então foi importante achar uma boa formalização do conceito.
Matemáticos modernos usam, em seu lugar, o termo bem-definido Turing-computável
ou apenas computável, já que a terminologia indefinida caiu em desuso, a
questão de como definí-la é agora menos importante.
REFERÊNCIA
Wikipedia, Máquinas de
Turing Deterministicas. Disponível em: <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>. Acesso em 15 de setembro de 2016.
Wikipedia, Tese de
Church-Turing. Disponível em: <https://pt.wikipedia.org/wiki/Tese_de_Church-Turing>. Acesso em 15 de setembro de 2016.
Google, Elementos da Máquina de Turing. Disponível em: < https://www.google.com.br/search?q=elementos+da+maquina+de+turing>. Acesso em 15 de setembro de 2016.
Prof. Regina, Maquina de Turing. Disponível em: <http://www.profregina.atmanandi.com.br>. Acesso em 15 de setembro de 2016.
Wikipedia, Computabilidade. Disponível em: < https://pt.wikipedia.org/wiki/Computabilidade>. Acesso em 15 de setembro de 2016.
BLOG
PUBLICAÇÃO NA WEB
http://anhangueracollegeworks.blogspot.com.br/
