MÁQUINAS TURING !

Description

MÁQUINAS TURING
mjas0519
Mind Map by mjas0519, updated more than 1 year ago
mjas0519
Created by mjas0519 over 10 years ago
137
0

Resource summary

MÁQUINAS TURING
  1. Es un dispositivo de reconocimientos de lenguaje, es más general que cualquier autómata finito y cualquier autómata de pila, debido a que ellas pueden reconocer tanto los lenguajes regulares, como los lenguajes independientes de contexto y además muchos otros tipos de lenguajes.
    1. La máquina de Turing (abreviado MT) tiene, un control finito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene la palabra de entrada.
      1. La cinta es de longitud infinita hacia la derecha, hacia donde se extiende indefinidamente; La cinta no es infinita hacia la izquierda, por lo que hay un cuadro de la cinta que es el extremo izquierdo.
        1. En la MT la cabeza se mueve bidireccionalmente (izquierda y derecha), por lo que puede pasar repetidas veces sobre un mismo segmento de la cinta.
      2. Transforma un INPUT en un OUTPUT después de algunos pasos. Tanto el INPUT como el OUPUT constan de números en código binario (ceros y unos). En su versión original la máquina de Turing consiste en una cinta infinitamente larga con unos y ceros que pasa a través de una caja. La caja es tan fina que solo el trozo de cinta que ocupa un bit (0 ó 1) está en su interior. La máquina tiene una serie de estados internos finitos que también se pueden numerar en binario.
        1. La máquina de Turing, mecanismo que formaliza el concepto de algoritmo, que pretende ser lo suficientemente general como para resolver cualquier problema posible, se introduce para demostrar la validez de los postulados de Gödel. Turing demuestra que existen problemas irresolubles, inasequibles para cualquier máquina de Turing, y por ende, actualmente, para cualquier ordenador.
          1. • Máquina de Turing Multicinta • Máquina de Turing No Determinista • Máquina de Turing Multidimensional • Máquina de Turing con Múltiples Cabezales • Máquina de Turing Offline • Máquina de Turing con movimiento "stay" o "esperar" • Máquina de Turing con cinta infinita a ambos lados • Máquina de Turing con cinta multipista • Máquina Universal de Turing •Máquina de Turing Cuántica.
        Show full summary Hide full summary

        Similar

        The USA, 1919-41
        sagar.joban
        Unit 1 Sociology: Family Types
        ArcticCourtney
        English Language
        livbennett
        Romeo and Juliet: Key Points
        mbennett
        F211- Module 1 Cells, exchange and transport
        eilish.waite
        GCSE Chemistry C3 (OCR)
        Usman Rauf
        Topic 1 Quiz - Elements & The Periodic Table
        Musicdudejoe
        I wish I..
        Cristina Cabal
        1PR101 2.test - Část 15.
        Nikola Truong
        Cuadro sinóptico de la función de la planeación
        Elliot Anderson
        Mapa Mental para Resumir y Conectar Ideas
        Rosario Sharline Vilcarromero Saenz