TUring

Trabalho:
Teoria
da computação

Máquina de Turing

Prof. Mestre Hugo Resende.
João Paulo Ramos
Exercício 2.1: Qual a importância da MT?
A MT teve importância fundamental no desenvolvimento das áreas de computabilidade, teoria dos autômatos formais e análise de algoritmos. Baseado nela, Turing tentou construir computadores com instruções extremamente elementares, o que bem depois concretizou-se com as máquinas denominadas de "RISC" (reduced instruction set computer). É assim que todos os computadores funcionam. A lógica por trás da máquina de Turing pode imitar qualquer algoritmo de um computador, se mostrando especialmente útil para que as pessoas possam compreender as limitações da computação.

2.2: O que diz a hipótese/tese de Church-Turing e qual sua importância para computação?

A Hipótese de Church-Turing Afirma que: Qualquer função computável pode ser processada por uma “Máquina de Turing”. Existe um procedimento eficiente para resolver um problema de decisão se e somente se, existe uma MT que termina para qualquer entrada que solucione o problema. Todos os modelos razoáveis do processo de computação definidos e por definir são equivalentes. Todos os formalismos propostos são equivalentes. Nenhuma função intuitivamente computável foi obtida que não pudesse ser expressa nesses formalismos.

2.3: Que modelos computacionais foram idealizados na tentativa de superar os limites computacionais das MT? Cite e descreva pelo menos 3.
Hipercomputação: refere-se aos modelos de computação que são mais poderosos que, ou são incomparáveis com, computabilidade de Turing. Isso inclui vários métodos hipotéticos para a Computação de Funções não-Turing computáveis, seguido por Algoritmo super-recursivas. O termo "computação super-Turing" surgiu em 1995 numa revista científica por Hava Siegelmann. O termo hipercomputação surgiu em 1999 por Jack Copeland and Diane Proud. Esses termos no são bem sinônimos: "computação super-Turing"