Saltar al contenido principal
LibreTexts Español

12.10: Resumen

  • Page ID
    103674
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Template:MathJaxZach

    Una máquina de Turing es una especie de mecanismo de cómputo idealizado. Consiste en una cinta infinita unidireccional, dividida en cuadrados, cada uno de los cuales puede contener un símbolo de un alfabeto predeterminado. La máquina funciona moviendo un cabezal de lectura-escritura a lo largo de la cinta. También puede estar en uno de un número predeterminado de estados. Las acciones del cabezal de lectura-escritura están determinadas por un conjunto de instrucciones; cada instrucción está condicionada a que la máquina esté en cierto estado y lea cierto símbolo, y especifica qué símbolo escribirá la máquina en el cuadrado actual, si moverá el cabezal de lectura-escritura un cuadrado a la izquierda, derecho, o quedarse quieto, y a qué estado cambiará. Si la cinta contiene una cierta entrada, representada como una secuencia de símbolos en la cinta, y la máquina se pone en el estado de inicio designado con el cabezal de lectura-escritura leyendo el cuadrado más a la izquierda de la entrada, el conjunto de instrucciones determinará paso a paso una secuencia de configuraciones de la máquina: contenido de cinta, posición del cabezal de lectura-escritura y estado de la máquina. Si la máquina encuentra una configuración en la que el conjunto de instrucciones no contiene una instrucción para la combinación actual de lectura/estado de símbolos, la máquina se detiene y el contenido de la cinta es la salida.

    Los números se pueden representar muy fácilmente como secuencias de trazos en la Cinta de una máquina Turing. Decimos que una función\(\Nat \to \Nat\) es Turing computable si hay una máquina Turing que, cada vez que se inicia en la representación unaria de\(n\) como entrada, eventualmente se detiene con su cinta que contiene la representación unaria de\(f(n)\) como salida. Muchas funciones aritméticas familiares se muestran fácilmente (o no tan fácilmente) para ser computables Turing. Se han propuesto muchos otros modelos de cómputos distintos a las máquinas Turing; y siempre ha resultado que las funciones aritméticas computables allí también son computables Turing. Esto se ve como soporte para la Tesis Church-Turing, que cada función aritmética que se pueda calcular efectivamente es Turing computable.


    This page titled 12.10: Resumen is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .