Caracterizaciones de algoritmos - Algorithm characterizations

Las caracterizaciones de algoritmos son intentos de formalizar la palabra algoritmo . El algoritmo no tiene una definición formal generalmente aceptada. Los investigadores están trabajando activamente en este problema. Este artículo presentará algunas de las "caracterizaciones" de la noción de "algoritmo" con más detalle.

El problema de la definicion

Durante los últimos 200 años, la definición de algoritmo se ha vuelto más complicada y detallada a medida que los investigadores han tratado de precisar el término. De hecho, puede haber más de un tipo de "algoritmo". Pero la mayoría está de acuerdo en que el algoritmo tiene algo que ver con la definición de procesos generalizados para la creación de enteros de "salida" a partir de otros enteros de "entrada" - "parámetros de entrada" arbitrarios e infinitos en extensión, o limitados en extensión pero aún variables - mediante la manipulación de símbolos distinguibles (contar números) con colecciones finitas de reglas que una persona puede ejecutar con papel y lápiz.

Los esquemas de manipulación de números más comunes, tanto en las matemáticas formales como en la vida cotidiana, son: (1) las funciones recursivas calculadas por una persona con papel y lápiz, y (2) la máquina de Turing o sus equivalentes de Turing (el registro primitivo) modelo de máquina o "contra-máquina", el modelo de máquina de acceso aleatorio (RAM), el modelo de máquina de programa almacenado de acceso aleatorio (RASP) y su equivalente funcional "la computadora ".

Cuando estamos haciendo "aritmética" en realidad estamos calculando mediante el uso de "funciones recursivas" en los algoritmos taquigráficos que aprendimos en la escuela primaria, por ejemplo, sumar y restar.

Las pruebas de que cada "función recursiva" que podemos calcular a mano se puede calcular mediante una máquina y viceversa —nótese el uso de las palabras calcular frente a calcular— son notables. Pero esta equivalencia junto con la tesis (afirmación no probada) de que esto incluye cada cálculo / cálculo indica por qué se ha puesto tanto énfasis en el uso de máquinas equivalentes de Turing en la definición de algoritmos específicos, y por qué la definición de "algoritmo" en sí. a menudo se refiere a "la máquina de Turing ". Esto se discute con más detalle bajo la caracterización de Stephen Kleene .

Los siguientes son resúmenes de las caracterizaciones más famosas (Kleene, Markov, Knuth) junto con aquellas que introducen elementos novedosos, elementos que amplían aún más la definición o contribuyen a una definición más precisa.

[ Un problema matemático y su resultado pueden considerarse como dos puntos en un espacio, y la solución consiste en una secuencia de pasos o un camino que los une. La calidad de la solución es función del camino. Puede haber más de un atributo definido para el camino, por ejemplo, longitud, la complejidad de la forma, una facilidad de generalizar, dificultad, y así sucesivamente . ]

Jerarquía de Chomsky

Existe un mayor consenso sobre la "caracterización" de la noción de "algoritmo simple".

Todos los algoritmos deben especificarse en un lenguaje formal, y la "noción de simplicidad" surge de la simplicidad del lenguaje. La jerarquía de Chomsky (1956) es una jerarquía de contención de clases de gramáticas formales que generan lenguajes formales . Se utiliza para clasificar lenguajes de programación y máquinas abstractas .

Desde la perspectiva de la jerarquía de Chomsky , si el algoritmo se puede especificar en un lenguaje más simple (que sin restricciones), se puede caracterizar por este tipo de lenguaje, de lo contrario es un típico "algoritmo sin restricciones".

Ejemplos: un lenguaje de macros de "propósito general", como M4, no tiene restricciones ( Turing completo ), pero el lenguaje de macros del preprocesador de C no lo es, por lo que cualquier algoritmo expresado en el preprocesador de C es un "algoritmo simple".

Consulte también Relaciones entre clases de complejidad .

Características de un buen algoritmo.

Las siguientes son las características de un buen algoritmo;

  • Precisión: un buen algoritmo debe tener ciertos pasos descritos. Los pasos deben ser lo suficientemente exactos y no variar.
  • Unicidad: cada paso dado en el algoritmo debe dar un resultado definido según lo establecido por el escritor del algoritmo. Los resultados no deben fluctuar de ninguna manera.
  • Viabilidad: el algoritmo debería ser posible y practicable en la vida real. No debe ser abstracto o imaginario.
  • Entrada: un buen algoritmo debe poder aceptar un conjunto de entradas definidas.
  • Salida: un buen algoritmo debería poder producir resultados como salida, preferiblemente soluciones.
  • Finitud: el algoritmo debe detenerse después de un cierto número de instrucciones.
  • Generalidad: el algoritmo debe aplicarse a un conjunto de entradas definidas.

1881 La reacción negativa de John Venn a la máquina lógica de W. Stanley Jevons de 1870

A principios de 1870 W. Stanley Jevons presentó una "Máquina lógica" (Jevons 1880: 200) para analizar un silogismo u otra forma lógica, por ejemplo, un argumento reducido a una ecuación booleana . Mediante lo que Couturat (1914) llamó una "especie de piano lógico [,] ... las igualdades que representan las premisas ... se" tocan "en un teclado como el de una máquina de escribir. ... Cuando todas las premisas "jugado", el panel muestra sólo aquellos constituyentes cuya suma es igual a 1, es decir, ... su todo lógico. Este método mecánico tiene la ventaja sobre el método geométrico de VENN ... "(Couturat 1914: 75).

Por su parte, John Venn , un lógico contemporáneo de Jevons, estaba menos que emocionado, y opinó que "no me parece que ninguna invención actualmente conocida o que pueda descubrirse realmente merezca el nombre de máquinas lógicas" (cursiva agregada, Venn 1881: 120). Pero de uso histórico para la noción en desarrollo de "algoritmo" es su explicación de su reacción negativa con respecto a una máquina que "puede servir a un propósito realmente valioso al permitirnos evitar un trabajo que de otro modo sería inevitable":

(1) "Primero, la declaración de nuestros datos en un lenguaje lógico preciso",
(2) "Luego, en segundo lugar, tenemos que lanzar estas declaraciones en una forma adecuada para que el motor funcione - en este caso la reducción de cada proposición a sus negaciones elementales",
(3) "En tercer lugar, existe la combinación o el tratamiento adicional de nuestras instalaciones después de dicha reducción".
(4) "Finalmente, los resultados deben interpretarse o leerse. Esto último generalmente da lugar a una gran apertura para la habilidad y la sagacidad".

Concluye que "no veo que ninguna máquina pueda esperar ayudarnos excepto en el tercero de estos pasos; de modo que parece muy dudoso que algo de este tipo realmente merezca el nombre de motor lógico" (Venn 1881: 119). –121).

1943, 1952 Caracterización de Stephen Kleene

Esta sección es más larga y detallada que las demás debido a su importancia para el tema: Kleene fue el primero en proponer que todos los cálculos / cálculos, de todo tipo, la totalidad de, se pueden (i) calcular de manera equivalente mediante el uso de cinco " operadores recursivos primitivos "más un operador especial llamado operador mu , o ser (ii) calculado por las acciones de una máquina de Turing o un modelo equivalente.

Además, opinó que cualquiera de estos sería una definición de algoritmo .

Un lector que se enfrente primero a las palabras que siguen puede muy bien estar confundido, por lo que conviene una breve explicación. Medios de cálculo realizados a mano, medios de cálculo realizados por máquina de Turing (o equivalente). (A veces un autor se desliza e intercambia las palabras). Una "función" puede considerarse como un "cuadro de entrada-salida" en el que una persona coloca números naturales llamados "argumentos" o "parámetros" (pero solo los números de conteo, incluido el 0, los enteros no negativos) y obtiene un solo número no negativo. entero (llamado convencionalmente "la respuesta"). Piense en la "caja de función" como un hombrecito que calcula a mano usando "recursividad general" o calcula con una máquina de Turing (o una máquina equivalente).

"Efectivamente calculable / computable" es más genérico y significa "calculable / computable mediante algún procedimiento, método, técnica ... lo que sea ...". "General recursivo" era la forma en que Kleene escribía lo que hoy se llama simplemente "recursividad"; sin embargo, la "recursividad primitiva" —cálculo mediante el uso de los cinco operadores recursivos— es una forma menor de recursividad que carece de acceso al sexto operador mu adicional que se necesita sólo en raras ocasiones. Así, la mayor parte de la vida continúa requiriendo sólo las "funciones recursivas primitivas".

1943 "Tesis I", 1952 "Tesis de la Iglesia"

En 1943, Kleene propuso lo que se conoce como la tesis de Church :

" Tesis I. Toda función efectivamente calculable (predicado efectivamente decidible) es recursiva general" (Declarada por primera vez por Kleene en 1943 (página 274 reimpresa en Davis, ed. The Undecidable ; aparece también textualmente en Kleene (1952) p.300)

En pocas palabras: para calcular cualquier función, las únicas operaciones que una persona necesita (técnicamente, formalmente) son los 6 operadores primitivos de la recursividad "general" (hoy en día denominados operadores de las funciones recursivas mu ).

La primera declaración de Kleene sobre esto fue bajo el título de la sección " 12. Teorías algorítmicas ". Más tarde lo ampliaría en su texto (1952) de la siguiente manera:

"La tesis I y su inversa proporcionan la definición exacta de la noción de un procedimiento o algoritmo de cálculo (decisión) , para el caso de una función (predicado) de números naturales" (p. 301, negrita agregada para enfatizar)

(Su uso de la palabra "decisión" y "predicado" extiende la noción de calculabilidad a la manipulación más general de símbolos, como ocurre en las "pruebas" matemáticas).

Esto no es tan abrumador como puede parecer: la recursividad "general" es solo una forma de realizar nuestras operaciones aritméticas diarias a partir de los cinco "operadores" de las funciones recursivas primitivas junto con el operador mu adicional según sea necesario. De hecho, Kleene da 13 ejemplos de funciones recursivas primitivas y Boolos-Burgess-Jeffrey agregan algunos más, la mayoría de los cuales serán familiares para el lector, por ejemplo, suma, resta, multiplicación y división, exponenciación, la función CASE, concatenación, etc. etc .; para obtener una lista, consulte Algunas funciones recursivas primitivas comunes .

¿Por qué funciones recursivas generales en lugar de funciones recursivas primitivas?

Kleene y col. (cf §55 Funciones recursivas generales p. 270 en Kleene 1952) tuvo que agregar un sexto operador de recursión llamado operador de minimización (escrito como operador μ u operador mu ) porque Ackermann (1925) produjo una función enormemente creciente: la de Ackermann función —y Rózsa Péter (1935) produjeron un método general para crear funciones recursivas usando el argumento diagonal de Cantor , ninguno de los cuales podría ser descrito por los 5 operadores de función recursiva primitiva. Con respecto a la función de Ackermann:

"... en cierto sentido, la longitud del algoritmo de cálculo de una función recursiva que no es también recursiva primitiva crece más rápidamente con los argumentos que el valor de cualquier función recursiva primitiva" (Kleene (1935) reimpreso p. 246 en The Indecidible , más la nota al pie 13 con respecto a la necesidad de un operador adicional, negrita agregada).

Pero la necesidad del operador mu es una rareza. Como se indicó anteriormente en la lista de cálculos comunes de Kleene, una persona sigue su vida felizmente calculando funciones recursivas primitivas sin temor a encontrar los números monstruosos creados por la función de Ackermann (por ejemplo , superexponenciación ).

1952 "Tesis de Turing"

La Tesis de Turing plantea la hipótesis de la computabilidad de "todas las funciones computables" mediante el modelo de la máquina de Turing y sus equivalentes.

Para hacer esto de una manera eficaz, Kleene extendió la noción de "computable" ampliando la red, permitiendo en la noción de "funciones" tanto las "funciones totales" como las "funciones parciales". Una función total es aquella que se define para todos los números naturales (enteros positivos, incluido el 0). Se define una función parcial para algunos números naturales, pero no para todos; la especificación de "algunos" tiene que venir "por adelantado". Así, la inclusión de "función parcial" extiende la noción de función a funciones "menos perfectas". Las funciones totales y parciales pueden calcularse a mano o calcularse a máquina.

Ejemplos:
"Funciones": incluye "resta común m  -  n " y "suma m  +  n "
"Función parcial": "Resta común" m  -  n no está definida cuando solo se permiten números naturales (enteros positivos y cero) como entrada; por ejemplo, 6 - 7 no está definida
Función total: "Suma" m  +  n se define para todos los enteros positivos y cero.


Ahora observamos la definición de Kleene de "computable" en un sentido formal:

Definición: "Una función parcial φ es computable , si hay una máquina M que la calcula" (Kleene (1952) p. 360)
"Definición 2.5. Una función n -aria f ( x 1 , ..., x n ) es parcialmente computable si existe una máquina de Turing Z tal que
f ( x 1 , ..., x norte ) = Ψ Z ( norte ) ( x 1 , ..., [ x norte )
En este caso decimos que [máquina] Z calcula f . Si, además, f ( x 1 , ..., x n ) es una función total, entonces se llama computable "(Davis (1958) p. 10)

Así llegamos a la Tesis de Turing :

"Toda función que naturalmente se consideraría computable es computable ... por una de sus máquinas ..." (Kleene (1952) p.376)

Aunque Kleene no dio ejemplos de "funciones computables", otros sí lo han hecho. Por ejemplo, Davis (1958) da tablas de Turing para las funciones Constante, Sucesora e Identidad, tres de los cinco operadores de las funciones recursivas primitivas :

Computable por máquina de Turing:
Suma (también es la función constante si un operando es 0)
Incremento (función sucesora)
Resta común (definida solo si x y ). Por tanto, " x  -  y " es un ejemplo de una función parcialmente computable.
Resta adecuada x y (como se define arriba)
La función identidad: para cada i , existe una función U Z n = Ψ Z n ( x 1 , ..., x n ) que extrae x i del conjunto de argumentos ( x 1 , ..., x n )
Multiplicación

Boolos-Burgess-Jeffrey (2002) dan lo siguiente como descripciones en prosa de las máquinas de Turing para:

Duplicación: 2 p
Paridad
Adición
Multiplicación

Con respecto a la máquina contador , un modelo de máquina abstracto equivalente a la máquina de Turing:

Ejemplos Computable por la máquina Abacus (cf Boolos – Burgess – Jeffrey (2002))
Adición
Multiplicación
Exponention: (un diagrama de flujo / diagrama de bloques descripción del algoritmo)

Demostraciones de computabilidad por máquina de ábaco (Boolos – Burgess – Jeffrey (2002)) y por máquina de contador (Minsky 1967):

Los seis operadores de funciones recursivas:
  1. Función cero
  2. Función sucesora
  3. Función de identidad
  4. Función de composición
  5. Recursión primitiva (inducción)
  6. Minimización

El hecho de que los modelos ábaco / contra-máquina puedan simular las funciones recursivas proporciona la prueba de que: Si una función es "calculable por máquina", entonces es "calculable a mano por recursividad parcial". Teorema XXIX de Kleene:

" Teorema XXIX:" Toda función parcial computable φ es parcial recursiva ... "(cursiva en el original, p. 374).

Lo contrario aparece como su Teorema XXVIII. Juntos, estos forman la prueba de su equivalencia, el Teorema XXX de Kleene.

1952 Tesis de Church-Turing

Con su Teorema XXX, Kleene prueba la equivalencia de las dos "Tesis": la Tesis de Church y la Tesis de Turing. (Kleene solo puede hipotetizar (conjeturar) la verdad de ambas tesis, estas no las ha probado ):

TEOREMA XXX: Las siguientes clases de funciones parciales ... tienen los mismos miembros: (a) las funciones parciales recursivas, (b) las funciones computables ... " (p. 376)
Definición de "función parcial recursiva": "Una función parcial φ es parcial recursiva en [las funciones parciales] ψ 1 , ... ψ n si hay un sistema de ecuaciones E que define φ recursivamente a partir de [funciones parciales] ψ 1 , ... ψ n "(pág. 326)

Así, según el teorema XXX de Kleene: cualquier método para hacer números a partir de números de entrada —funciones recursivas calculadas a mano o calculadas por la máquina de Turing o equivalente— da como resultado una "función efectivamente calculable / computable ". Si aceptamos la hipótesis de que cada cálculo / cálculo se puede realizar por cualquier método de manera equivalente, hemos aceptado tanto el Teorema XXX de Kleene (la equivalencia) como la Tesis de Church-Turing (la hipótesis de "todos").

Una nota de disensión: "Hay más en el algoritmo ..." Blass y Gurevich (2003)

La noción de separar las tesis de Church y Turing de la "tesis de Church-Turing" aparece no sólo en Kleene (1952) sino también en Blass-Gurevich (2003). Pero si bien hay acuerdos, también hay desacuerdos:

"... no estamos de acuerdo con Kleene en que la noción de algoritmo es tan bien entendida. De hecho, la noción de algoritmo es más rica en estos días de lo que era en los días de Turing. Y hay algoritmos, de variedades modernas y clásicas, no cubiertos directamente por El análisis de Turing, por ejemplo, algoritmos que interactúan con sus entornos, algoritmos cuyas entradas son estructuras abstractas y algoritmos geométricos o, más generalmente, no discretos "(Blass-Gurevich (2003) p. 8, negrita agregada)

1954 Caracterización de AA Markov Jr.

Andrey Markov Jr. (1954) proporcionó la siguiente definición de algoritmo:

"1. En matemáticas," algoritmo "se entiende comúnmente como una prescripción exacta, que define un proceso computacional, que lleva desde varios datos iniciales al resultado deseado ..."
"Las siguientes tres características son características de los algoritmos y determinan su papel en las matemáticas:
"a) la precisión de la prescripción, sin dejar lugar a la arbitrariedad, y su comprensibilidad universal - la precisión del algoritmo;
"b) la posibilidad de comenzar con datos iniciales, que pueden variar dentro de determinados límites: la generalidad del algoritmo;
"c) la orientación del algoritmo hacia la obtención de algún resultado deseado, que de hecho se obtiene al final con los datos iniciales adecuados: la conclusividad del algoritmo". (pág.1)

Admitió que esta definición "no pretende ser de precisión matemática" (p. 1). Su monografía de 1954 fue su intento de definir el algoritmo con mayor precisión; vio la definición resultante, su algoritmo "normal", como "equivalente al concepto de función recursiva " (pág. 3). Su definición incluía cuatro componentes principales (Capítulo II.3 págs. 63 y siguientes):

"1. Pasos elementales separados, cada uno de los cuales se llevará a cabo de acuerdo con una de [las reglas de sustitución] ... [reglas dadas al principio]
"2. ... pasos de naturaleza local ... [Por lo tanto, el algoritmo no cambiará más que un cierto número de símbolos a la izquierda o derecha de la palabra / símbolo observado]
"3. Reglas para las fórmulas de sustitución ... [llamó a la lista de estos" el esquema "del algoritmo]
"4. ... un medio para distinguir una" sustitución final "[es decir, un estado o estados" terminales / finales "distinguibles]

En su Introducción, Markov observó que "todo el significado para las matemáticas" de los esfuerzos por definir el algoritmo con mayor precisión estaría "en conexión con el problema de una base constructiva para las matemáticas" (p. 2). Ian Stewart (cf. Encyclopædia Britannica) comparte una creencia similar: "... el análisis constructivo tiene el mismo espíritu algorítmico que la informática ...". Para obtener más información, consulte Matemáticas constructivas e intuicionismo .

Distinguibilidad y localidad : ambas nociones aparecieron por primera vez con Turing (1936-1937) -

"Los nuevos cuadrados observados deben ser inmediatamente reconocibles por la computadora [ sic : una computadora era una persona en 1936]. Creo que es razonable suponer que solo pueden ser cuadrados cuya distancia desde el más cercano de los cuadrados inmediatamente observados no exceda un cierta cantidad fija. Dejemos que cada uno de los nuevos cuadrados observados esté dentro de L cuadrados de uno de los cuadrados observados anteriormente ". (Turing (1936) p. 136 en Davis ed. Indecidible )

La localidad aparece de manera prominente en el trabajo de Gurevich y Gandy (1980) (a quien Gurevich cita). El "cuarto principio de los mecanismos" de Gandy es "el principio de causalidad local":

"Ahora llegamos al más importante de nuestros principios. En el análisis de Turing, el requisito de que la acción dependa sólo de una parte limitada del registro se basó en una limitación humana. Reemplazamos esto por una limitación física que llamamos el principio de causalidad. Su justificación radica en la velocidad finita de propagación de efectos y señales: la física contemporánea rechaza la posibilidad de una acción instantánea a distancia ". (Gandy (1980) p. 135 en J. Barwise et al.)

1936, 1963, 1964 Caracterización de Gödel

1936 : Una cita bastante famosa de Kurt Gödel aparece en una "Observación agregada como prueba [de la publicación alemana original] en su artículo" Sobre la extensión de las pruebas "traducido por Martin Davis que aparece en las páginas 82-83 de The Undecidable . varios autores (Kleene, Gurevich, Gandy, etc.) han citado lo siguiente:

"Así, el concepto de" computable "es en cierto sentido definido" absoluto ", mientras que prácticamente todos los demás conceptos metamatemáticos familiares (por ejemplo, demostrables, definibles, etc.) dependen esencialmente del sistema con respecto al cual se definen". (pág.83)

1963 : En una "Nota" fechada el 28 de agosto de 1963 agregada a su famoso artículo On Formally Undecidable Propositions (1931), Gödel afirma (en una nota al pie) su creencia de que los " sistemas formales " tienen "la propiedad característica de que el razonamiento en ellos, en principio, puede ser reemplazado completamente por dispositivos mecánicos "(p. 616 en van Heijenoort). "... debido a" el trabajo de AM Turing, ahora se puede dar una definición precisa e incuestionablemente adecuada de la noción general de sistema formal [y] ahora es posible una versión completamente general de los Teoremas VI y XI "(p. 616). En una nota de 1964 a otra obra, expresa la misma opinión con más fuerza y ​​con más detalle.

1964 : En un Postscriptum, fechado en 1964, en un artículo presentado al Instituto de Estudios Avanzados en la primavera de 1934, Gödel amplió su convicción de que los "sistemas formales" son aquellos que pueden mecanizarse:

"Como consecuencia de los avances posteriores, en particular del hecho de que, debido al trabajo de AM Turing, ahora se puede dar una definición precisa e incuestionablemente adecuada del concepto general de sistema formal ... El trabajo de Turing da un análisis del concepto de" procedimiento mecánico "(alias" algoritmo "o" procedimiento computacional "o" procedimiento combinatorio finito "). Se muestra que este concepto es equivalente al de una" máquina de Turing ". * Un sistema formal puede definirse simplemente como cualquier procedimiento mecánico para producir fórmulas, llamadas fórmulas demostrables ... ". (p. 72 en Martin Davis ed. The Undecidable : "Postscriptum" a "On Undecidable Propositions of Formal Mathematical Systems" que aparece en la p. 39, loc. cit.)

El * indica una nota a pie de página en la que Gödel cita los artículos de Alan Turing (1937) y Emil Post (1936) y luego pasa a hacer la siguiente declaración intrigante:

"En cuanto a las definiciones equivalentes anteriores de computabilidad, que sin embargo, son mucho menos adecuadas para nuestro propósito, ver Alonzo Church , Am. J. Math., Vol. 58 (1936) [que aparece en The Undecidable pp. 100-102]).

Las definiciones de Church abarcan la llamada " recursividad " y el " cálculo lambda " (es decir, las funciones definibles por λ). Su nota a pie de página 18 dice que discutió la relación de "calculabilidad efectiva" y "recursividad" con Gödel, pero que cuestionó independientemente "calculabilidad efectiva" y "definibilidad λ":

"Ahora definimos la noción ... de una función efectivamente calculable de enteros positivos identificándola con la noción de una función recursiva de enteros positivos 18 (o de una función definible por λ de enteros positivos.
"Ya se ha señalado que, para cada función de números enteros positivos que sea efectivamente calculable en el sentido recién definido, existe un algoritmo para el cálculo de su valor.
"Por el contrario, es cierto..." (p. 100, Lo indecidible).

Parecería de esto y de lo siguiente, que en lo que respecta a Gödel, la máquina de Turing era suficiente y el cálculo lambda era "mucho menos adecuado". Continúa señalando que, con respecto a las limitaciones de la razón humana, el jurado aún está deliberando:

("Nótese que la cuestión de si existen procedimientos finitos no mecánicos ** no equivalentes a ningún algoritmo, no tiene nada que ver con la adecuación de la definición de" sistema formal "y de" procedimiento mecánico ") (p. 72, loc. Cit.)
"(Para teorías y procedimientos en el sentido más general indicado en la nota al pie **, la situación puede ser diferente. Nótese que los resultados mencionados en la posdata no establecen límites para los poderes de la razón humana, sino más bien para las potencialidades del formalismo puro en matemáticas.) (p. 73 loc. cit.)
Nota a pie de página **: "Es decir, como implica el uso de términos abstractos sobre la base de su significado. Ver mi artículo en Dial. 12 (1958), p. 280." (esta nota a pie de página aparece en la p. 72, loc. cit.).

1967 caracterización de Minsky

Minsky (1967) afirma sin rodeos que "un algoritmo es" un procedimiento eficaz "y se niega a utilizar la palabra" algoritmo "más adelante en su texto; de hecho, su índice deja en claro lo que siente acerca de" Algoritmo, sinónimo de procedimiento eficaz "( pág.311):

"Usaremos el último término [un procedimiento efectivo ] en la secuela. Los términos son aproximadamente sinónimos, pero hay varios matices de significado usados ​​en diferentes contextos, especialmente para 'algoritmo'" (cursiva en el original, p. 105 )

Otros escritores (ver Knuth más adelante) usan la palabra "procedimiento efectivo". Esto lleva a uno a preguntarse: ¿Cuál es la noción de Minsky de "un procedimiento eficaz"? Comienza con:

"... un conjunto de reglas que nos dicen, momento a momento, precisamente cómo comportarnos" (p. 106)

Pero reconoce que esto está sujeto a críticas:

"... la crítica de que se deja que la interpretación de las reglas dependa de alguna persona o agente" (p. 106)

¿Su refinamiento? Para "especificar, junto con el enunciado de las reglas, los detalles del mecanismo que va a interpretarlas ". Para evitar el proceso "engorroso" de "tener que hacer esto nuevamente para cada procedimiento individual", espera identificar una " familia razonablemente uniforme de mecanismos de obediencia a las reglas". Su "formulación":

"(1) un lenguaje en el que se expresen conjuntos de reglas de comportamiento, y
"(2) una sola máquina que puede interpretar declaraciones en el lenguaje y así llevar a cabo los pasos de cada proceso especificado". (cursiva en el original, todas las citas de este párrafo p. 107)

Al final, sin embargo, todavía le preocupa que "quede un aspecto subjetivo del asunto. Es posible que diferentes personas no estén de acuerdo sobre si un determinado procedimiento debe considerarse efectivo" (p. 107).

Pero Minsky no se deja intimidar. Inmediatamente introduce el "Análisis del proceso de computación de Turing" (su capítulo 5.2). Cita lo que él llama " tesis de Turing ".

"Cualquier proceso que naturalmente podría llamarse un procedimiento efectivo puede ser realizado por una máquina de Turing" (p. 108. Minsky comenta que en una forma más general esto se llama " tesis de Church ").

Después de un análisis del "Argumento de Turing" (su capítulo 5.3), observa que "la equivalencia de muchas formulaciones intuitivas" de Turing, Church, Kleene, Post y Smullyan "... nos lleva a suponer que realmente hay aquí un 'objetivo 'o noción' absoluta '. Como lo expresó Rogers [1959]:

“En este sentido, la noción de función efectivamente computable es uno de los pocos conceptos 'absolutos' producidos por el trabajo moderno en los fundamentos de las matemáticas '” (Minsky p. 111 citando a Rogers, Hartley Jr (1959) La teoría actual de la máquina de Turing computabilidad , J. SIAM 7, 114-130.)

Caracterización de Rogers de 1967

En su Teoría de Funciones Recursivas y Computabilidad Efectiva de 1967, Hartley Rogers caracteriza el "algoritmo" aproximadamente como "un procedimiento administrativo (es decir, determinista, contable) ... aplicado a ... entradas simbólicas y que eventualmente cederá, para cada entrada , una salida simbólica correspondiente "(p. 1). Luego pasa a describir la noción "en términos aproximados e intuitivos" como que tiene diez "características", cinco de las cuales afirma que "prácticamente todos los matemáticos estarían de acuerdo [con]" (p. 2). Afirma que los 5 restantes "son menos obvios que * 1 a * 5 y acerca de los cuales podríamos encontrar un acuerdo menos general" (p. 3).

Los 5 "obvios" son:

  • 1 Un algoritmo es un conjunto de instrucciones de tamaño finito,
  • 2 Hay un agente informático capaz,
  • 3 "Hay instalaciones para realizar, almacenar y recuperar pasos en un cálculo"
  • 4 Dados los números 1 y 2, el agente calcula "de manera discreta por pasos" sin el uso de métodos continuos o dispositivos analógicos ",
  • 5 El agente informático lleva adelante el cálculo "sin recurrir a métodos o dispositivos aleatorios, por ejemplo, dados" (en una nota a pie de página, Rogers se pregunta si el n. ° 4 y el n. ° 5 son realmente lo mismo)

Los 5 restantes que abre a debatir, son:

  • 6 Sin límite fijo en el tamaño de las entradas,
  • 7 Sin límite fijo sobre el tamaño del conjunto de instrucciones,
  • 8 Sin límite fijo en la cantidad de almacenamiento de memoria disponible,
  • 9 Un límite finito fijo en la capacidad o habilidad del agente informático (Rogers ilustra con un ejemplo mecanismos simples similares a una máquina de Post-Turing o una máquina de contador ),
  • 10 Un límite en la longitud del cálculo: "¿deberíamos tener alguna idea, 'antes de tiempo', cuánto tiempo llevará el cálculo?" (pág.5). Rogers requiere "sólo que un cálculo termine después de un número finito de pasos; no insistimos en una capacidad a priori para estimar este número". (pág.5).

1968, 1973 caracterización de Knuth

Knuth (1968, 1973) ha proporcionado una lista de cinco propiedades que son ampliamente aceptadas como requisitos para un algoritmo:

  1. Finitud : "Un algoritmo siempre debe terminar después de un número finito de pasos ... un número muy finito, un número razonable"
  2. Precisión : "Cada paso de un algoritmo debe definirse con precisión; las acciones a realizar deben especificarse de manera rigurosa e inequívoca para cada caso"
  3. Entrada : "... cantidades que se le dan inicialmente antes de que comience el algoritmo. Estas entradas se toman de conjuntos de objetos específicos"
  4. Salida : "... cantidades que tienen una relación específica con las entradas"
  5. Efectividad : "... todas las operaciones a realizar en el algoritmo deben ser lo suficientemente básicas como para que, en principio, puedan ser realizadas con exactitud y en un tiempo finito por un hombre usando papel y lápiz"

Knuth ofrece como ejemplo el algoritmo euclidiano para determinar el máximo común divisor de dos números naturales (cf. Knuth Vol. 1 p. 2).

Knuth admite que, si bien su descripción de un algoritmo puede ser intuitivamente clara, carece de rigor formal, ya que no está exactamente claro qué significa "definido con precisión", o qué significa "especificado de manera rigurosa e inequívoca", o "suficientemente básico", y así adelante. Hace un esfuerzo en esta dirección en su primer volumen donde define en detalle lo que él llama el " lenguaje máquina " de su "mítico MIX ... el primer ordenador poliinsaturado del mundo" (págs. 120ss). Muchos de los algoritmos de sus libros están escritos en el lenguaje MIX. También utiliza diagramas de árbol , diagramas de flujo y diagramas de estado .

"Bondad" de un algoritmo, "mejores" algoritmos : Knuth afirma que "en la práctica, no solo queremos algoritmos, queremos buenos algoritmos ...". Sugiere que algunos criterios de bondad de un algoritmo son el número de pasos a realizar el algoritmo, su "adaptabilidad a los ordenadores, su sencillez y elegancia, etc." Dado un número de algoritmos para realizar el mismo cálculo, ¿cuál es el "mejor"? Él llama a este tipo de indagación "análisis algorítmico: dado un algoritmo, para determinar sus características de desempeño" (todo cita este párrafo: Knuth Vol. 1 p. 7)

1972 Caracterización de Stone

Stone (1972) y Knuth (1968, 1973) fueron profesores en la Universidad de Stanford al mismo tiempo, por lo que no es sorprendente que haya similitudes en sus definiciones (negrita agregada para enfatizar):

"Para resumir ... definimos un algoritmo como un conjunto de reglas que definen con precisión una secuencia de operaciones de modo que cada regla sea efectiva y definida y que la secuencia termine en un tiempo finito". (negrita agregada, p. 8)

Stone es digno de mención debido a su detallada discusión sobre lo que constituye una regla "efectiva": su robot , o persona que actúa como robot, debe tener cierta información y habilidades dentro de ellos, y si no, la información y la capacidad deben proporcionarse en "el algoritmo":

"Para que las personas sigan las reglas de un algoritmo, las reglas deben estar formuladas de modo que puedan seguirse como un robot , es decir, sin necesidad de pensar ... sin embargo, si las instrucciones [para resolver la cuadrática ecuación, su ejemplo] deben ser obedecidos por alguien que sabe cómo realizar operaciones aritméticas pero no sabe cómo extraer una raíz cuadrada, entonces también debemos proporcionar un conjunto de reglas para extraer una raíz cuadrada a fin de satisfacer la definición de algoritmo "(pág. 4-5)

Además, "... no todas las instrucciones son aceptables , porque pueden requerir que el robot tenga habilidades más allá de las que consideramos razonables ". Da el ejemplo de un robot que se enfrenta a la pregunta "¿Enrique VIII es rey de Inglaterra?" e imprimir 1 en caso afirmativo y 0 en caso negativo, pero al robot no se le ha proporcionado previamente esta información. Y lo que es peor, si se le pregunta al robot si Aristóteles era un rey de Inglaterra y al robot solo se le habían proporcionado cinco nombres, no sabría cómo responder. Así:

“Una definición intuitiva de una secuencia aceptable de instrucciones es aquella en la que cada instrucción se define con precisión para que el robot tenga la garantía de poder obedecerla ” (p. 6)

Después de proporcionarnos su definición, Stone presenta el modelo de la máquina de Turing y afirma que el conjunto de cinco tuplas que son las instrucciones de la máquina son “un algoritmo ... conocido como programa de la máquina de Turing” (p. 9). Inmediatamente después, continúa diciendo que un “ cálculo de una máquina de Turing se describe declarando:

"1. El alfabeto de la cinta
"2. La forma en que se presentan los parámetros [de entrada] en la cinta
"3. El estado inicial de la máquina de Turing
"4. La forma en que las respuestas [salida] se representarán en la cinta cuando la máquina de Turing se detenga
"5. El programa de la máquina" (cursiva agregada, p. 10)

Esta prescripción precisa de lo que se requiere para "un cálculo" está en el espíritu de lo que seguirá en el trabajo de Blass y Gurevich.

1995 caracterización de Soare

"Un cálculo es un proceso mediante el cual procedemos a partir de objetos inicialmente dados, llamados entradas , de acuerdo con un conjunto fijo de reglas, llamado programa, procedimiento o algoritmo , a través de una serie de pasos y llegamos al final de estos pasos con un final resultado, llamado salida . El algoritmo , como un conjunto de reglas que van de las entradas a la salida, debe ser preciso y definido con cada paso sucesivo claramente determinado. El concepto de computabilidad se refiere a aquellos objetos que pueden especificarse en principio mediante cálculos. "(cursiva en el original, negrita añadida pág. 3)

2000 la caracterización de Berlinski

Mientras estudiaba en Princeton a mediados de la década de 1960, David Berlinski era alumno de Alonzo Church (cf. p. 160). Su libro del año 2000 The Advent of the Algorithm: The 300-year Journey from an Idea to the Computer contiene la siguiente definición de algoritmo :

" En la voz del lógico:
" un algoritmo es
un procedimiento finito,
escrito en un vocabulario simbólico fijo,
regido por instrucciones precisas,
moviéndose en pasos discretos, 1, 2, 3,. . .,
cuya ejecución no requiere perspicacia, astucia,
intuición, inteligencia o perspicacia,
y que tarde o temprano llega a su fin. "(negrita y cursiva en el original, pág. xviii)

2000, 2002 Caracterización de Gurevich

Una lectura cuidadosa de Gurevich 2000 lleva a uno a concluir (¿inferir?) Que él cree que "un algoritmo" es en realidad "una máquina de Turing" o "una máquina de puntero " que realiza un cálculo. Un "algoritmo" no es solo la tabla de símbolos que guía el comportamiento de la máquina, ni es solo una instancia de una máquina que realiza un cálculo dado un conjunto particular de parámetros de entrada, ni es una máquina adecuadamente programada con la energía apagada. ; más bien, un algoritmo es la máquina que realmente realiza cualquier cálculo del que es capaz . Gurevich no sale directamente y dice esto, por lo que, tal como está redactado anteriormente, esta conclusión (¿inferencia?) Ciertamente está abierta al debate:

"... cada algoritmo puede ser simulado por una máquina de Turing ... un programa puede ser simulado y, por lo tanto, una máquina de Turing puede darle un significado preciso". (pág.1)
“A menudo se piensa que el problema de formalizar la noción de algoritmo secuencial fue resuelto por Church [1936] y Turing [1936]. Por ejemplo, según Savage [1987], un algoritmo es un proceso computacional definido por una máquina de Turing. Church y Turing no resolvieron el problema de formalizar la noción de algoritmo secuencial, sino que dieron formalizaciones (diferentes pero equivalentes) de la noción de función computable, y un algoritmo es más que la función que calcula (cursiva agregada p. 3)
"Por supuesto, las nociones de algoritmo y función computable están íntimamente relacionadas: por definición, una función computable es una función computable por un algoritmo ... (p. 4)


En Blass y Gurevich 2002 los autores invocan un diálogo entre "Quisani" ("Q") y "Autores" (A), utilizando a Yiannis Moshovakis como contraste, donde salen directamente y afirman rotundamente:

" R: Para localizar el desacuerdo, mencionemos primero dos puntos de acuerdo. Primero, hay algunas cosas que son obviamente algoritmos según la definición de cualquiera: máquinas de Turing, ASM de tiempo secuencial [Máquinas de estado abstracto] y similares... En segundo lugar, en el otro extremo están las especificaciones que no se considerarían algoritmos según la definición de nadie, ya que no dan ninguna indicación de cómo calcular nada ... El problema es qué tan detallada debe ser la información para que se considere un algoritmo. ... Moshovakis permite algunas cosas que llamaríamos sólo especificaciones declarativas, y probablemente usaría la palabra "implementación" para las cosas que llamamos algoritmos ". (párrafos unidos para facilitar la lectura, 2002: 22)

Este uso de la palabra "implementación" va directo al meollo de la cuestión. Al principio del artículo, Q afirma su lectura de Moshovakis:

"... [Él] probablemente pensaría que su trabajo práctico [Gurevich trabaja para Microsoft] lo obliga a pensar en implementaciones más que en algoritmos. Está bastante dispuesto a identificar implementaciones con máquinas, pero dice que los algoritmos son algo más general. Todo se reduce a que usted dice que un algoritmo es una máquina y Moschovakis dice que no lo es ". (2002: 3)

Pero los autores se mueven aquí, diciendo "[L] et se adhiere a" algoritmo "y" máquina ", y el lector queda, nuevamente, confundido. Tenemos que esperar hasta Dershowitz y Gurevich 2007 para obtener el siguiente comentario de nota al pie:

"... No obstante, si uno acepta el punto de vista de Moshovakis, entonces es la" implementación "de algoritmos lo que nos hemos propuesto caracterizar" (cf. Nota a pie de página 9 2007: 6).

2003 Caracterización de Blass y Gurevich

Blass y Gurevich describen su trabajo como una evolución de la consideración de las máquinas de Turing y las máquinas de puntero , específicamente las máquinas Kolmogorov-Uspensky (máquinas KU), las máquinas de modificación de almacenamiento de Schönhage (SMM) y los autómatas de enlace definidos por Knuth. El trabajo de Gandy y Markov también se describe como precursores influyentes.

Gurevich ofrece una definición 'fuerte' de un algoritmo (negrita agregada):

"... El argumento informal de Turing a favor de su tesis justifica una tesis más fuerte: cada algoritmo puede ser simulado por una máquina de Turing ... En la práctica, sería ridículo ... [Sin embargo,] [c] una generalización ¿Máquinas de Turing para que cualquier algoritmo, no importa cuán abstracto sea, puede ser modelado por una máquina generalizada? ... Pero supongamos que existen tales máquinas de Turing generalizadas. ¿Cuáles serían sus estados? ... una estructura de primer orden ... una un pequeño conjunto de instrucciones es suficiente en todos los casos ... el cálculo como una evolución del estado ... podría ser no determinista ... puede interactuar con su entorno ... [podría ser] paralelo y multi-agente ... [podría haber] semántica dinámica ... [los dos fundamentos de su trabajo son:] la tesis de Turing ... [y] la noción de estructura (de primer orden) de [Tarski 1933] "(Gurevich 2000, p. 1-2)

La frase anterior cálculo como evolución del estado difiere notablemente de la definición de Knuth y Stone: el "algoritmo" como programa de máquina de Turing. Más bien, corresponde a lo que Turing llamó la configuración completa (cf. la definición de Turing en Indecidible, p. 118) - e incluye tanto la instrucción actual (estado) como el estado de la cinta. [cf. Kleene (1952) p. 375 donde muestra un ejemplo de una cinta con 6 símbolos (todos los demás cuadrados están en blanco) y cómo Gödelize su estado combinado de cinta de mesa].

En los ejemplos de algoritmos vemos la evolución del estado de primera mano.

1995 - Daniel Dennett: la evolución como proceso algorítmico

El filósofo Daniel Dennett analiza la importancia de la evolución como un proceso algorítmico en su libro de 1995 Darwin's Dangerous Idea . Dennett identifica tres características clave de un algoritmo:

  • Neutralidad del sustrato : un algoritmo se basa en su estructura lógica . Por lo tanto, la forma particular en la que se manifiesta un algoritmo no es importante (el ejemplo de Dennett es la división larga: funciona igualmente bien en papel, en pergamino, en una pantalla de computadora, usando luces de neón o en escritura en el cielo). (pág.51)
  • Descuido subyacente : no importa cuán complicado pueda ser el producto final del proceso algorítmico, cada paso en el algoritmo es lo suficientemente simple como para ser realizado por un dispositivo mecánico no sensible. El algoritmo no requiere un "cerebro" para mantenerlo u operarlo. "La analogía estándar de los libros de texto señala que los algoritmos son recetas de todo tipo, diseñadas para ser seguidas por cocineros novatos " (p. 51).
  • Resultados garantizados : si el algoritmo se ejecuta correctamente, siempre producirá los mismos resultados. "Un algoritmo es una receta infalible". (pág.51)

Sobre la base de este análisis, Dennett concluye que "Según Darwin, la evolución es un proceso algorítmico". (pág. 60).

Sin embargo, en la página anterior ha ido mucho más lejos. En el contexto de su capítulo titulado "Procesos como algoritmos", afirma:

"Pero entonces ... ¿hay algún límite en lo que puede considerarse un proceso algorítmico? Supongo que la respuesta es NO; si quisiera, puede tratar cualquier proceso en el nivel abstracto como un proceso algorítmico ... Si lo que le sorprende lo desconcertante que es la uniformidad de los granos de arena [del océano] o la fuerza de la hoja [de acero templado], una explicación algorítmica es lo que satisfará su curiosidad, y será la verdad.
"No importa cuán impresionantes sean los productos de un algoritmo, el proceso subyacente siempre consiste en nada más que un conjunto de pasos inconscientes individuales [ sic ] que se suceden sin la ayuda de ninguna supervisión inteligente; son 'automáticos' por definición: el funcionamiento de un autómata ". (pág.59)

De lo anterior no queda claro si Dennett está afirmando que el mundo físico por sí mismo y sin observadores es intrínsecamente algorítmico (computacional) o si un observador que procesa símbolos es lo que agrega "significado" a las observaciones.

2002 John Searle agrega una advertencia aclaratoria a la caracterización de Dennett

Daniel Dennett es un defensor de la inteligencia artificial fuerte : la idea de que la estructura lógica de un algoritmo es suficiente para explicar la mente . John Searle , el creador del experimento mental de la habitación china , afirma que "la sintaxis [es decir, la estructura lógica] por sí misma no es suficiente para el contenido semántico [es decir, el significado]" ( Searle 2002 , p. 16). En otras palabras, el "significado" de los símbolos es relativo a la mente que los usa; un algoritmo —una construcción lógica— por sí solo es insuficiente para una mente.

Searle advierte a quienes afirman que los procesos algorítmicos (computacionales) son intrínsecos a la naturaleza (por ejemplo, cosmólogos, físicos, químicos, etc.):

La computación es relativa al observador, y esto se debe a que la computación se define en términos de manipulación de símbolos, pero la noción de "símbolo" no es una noción de física o química. Algo es un símbolo solo si se usa, trata o considera como un símbolo. El argumento de la sala china mostró que la semántica no es intrínseca a la sintaxis. Pero lo que esto muestra es que la sintaxis no es intrínseca a la física. [...] Algo es un símbolo sólo relativo a algún observador, usuario o agente que le asigna una interpretación simbólica [...] puedes asignarle una interpretación computacional a cualquier cosa. Pero si la pregunta es: "¿Es la conciencia intrínsecamente computacional?" la respuesta es: nada es intrínsecamente computacional [cursiva agregada para enfatizar]. La computación existe solo en relación con algún agente u observador que impone una interpretación computacional sobre algún fenómeno. Este es un punto obvio. Debería haberlo visto hace diez años, pero no lo hice.

-  John Searle, Searle 2002 , pág. 17

2002: Especificación de Boolos-Burgess-Jeffrey del cálculo de la máquina de Turing

Para obtener ejemplos de este método de especificación aplicado al algoritmo de suma "m + n", consulte Ejemplos de algoritmos .

Un ejemplo en Boolos-Burgess-Jeffrey (2002) (págs. 31-32) demuestra la precisión requerida en una especificación completa de un algoritmo, en este caso para sumar dos números: m + n. Es similar a los requisitos de Stone anteriores.

(i) Han discutido la función del "formato de número" en el cálculo y han seleccionado la "notación de conteo" para representar los números:

"Ciertamente, el cálculo puede ser más difícil en la práctica con algunas notaciones que con otras ... Pero ... en principio es posible hacerlo en cualquier otra notación, simplemente traduciendo los datos ... Con el propósito de enmarcar una noción de computabilidad rigurosamente definida , es conveniente utilizar la notación monádica o de conteo "(p. 25-26)

(ii) Al comienzo de su ejemplo, especifican la máquina que se utilizará en el cálculo como una máquina de Turing . Han especificado previamente (p. 26) que la máquina de Turing será de la variedad de 4 tuplas, en lugar de 5 tuplas. Para obtener más información sobre esta convención, consulte la máquina de Turing .

(iii) Anteriormente, los autores han especificado que la posición del cabezal de la cinta se indicará mediante un subíndice a la derecha del símbolo escaneado. Para obtener más información sobre esta convención, consulte la máquina de Turing . (A continuación, se agrega negrita para enfatizar):

"No hemos dado una definición oficial de lo que es para que una función numérica sea computable por una máquina de Turing , especificando cómo se deben representar las entradas o los argumentos en la máquina, y cómo se representan las salidas o los valores. Nuestras especificaciones para un k- La función de lugar de enteros positivos a enteros positivos es la siguiente:
"(a) [ Formato numérico inicial: ] Los argumentos m 1 , ... m k , ... serán representados en notación monádica [unaria] por bloques de ese número de trazos, cada bloque separado del siguiente por un solo en blanco, en una cinta de otro modo en blanco.
Ejemplo: 3 + 2, 111B11
"(b) [ Ubicación del cabezal inicial, estado inicial: ] Inicialmente, la máquina escaneará el 1 más a la izquierda de la cinta y estará en su estado inicial, estado 1.
Ejemplo: 3 + 2, 1 1 111B11
"(c) [ Cálculo exitoso - formato de número en la parada: ] Si la función que se va a calcular asigna un valor n a los argumentos que se representan inicialmente en la cinta, la máquina finalmente se detendrá en una cinta que contenga un bloque de trazos , y de lo contrario en blanco ...
Ejemplo: 3 + 2, 11111
"(d) [ Cálculo satisfactorio: ubicación del cabezal en el alto: ] En este caso [c] la máquina detendrá el escaneo del 1 más a la izquierda en la cinta ...
Ejemplo: 3 + 2, 1 n 1111
"(e) [ Cálculo fallido - Fallo al detener o detener con formato numérico no estándar: ] Si la función que se va a calcular no asigna ningún valor a los argumentos que se representan inicialmente en la cinta, entonces la máquina nunca detenerse, o se detendrá en alguna configuración no estándar ... "(ibid)
Ejemplo: B n 11111 o B11 n 111 o B11111 n

Esta especificación está incompleta: requiere la ubicación del lugar donde se colocarán las instrucciones y su formato en la máquina.

(iv) en la TABLA de la máquina de estado finito o, en el caso de una máquina de Turing Universal en la cinta, y
(v) la Tabla de instrucciones en un formato específico

Este último punto es importante. Boolos-Burgess-Jeffrey dan una demostración (p. 36) de que la previsibilidad de las entradas en la tabla permite "encoger" la tabla colocando las entradas en secuencia y omitiendo el estado de entrada y el símbolo. De hecho, el cálculo de la máquina de Turing de ejemplo requirió solo las 4 columnas como se muestra en la tabla a continuación (pero tenga en cuenta: estas se presentaron a la máquina en filas ):

Estado qk
Símbolo escaneado
Acción
Siguiente estado qk
Estado qn
Símbolo escaneado
Acción
Siguiente estado qk
Estado qk
Acción B
B-siguiente estado qkB
1 acción
1: siguiente estado qk1
1 B R H 1 1 R 2 1 R H R 2
2 B PAG 3 2 1 R 2 2 PAG 3 R 2
3 B L 4 3 1 R 3 3 L 4 R 3
4 B L 5 4 1 mi 4 4 L 5 mi 4
5 B R H 5 1 L 5 5 R H L 5

2006: la afirmación de Sipser y sus tres niveles de descripción

Para obtener ejemplos de este método de especificación aplicado al algoritmo de suma "m + n", consulte Ejemplos de algoritmos .

Sipser comienza definiendo "algoritmo" de la siguiente manera:

"Hablando informalmente, un algoritmo es una colección de instrucciones simples para llevar a cabo alguna tarea. En la vida cotidiana, los algoritmos a veces se denominan procedimientos o recetas (cursiva en el original, p. 154)
"... nuestro enfoque real de ahora en adelante está en los algoritmos. Es decir, la máquina de Turing simplemente sirve como un modelo preciso para la definición de algoritmo ... solo necesitamos estar lo suficientemente cómodos con las máquinas de Turing para creer que capturan todos los algoritmos "(p. 156)

¿Sipser quiere decir que "algoritmo" son solo "instrucciones" para una máquina de Turing, o es la combinación de "instrucciones + una (variedad específica de) máquina de Turing"? Por ejemplo, define las dos variantes estándar (cinta múltiple y no determinista) de su variante particular (no la misma que la original de Turing) y continúa, en sus Problemas (páginas 160-161), para describir cuatro variantes más ( escribir una vez, cinta doblemente infinita (es decir, izquierda y derecha infinita), reiniciar a la izquierda y "permanecer en el lugar en lugar de a la izquierda). Además, impone algunas restricciones. Primero, la entrada debe codificarse como una cadena (p. 157) y dice de las codificaciones numéricas en el contexto de la teoría de la complejidad:

"Pero tenga en cuenta que la notación unaria para codificar números (como en el número 17 codificado por el número unario 11111111111111111) no es razonable porque es exponencialmente más grande que las codificaciones verdaderamente razonables, como la notación base k para cualquier k ≥ 2". (pág.259)

Van Emde Boas comenta sobre un problema similar con respecto al modelo abstracto de computación de la máquina de acceso aleatorio (RAM) que a veces se usa en lugar de la máquina de Turing cuando se hace "análisis de algoritmos": "La ausencia o presencia de manipulación de bits multiplicativa y paralela Las operaciones son de relevancia para la correcta comprensión de algunos resultados en el análisis de algoritmos.

"... [E] aquí apenas existe algo como una extensión" inocente "del modelo de RAM estándar en las medidas de tiempo uniforme; o uno solo tiene aritmética aditiva o bien podría incluir todos los razonables multiplicativos y / o bit a bit Instrucciones booleanas sobre operandos pequeños ". (Van Emde Boas, 1990: 26).

Con respecto a un "lenguaje de descripción" para algoritmos, Sipser termina el trabajo que comenzaron Stone y Boolos-Burgess-Jeffrey (negrita agregada). Nos ofrece tres niveles de descripción de los algoritmos de la máquina de Turing (p. 157):

Descripción de alto nivel : "donde usamos ... prosa para describir un algoritmo, ignorando los detalles de implementación. En este nivel no necesitamos mencionar cómo la máquina maneja su cinta o cabezal".
Descripción de la implementación : "en la que usamos ... prosa para describir la forma en que la máquina de Turing mueve su cabeza y la forma en que almacena datos en su cinta. En este nivel no damos detalles de estados o función de transición".
Descripción formal : "... el nivel de descripción más bajo, más detallado ... que explica en detalle los estados de la máquina de Turing, la función de transición, etc.".

Notas

Referencias

  • David Berlinski (2000), The Advent of the Algorithm: The 300-Year Journey from an Idea to the Computer , Harcourt, Inc., San Diego, ISBN   0-15-601391-6 (pbk.)
  • George Boolos , John P. Burgess , Richard Jeffrey (2002), Computability and Logic: Fourth Edition , Cambridge University Press, Cambridge, Reino Unido. ISBN   0-521-00758-5 (pbk).
  • Andreas Blass y Yuri Gurevich (2003), Algorithms: A Quest for Absolute Definitions , Bulletin of European Association for Theoretical Computer Science 81, 2003. Incluye una excelente bibliografía de 56 referencias.
  • Burgin, M. Algoritmos superrecursivos , Monografías en ciencias de la computación, Springer, 2005. ISBN   0-387-95569-0
  • Davis, Martin (1958). Computabilidad e insolubilidad . Nueva York: McGraw-Hill Book Company, Inc. . Una fuente de definiciones importantes y algunos algoritmos basados ​​en máquinas de Turing para algunas funciones recursivas.
  • Davis, Martín (1965). Lo indecidible: artículos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables . Nueva York: Raven Press. Davis da comentarios antes de cada artículo. Se incluyen artículos de Gödel , Alonzo Church , Turing , Rosser , Kleene y Emil Post .
  • Dennett, Daniel (1995). La peligrosa idea de Darwin . Nueva York: Touchstone / Simon & Schuster.
  • Robin Gandy , Tesis de Church y principios para los mecanismos , en J. Barwise , HJ Keisler y K. Kunen , eds., The Kleene Symposium , North-Holland Publishing Company 1980) págs. 123–148. Los famosos "4 principios de los mecanismos [computacionales]" de Gandy incluyen el "Principio IV - El principio de causalidad local".
  • Yuri Gurevich , Sequential Abstract State Machines Capture Sequential Algorithms , ACM Transactions on Computational Logic, Vol 1, no 1 (julio de 2000), páginas 77-111. Incluye bibliografía de 33 fuentes.
  • Kleene C., Stephen (1943). "Predicados y cuantificadores recursivos" . Transacciones de la Sociedad Americana de Matemáticas . Transactions of the American Mathematical Society, vol. 53, núm. 1. 54 (1): 41–73. doi : 10.2307 / 1990131 . JSTOR   1990131 . Reimpreso en The Undecidable , p. 255ff. Kleene refinó su definición de "recursividad general" y procedió en su capítulo "12. Teorías algorítmicas" a postular "Tesis I" (p. 274); más tarde repetiría esta tesis (en Kleene 1952: 300) y la denominaría "Tesis de la Iglesia" (Kleene 1952: 317) (es decir, la Tesis de la Iglesia ).
  • Kleene, Stephen C. (1991) [1952]. Introducción a la Metamatemática (Décima ed.). Compañía editorial de Holanda Septentrional. Excelente - accesible, legible - fuente de referencia para "fundamentos" matemáticos.
  • Knuth, Donald E .. (1973) [1968]. El arte de la programación informática Segunda edición, Volumen 1 / Algoritmos fundamentales (2ª ed.). Compañía editorial de Addison-Wesley. El primero de la famosa serie de tres textos de Knuth.
  • Lewis, HR y Papadimitriou, CH Elementos de la teoría de la computación , Prentice-Hall, Uppre Saddle River, Nueva Jersey, 1998
  • AA Markov (1954) Teoría de algoritmos . [Traducido por Jacques J. Schorr-Kon y personal del PST] Pie de imprenta Moscú, Academia de Ciencias de la URSS, 1954 [es decir, Programa de Traducciones Científicas de Jerusalén, Israel, 1961; disponible en la Oficina de Servicios Técnicos, Departamento de Comercio de EE. UU., Washington] Descripción 444 p. 28 cm. Añadido tp en Traducción rusa de obras del Instituto de Matemáticas, Academia de Ciencias de la URSS, v. 42. Título original: Teoriya algerifmov. [QA248.M2943 Biblioteca de Dartmouth College. Departamento de Comercio de EE. UU., Oficina de Servicios Técnicos, número OTS 60-51085.]
  • Minsky, Marvin (1967). Computación: máquinas finitas e infinitas (Primera ed.). Prentice-Hall, Englewood Cliffs, Nueva Jersey. Minsky expande su "... idea de un algoritmo - un procedimiento efectivo ..." en el capítulo 5.1 Computabilidad, procedimientos efectivos y algoritmos. Máquinas infinitas.
  • Hartley Rogers, Jr , (1967), Teoría de funciones recursivas y computabilidad efectiva , MIT Press (1987), Cambridge MA, ISBN   0-262-68052-1 (pbk.)
  • Searle, John (2002). Conciencia y Lenguaje . Cambridge, Reino Unido: Cambridge University Press. ISBN   0-521-59744-7 .
  • Robert Soare , (1995 aparecerá en Proceedings of the 10th International Congress of Logic, Methodology, and Philosophy of Science , 19-25 de agosto de 1995, Florencia Italia), Computability and Recursion ), en la web en ??.
  • Michael Sipser , (2006), Introducción a la teoría de la computación: segunda edición , Thompson Course Technology div. de Thompson Learning, Inc. Boston, MA. ISBN   978-0-534-95097-2 .
  • Ian Stewart , Algoritmo , Encyclopædia Britannica 2006.
  • Stone, Harold S. Introducción a la organización informática y las estructuras de datos (1972 ed.). McGraw-Hill, Nueva York. Cf. en particular el primer capítulo titulado: Algoritmos, Máquinas de Turing y Programas . Su sucinta definición informal: "... cualquier secuencia de instrucciones que pueda ser obedecida por un robot, se llama algoritmo " (p. 4).
  • Peter van Emde Boas (1990), "Modelos de máquinas y simulaciones" págs. 3-66, que aparece en Jan van Leeuwen (1990), Handbook of Theoretical Computer Science. Volumen A: Algoritmos y complejidad , The MIT Press / Elsevier, 1990, ISBN   0-444-88071-2 (Volumen A)