226304 materialEducativo

textoFiltroFicha
  • Eu curto 1
  • Visitas 466
  • Comentarios 0
  • Guardar en
  • Ações

Sobre este recurso...

La máquina de Turing, presentada por Alan Turing en 1936 en On computable numbers, with an application to the Entscheidungsproblems, es el modelo matemático de un dispositivo que se comporta como un autómata finito y que dispone de una cinta de longitud infinita en la que se pueden leer, escribir o borrar símbolos. Existen otras versiones con varias cintas, deterministas o no, etc., pero todas son equivalentes (respecto a los lenguajes que aceptan).

Uno de los teoremas más importantes sobre las máquinas de Turing es que pueden simular el comportamiento de una computadora (almacenamiento y unidad de control). Por ello, si un problema no puede ser resuelto por una de estas máquinas, entonces tampoco puede ser resuelto por una computadora (problema indecidible, NP).

La notación de las máquinas de Turing es sencilla y exacta, por lo que es más cómodo trabajar con ellas a la hora de estudiar qué problemas son decidibles (P) y cuáles indecidibles (NP).

En esta página veremos la definición de la Máquina de Turing, algunos ejemplos, su lenguaje y algunos teoremas que la relacionan con los Autómatas Finitos.

Mapa conceitual: Máquina de Turing (definición y lenguaje)

Conteúdo exclusivo para membros de

D/i/d/a/c/t/a/l/i/a
Iniciar sessão

Mira un ejemplo de lo que te pierdes

Fecha publicación: 15.4.2018

Respeita a licença original do recurso.

Comentar

0

Deseja fazer um comentário? Registrar o Iniciar sessão

Junte-se à Didactalia

Navegue entre 226304 recursos e 560475 pessoas

Regístrate >

O conéctate a través de:

Si ya eres usuario, Inicia sesión

Você quer acessar mais conteúdo educacional?

Iniciar sessao Participar de uma aula
x

Adicionar ao Didactalia Arrastra el botón a la barra de marcadores del navegador y comparte tus contenidos preferidos. Más info...

Ajuda do jogo
Juegos de anatomía
Selecciona nivel educativo