TUring

Páginas: 6 (1425 palavras) Publicado: 17 de setembro de 2014
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 qualsua 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ãoequivalentes. 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ãoincompará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"normalmente implica que o modelo proposto é fisicamente realizável, enquanto "hipercomputação".
A Tese de Church-Turing diz que toda função que é algoritmicamente computável, pode ser computada em uma Máquina de Turing. Hipercomputadores computam funções que máquinas de Turing não podem, e assim, não computáveis pela tese de Church-Turing.
Um exemplo de um problema que uma Máquina de Turing nopode resolver, é o Problema da Parada. Uma máquina de Turing na pode decidir se um programa arbitrário para, ou se executa para sempre. Algumas propostas de hipercomputadores podem simular um programa por um nemro infinito de passos, e pode dizer ao usuário se o programa parou ou não.



Redes Neurais: Em 1936, Turing idealizou um processo mecânico capaz realizar a manipulação de símbolos deforma semelhante a um ser humano, e assim, processar informação.
O paradigma computacional discreto - ou clássico - reinante na atualidade, tem sua raiz fincada na formalização desse conceito. Uma interpretação da tese de Church-Turing pode mesmo dar suporte à ideia de que nenhuma máquina realizável segundo esse paradigma pode superar a máquina de Turing em poder computacional.
A análise dopoder computacional de redes neurais proposta por Hava Siegelmann tem duas propriedades interessantes: uma rede recorrente com pesos sinápticos racionais possui a mesma capacidade computacional da clássica máquina de Turing, e uma estrutura com pesos reais tem poder computacional além-Turing.
No entanto, Siegelmann mostra que é possível implementar dispositivos analógicos que computam funçõesnão-recursivas, e, por isso, têm poder computacional superior ao de uma máquina de Turing. Para tanto, lança mão de redes neurais artificiais recorrentes de primeira ordem.

Computação Quântica: Pode-se dizer que a Computação Quântica nada mais é que uma melhoria (ou melhor, dizendo: “uma grande melhoria”) da Máquina de Turing.
Teoricamente, todos os problemas resolvidos em Computação...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Turing
  • Turing
  • Alan turing
  • Maquina de Turing
  • Alan Turing
  • Modelo de turing
  • TESTE Turing
  • Alan turing

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!