Otras publicaciones:

12-3861t

12-3949t

Otras publicaciones:

9789871867967-frontcover

12-4583t

2 Intérpretes

Javier Blanco, Renato Cherini y Pío García

Introducción

Alrededor de la década de 1930, dos concepciones coherentes sobre lo efectivamente computable se anclan en diferentes maneras de plantear este problema. Por un lado, se caracterizan los algoritmos como maneras mecánicas de resolver problemas. Por otro, en el marco de los sistemas axiomáticos, la pregunta se coloca en la noción de calculabilidad en una lógica. Si bien los diferentes intentos de caracterizar lo efectivamente computable se demuestran equivalentes (lo que luego se llama la tesis de Church-Turing), no es sino hasta que Turing explicita restricciones estrictas sobre qué significa un paso mecánico de cálculo, que los participantes de estas discusiones (Church, Kleene, Herbrand, Gödel, entre otros) llegan al consenso de que el problema está resuelto.

Para Turing (1936) las reglas que determinan el proceso de computación efectiva son seguidas por el “computer”, una persona actuando rutinariamente con percepción y memoria limitadas, que se cristalizan en la utilización de papel y lápiz, y operaciones elementales con ellos. Así, computar es seguir reglas prescriptas de manera simple, que en el caso del formalismo propuesto, las máquinas de Turing, son tan elementales que ya no es posible ni necesario descomponerlas. Turing justifica a partir de un análisis conceptual que lo computable es lo que puede ser calculado de esta manera.

Gandy (1980) extiende la idea de computación a partir de mecanismos no-humanos, caracterizándolos de forma abstracta y determinando el máximo poder de cómputo que puede obtenerse. Uno de sus objetivos explícitos es independizarse de cualquier formalismo particular, presentando solo restricciones estructurales que limitan lo computable por esos mecanismos. De alguna manera, lo que se obtiene es un meta-formalismo que intenta capturar las posibles maneras de definir mecanismos computacionales y las restricciones para ser considerados tales.

Está generalmente aceptado que la caracterización de Turing, luego consolidada por Gandy, captura la noción de computación. Sin embargo, preguntas como qué es computar, cuando un sistema computa y en qué sentido es computacional, y cuál es la relación entre los aspectos abstractos y concretos de la computación, no se resuelven definitivamente con su propuesta. Tanto la filosofía de la mente como la filosofía y las prácticas de las ciencias de la computación son una fuente de problemas para las concepciones de computación.

El problema de la relación entre computación abstracta y concreta incluye la cuestión de la naturaleza dual de los programas, con sus derivas en aspectos metodológicos (como la verificación formal y el testing de programas), la preeminencia entre la teoría de la computación y la construcción de computadoras, e incluso la eventual bifurcación de la tesis Church-Turing para sistemas abstractos y físicos (Piccinini, 2015).

En ocasiones se cuenta la historia de la computación como si la construcción efectiva de una computadora física supusiera la elucidación previa de una noción abstracta de computación. Esta forma de defender la preeminencia de una concepción abstracta de computación se enfrenta con la evidencia histórica de la potencia expresiva y la flexibilidad de dispositivos como los de Babbage, diseñados cien años antes que las discusiones de 1930 (Davis y Weyuker, 1994). Esto sugiere que para construir una computadora no haría falta una noción abstracta previa de computación, pero sí parece necesaria para reconocer un artefacto como computadora y definir sus límites computacionales.

Por otro lado, la división entre aspectos abstractos y concretos de la computación a veces se presenta de tal manera que implica una diferenciación ontológica (Eden, 2007). Así, un programa debería entenderse como una estructura sintáctica que obedece las leyes de la lógica (program-script) o como una estructura causal sujeta a la leyes de la física (program-process). La ineludible necesidad de un sustrato material que lleve adelante el proceso de computación otorgaría preeminencia a la segunda concepción. Esto, junto a la dificultad para relacionar el reino de lo abstracto con el mundo material, parece bregar por soluciones que relativizan cualquier conocimiento que no provenga de una experimentación empírica, lo que choca de lleno con las prácticas actuales en el ámbito de las ciencias de computación.

Respecto a la identificación de cuando un sistema computa o, de forma más general, cuando es computacional, se puede señalar al pancomputacionalismo como la concepción que parece trivializar la noción de cómputo. La discusión sobre el pancomputacionalismo comienza en el campo de la filosofía de la mente y luego es tomada por la filosofía de la computación. Un problema que aparece en cualquier definición de computación es saber si puede servir para distinguir sistemas que computan de aquellos que no. Putnam (1988) y Searle (1990), entre otros, elaboran argumentos que mostrarían la ausencia de rasgos específicos en la idea de computación que se expresa como pancomputacionalismo: “todo computa”; y otras veces como relativismo semántico: “la computación está en el ojo del observador”.

Estas críticas toman diferentes formas. Quizá la mejor formulada es la que Putnam expresa en forma de teorema, en el que muestra que cualquier sistema de transición (sin entrada ni salida de datos) es implementado por cualquier sistema físico abierto con suficientes estados. La idea es que los estados abstractos de una computación pueden ser realizados por cualquier (clase de equivalencia de) estado(s) físico(s). Si se consideran sistemas de entrada-salida el teorema se debilita, pero igualmente sigue planteando cierta trivialización de la noción de cómputo: cualquier sistema de transición finito es implementado por cualquier sistema físico abierto que exhibe la relación adecuada de entrada-salida.

En este artículo proponemos una noción relacional de implementación y computación, a través del concepto de intérprete. Computar es un proceso determinado por el vínculo prescriptivo entre un programa y un comportamiento. La implementación que determina un sistema computacional como tal puede ser comprendida como una relación de realización de una descripción abstracta de este vínculo, que cierra el gap ontológico entre los aspectos abstractos y físicos de la computación.

La propiedad de programabilidad, i.e. la capacidad de un sistema de recibir una prescripción arbitraria y comportarse de acuerdo con ella, es central. Así, creemos que el concepto de intérprete permite resumir los aspectos centrales que caracterizan la noción de computación. Más aun, permite construir jerarquías de sistemas computacionales que habilitan, ya no a contestar por sí o no la pregunta sobre cuándo un sistema es computacional, sino a describir grados de computación de acuerdo con la programabilidad de los sistemas.

Funciones de interpretación y sistemas computacionales

Un intérprete es una noción general que provee un marco uniforme para analizar, caracterizar y relacionar mecanismos físicos, como calculadoras y computadoras; una persona actuando mecánicamente, como el computador de Turing, o haciendo reducciones de un término lambda; formalismos matemáticos, como la Máquina de Turing Universal; o incluso sistemas computacionales ideales que están más allá de la compatibilidad de Turing, como las computadoras oráculo.

Uno de los aspectos comunes a todos los sistemas mencionados es que pueden caracterizarse por sus posibles comportamientos. Por comportamiento entendemos una descripción idealizada de las ocurrencias de ciertos eventos considerados relevantes. Las diferentes formas de observar un sistema determinan conjuntos diferentes de comportamientos. La parcialidad en la forma de observar solo lo considerado relevante abre la puerta a múltiples realizaciones de un mismo comportamiento, i.e. diferentes configuraciones de un sistema pueden ser vistas como equivalentes y consideradas como el mismo comportamiento. Algunos ejemplos de comportamientos que se consideran en la literatura son la salida de datos, trazas de ejecución, grafos de procesos, conjuntos de fallas, interleavings de acciones atómicas, etc. Una definición más precisa de comportamiento solo tiene sentido en un marco particular. Aquí evitamos hacer específica la definición, ya que nos interesa poder capturar el concepto de sistema computacional en su generalidad y consideramos que nuestros resultados se aplican a todos los comportamientos mencionados. A pesar de esto, vamos a ilustrar nuestros ejemplos con el caso más común: la salida de datos.

La idea central que presentamos es que un intérprete produce comportamientos a partir de una codificación de estos que acepta como entrada. La relación entre tal entrada, que llamamos programa, y el comportamiento que prescribe, se caracteriza mediante una función de interpretación.

 

Definición 1 (función de intepretación)

Dado un conjunto B de posibles comportamientos, un conjunto P de programas, y un conjunto D de datos, una función de interpretación es una función i P → (D → B), que asocia a todo comportamiento b B un programa p P y un dato d D. Con A → B denotamos el conjunto de funciones totales de A en B.

Usualmente nos referimos a una función de interpretación i ∈ P → B, asumiendo que los datos de entrada se encuentran codificados con el mismo programa. Cuando los elementos de P se construyen utilizando algún lenguaje, lo llamamos lenguaje de programación. Cuando consideramos los comportamientos de salida de datos, suele darse que B = D.

Las nociones de función de interpretación y programa son relacionales. Una función de interpretación es tal cuando prescribe comportamientos a un conjunto dado de programas; es una función de interpretación para tal conjunto. Un programa es tal cuando existe una función de interpretación para él. No hay nada intrínseco en ser un programa más allá de la relación con una función de interpretación. Por ejemplo, los números de Gödel permiten considerar los números como programas (Davis y Weyuker, 1994). De esta manera, los conceptos de función de interpretación, programa (e incluso lenguaje de programación) son interdefinibles.

imagen2 cap 2

Figura 1. Relación de implementación

Decimos que un sistema I es computacional respecto a una función de interpretación i (o equivalentemente I implementa i) cuando se comporta de acuerdo con la prescripción establecida por i.

Definición 2 (sistema computacional)

Dados un sistema I y una función de interpretación i P → B, decimos que I implementa i si es capaz de recibir una realización del programa p como entrada y sistemáticamente producir los eventos relevantes caracterizados por el comportamiento b, tal que i.p = b.

Ni los estados internos, ni la forma particular que tiene I para producir el comportamiento son relevantes para satisfacer el criterio de implementación, a excepción, por supuesto, de que tales aspectos formen parte de lo considerado relevante. La figura 1 muestra la implementación de una función de interpretación como una relación entre relaciones. En la versión “concreta”, el comportamiento usualmente toma la forma de un proceso (el llamado program-process) o el estado final de un proceso tal, cuya forma particular está establecida por el sistema pero puede ser comprendido en términos de los atributos observables definidos como relevantes. Consideramos que el programa mismo (el program-script) es parte fundamental del sistema, y como tal, debe ser considerado también en su forma “concreta”. Esta idea, que no es nueva, como muestra la siguiente cita de (Moor, 1978), generalmente es olvidada en los trabajos que intentan dar cuenta de la noción de computación:

It is important to remember that computer programs can be understood on the physical level as well as the symbolic level. The programming of early digital computers was commonly done by plugging in wires and throwing switches. Some analogue computers are still programmed in this way. The resulting programs are clearly as physical and as much a part of the computer system as any other part. Today digital machines usually store a program internally to speed up the execution of the program. A program in such a form is certainly physical and part of the computer system.

La presencia de una realización del programa como parte del sistema es quizá la mayor diferencia entre una descripción computacional de un sistema (cuando el programa no forma parte del sistema) y un sistema computacional (cuando el ahora presente programa actúa como una prescripción). La realización del programa puede darse de diferentes maneras (un texto representado con una configuración eléctrica de la memoria, la distribución de interruptores en una computadora hard-programmed, la tabla de transiciones de una máquina de Turing escrita en papel, etc.).

De esta manera, la principal característica de un sistema computacional es que es programable: admite la codificación de una variedad de sus comportamientos. El grado de programabilidad del sistema está dado por la variedad de comportamientos que el lenguaje de programación subyacente es capaz de codificar, y es la característica distintiva del sistema computacional como tal. Si consideramos que un sistema es computacional cuando es programable, entonces “ser computacional” es una propiedad que puede ser establecida solo en relación con un conjunto de comportamientos y una codificación correspondiente. En otras palabras, la propiedad de ser computacional no tiene sentido independientemente de un conjunto de comportamientos y un conjunto de programas.

imagen cap 2

Figura 2. Intérprete

La distinción entre la prescripción dada por una función de interpretación y su implementación refuerza la idea de que “ser un sistema computacional” es principalmente una propiedad relacional abstracta de los sistemas, y por lo tanto, no existe ningún sistema inherentemente computacional. Sin embargo, mientras que es necesaria una contraparte física para llevar adelante el proceso de la computación, la propiedad de ser un sistema computacional está determinada por la prescripción que es implementada por el sistema.

Definición 3 (intérprete y computación)

Utilizamos el término intérprete para denotar un sistema computacional en el sentido de la definición 2, reforzando la idea de que la prescripción es una parte constitutiva del sistema para que sea considerado computacional. Así comprendemos una computación como el resultado producido por un intérprete dada cierta prescripción como entrada, pero no simplemente el resultante proceso, o estado final, del sistema subyacente (fig. 2).

La propiedad de “ser un intérprete” para conjuntos dados de programas y comportamientos puede ser satisfecha por diferentes sistemas. La relación de implementación puede realizarse de diferentes maneras. Por ejemplo, una computadora de ADN o una computadora cuántica no se asemejan en su estructura a una computadora digital tradicional. De manera inversa, un mismo sistema puede implementar diferentes funciones de interpretación. Como mínimo, el subsistema de entrada debe ser modificable para permitir la recepción de un programa (y sus datos de entrada) y el subsistema de salida debe poseer los suficientes estados diferentes como para permitir reconocer la computación realizada. La prueba o justificación de la correspondencia entre la prescripción y la producción de un sistema puede requerir diferentes métodos, ya sean matemáticos o empíricos, dependiendo de la tecnología elegida para la implementación.

Nuestra noción de intérprete generaliza la definición usual en el área de compiladores y teoría de lenguajes, donde un intérprete es un programa de una computadora digital. Esta idea generalizada está implícita en los textos clásicos de compatibilidad, por ejemplo, en Jones, 1997:

 

The “computing agent” then interprets the algorithm; it can be a piece of hardware, or it can be software: an interpreter program written in a lower-level programming language. Operationally, an interpreter maintains a pointer to the current instruction within the algorithm’s instruction set, together with a representation of that algorithm’s current storage state. Larger algorithms correspond to larger interpreted programs, but the interpreter itself remains fixed, either as a machine or as a program.

Tanto en la teoría como en la práctica de las ciencias de la computación, el uso de intérpretes es ubicuo, aunque no siempre son presentados como tales. Los siguientes ejemplos ilustran esta afirmación.

Ejemplo 1

El formalismo de las máquinas de Turing define elementos estructurales, como una cinta infinita, un cabezal de lectura/escritura, un conjunto finito de estados mentales, acciones elementales, como mover la cinta a la izquierda o derecha, leer o escribir un símbolo en la cinta, etc., y sus relaciones; y prescribe su desempeño de acuerdo con una tabla de transiciones. Cada tabla de transiciones (una máquina de Turing particular) es un programa, y su resultado son los valores escritos en la cinta.

Una posible implementación es un “computer”, una persona provista de papel y lápiz, actuando mecánicamente, obedeciendo las reglas de la tabla de transiciones, utilizando percepción y memoria limitadas. Tanto el programa como el comportamiento resultante se realizan como símbolos en el papel.

Los comportamientos producidos por las máquinas de Turing son el conjunto de valores resultantes de las funciones computables sobre números (según la tesis de Church-Turing).

Ejemplo 2

El diseño de una computadora digital moderna establece el conjunto de operaciones elementales del microprocesador sobre valores simples y estructurados, ambos, las operaciones y los valores, codificados como palabras de bits, llamadas código de máquina, y la forma en que el sistema de memoria los almacena.

Una computadora particular, construida de acuerdo con el diseño anterior, ejecuta el código de máquina de un programa y produce el valor resultante, ambos realizados como patrones eléctricos en los chips de memoria. La relación de implementación está garantizada por la teoría detrás de la tecnología electrónica.

El conjunto de comportamientos puede limitarse a los valores computados (coincidiendo con los comportamientos de las máquinas de Turing), o puede definirse teniendo en cuenta detalles relevantes del proceso de computación, como paralelismo, predicación, etc.

Ejemplo 3

Una computadora hard-programmable, como la ENIAC, es un intérprete de los mismos comportamientos mencionados anteriormente. En este caso, el programa y los datos se realizan como ciertas configuraciones de switches y cables, mientras que el resultado está dado por la configuración del hardware.

Jerarquías de intérpretes

En lugar de trazar una línea entre los sistemas que son computacionales y los que no, el concepto de intérprete permite hablar de niveles de computacionalismo, con sistemas que aceptan lenguajes Turing completos en la cima (por ejemplo, las computadoras digitales) y sistemas elementales que implementan intérpretes elementales en lo más bajo (como una piedra, o un balde de agua).

La necesidad de considerar una jerarquía de intérpretes no solo aparece cuando necesitamos distinguir hasta qué punto un sistema físico computa, sino también en el dominio de formalismos abstractos, como las máquinas de Turing. Por ejemplo, mientras que está fuera de la discusión que el formalismo como un todo, o en otras palabras, el conjunto de todas las máquinas de Turing es un caso paradigmático de un sistema computacional, es menos claro cuándo una máquina de Turing particular computa, o mejor, cuán potente o programable es. Consideremos una máquina de Turing de sumar, que toma la representación unaria de dos números y los concatena. Podríamos afirmar que la máquina computa, o más aun que es un sistema computacional. Algunos autores pueden estar de acuerdo con la primera afirmación pero no con la segunda. En esta sección, introducimos dos jerarquías diferentes para comparar intérpretes, de acuerdo con dos nociones importantes en el campo de la teoría de la computibilidad: simulación e interpretación. La primera permite relacionar intérpretes de acuerdo con su poder computacional, i.e. el conjunto de comportamientos que pueden producir. La segunda define una relación más fuerte, de acuerdo con su programabilidad, que implica, bajo ciertos requerimientos, a la anterior, y caracteriza además la relación comúnmente llamada “implementación”.

La primera jerarquía de intérpretes se define en términos de un simple pre-orden entre las funciones de interpretación, teniendo en cuenta el conjunto de comportamientos considerados por cada una de ellas.

 

Definición 4 (simulación de comportamientos)

Dadas las funciones de intepretación i P → B e i’ P’ → B’, y los intérpretes I e I’ respectivamente, decimos que I se comporta al menos como I’, denotado por I’ I, si B’ B. En el caso de que también valga I I′ decimos que los intérpretes son comportamentalmente equivalentes.

Usualmente los sistemas computacionales se comparan en términos de los lenguajes de programación que aceptan. En lugar de organizar una jerarquía de intérpretes en términos de los comportamientos que producen, es posible relacionarlos haciendo foco en los lenguajes de programación que soportan.

Eden y Turner (2007) presentan una caracterización de los lenguajes de programación en función de la completitud de Turing, intentando dejar fuera ciertos candidatos antiintuitivos. Sin embargo esta restricción parece demasiado fuerte, dado que algunos lenguajes que no son Turing completos pueden ser considerados lenguajes de programación genuinos, por ejemplo: el lenguaje de demostradores de teoremas como Coq e Isabelle, que solo permiten funciones que terminan; algunos lenguajes derivados de la teoría de tipos; o el lenguaje propuesto por Turner (1995), que consta de funciones primitivas recursivas de alto orden. Incluso un lenguaje mucho más simple, como el de una calculadora electrónica, es un lenguaje de programación interesante, aunque poco potente.

Para definir una jerarquía basada en los lenguajes de programación, introducimos la noción de función de compilación como una función que traduce un programa p en otro p’ equivalente, posiblemente escrito en un lenguaje de programación diferente.

 

Definición 5 (función de compilación y simulación de lenguajes)

Dadas dos funciones de interpretación i P → B e i’ P’ → B’, decimos que c P’ → P es una función de compilación entre P’ y P si para cada p’ P′:

i.(c.p’) = i’.p’

En este caso decimos que I simula a I’, denotado por I’ c I. En caso que también valga I c’ I’ (para c’ P → P’) decimos que los intérpretes son lenguaje-equivalentes.

Como una consecuencia directa de esta definición, el orden implica lógicamente el orden previamente definido. Lo recíproco también es cierto.

Lema 1

Dados dos intérpretes I e I’:

1. Si I’ I, entonces existe c P’ → P tal que I’ c I.

2. Si I c I’ (para alguna c P → P’), entonces I I′.

Ejemplo 4

Sea P un lenguaje de programación que consiste de dos instrucciones: sum.x y mult.x que producen respectivamente la suma y multiplicación de x con el valor almacenado en un acumulador, y almacenan el resultado en él. Sea I un intérprete para este lenguaje que acepta secuencias de tales instrucciones como programas. Así I se comporta como un evaluador de expresiones algebraicas conformadas por + y ×.

Sea P’ otro lenguaje de programación que consiste de tres operaciones: sum.x definida como la anterior, A que accede al valor almacenado en el acumulador, y repeat.x.S que repite la secuencia de instrucciones S una cantidad x de veces. Sea I’ un intérprete para P’.

Es fácil de demostrar que existe una función de compilación que traduce cada instrucción mult.x en un programa repeat (x-1).(sum.A). Por lo tanto I’ simula a I. Lo opuesto no es verdadero, ya que I’ se comporta como un evaluador de expresiones algebraicas conformadas por +, × e hiper-exponenciación.

Más allá del hecho de que los órdenes previamente definidos son equivalentes, el segundo tiene su propia importancia ya que los lenguajes de programación y la traducción entre ellos juegan un rol fundamental en las prácticas de las ciencias de la computación. Ya que son dispositivos diseñados, los intérpretes se construyen usualmente de acuerdo con un lenguaje de programación predefinido en lugar del conjunto de comportamientos subyacentes, que permanece implícito. Más aun, suele suceder que el conjunto de comportamientos no es (o no puede ser) descripto de forma precisa. Como un caso particular, el conjunto de las funciones efectivamente computables no puede ser definido excepto por la relación entre diferentes formalismos, conocida como la tesis de Church-Turing.

Lema 2 (tesis de Church-Turing)

Las funciones recursivas, las máquinas de Turing y un lenguaje imperativo estándar, etc., vistos como los respectivos intérpretes R, T, I de las “funciones efectivamente computables”, son lenguaje-equivalentes, y para cualquier otro intérprete I’ tal que R I’ necesariamente vale que I’ R.

Consideremos dos intérpretes I e I’, y sus funciones i ∈ P → (D → B) e i’ ∈ P’ → (D’ → B’) respectivamente. La jerarquía definida por los órdenes ≤ y ⊆ especifica que un intérprete, por caso I, puede simular a otro, I’, y consecuentemente comportarse como tal, pero no estipula cómo se lleva adelante esa simulación. No es un requerimiento que la función de compilación se pueda ejecutar mecánicamente, ni que sea una función computable. En la literatura se propone el concepto de compilador como un procedimiento mecánico para traducir efectivamente un programa escrito en un lenguaje de programación a otro. Si requerimos que la traducción sea ejecutada por I, esto es, existe un compilador comp ∈ P, la condición de la definición 5 se transforma en

i.(i.comp.p’) = i’.p’

Aquí i.comp.p’ es la “ejecución” del compilador con el dato de entrada p’ que resulta en otro programa, que es la entrada de i. Notar que debe suceder que P ⊆ D.

Dado el rol central que tiene la noción de compilador en la teoría de la computación, se puede argumentar que puede reemplazar a la noción de intérprete para determinar cuándo un formalismo sintáctico es un lenguaje de programación, y consecuentemente, cuándo un sistema es computacional. Sin embargo el concepto de intérprete es más primitivo, porque para que un compilador (o más en general, cualquier programa) sea “ejecutado”, siempre es necesario un intérprete (como se observa a partir de la ecuación anterior). Mientras que el concepto de compilador tiene cierta capacidad explicativa, que permite comprender un lenguaje de programación en términos de otro lenguaje más primitivo, es un intérprete quien finalmente caracteriza los comportamientos que tal lenguaje es capaz de codificar. La ecuación anterior nos permite decir informalmente que “la composición de un intérprete con (la ejecución de) un compilador resulta en un intérprete”.

Requerir que una función de compilación pueda ser codificada como un programa para un intérprete dado impone condiciones más fuertes no solo en los comportamientos que tal intérprete produce, sino también en su programabilidad. Siguiendo esta dirección, es posible definir un orden lógicamente más fuerte que ⊆ (y que ≤).

Definición 6 (interpretación)

Dadas dos funciones de intepretación i P → B e i’ P’ → B’, y respectivos intérpretes I e I’, e int P un programa particular que toma elementos de P’ como entrada, decimos que int es un programa-intérprete para P’ si

i.int = i’

En este caso decimos que I interpreta a I’, denotado como I’ I. Si además vale que I I’ decimos que I e I’ son inter-interpretables. Cuando I I decimos que I es auto-interpretable, que es una propiedad bien conocida de los sistemas Turing completos.

La diferencia entre las jerarquías de simulación e interpretación es sutil. Nuevamente consideremos dos intérpretes I e I’, que implementan las funciones i ∈ P → (D → B) e i’ ∈ P’ → (D’ → B’) respectivamente. Mientras que el orden I’ ≤ I determina una relación de ser parte entre los comportamientos subyacentes (i.e. B’ ⊆ B), el orden I’ ∝ I caracteriza una relación de ser un elemento (i’ ∈ D → B). Como consecuencia, no solo I puede finalmente comportarse como I’, sino que el lenguaje de programación de I es capaz de codificar en un único programa el conjunto completo de comportamientos del intérprete I’.

Para clarificar la distinción, supongamos que I’ ≤ I y I’ ∝ I. Así, combinando las condiciones de las definiciones 5 y 6 obtenemos

i.(c.p’) = i.int.p’

En el lado izquierdo, c.p’ es un programa diferente para cada p’. En el lado derecho, el programa es siempre el mismo, int, mientras que p’ es solo el dato de entrada de int.

La ecuación anterior permite entrever la relación lógica entre y. Si I’ I vale, es fácil de imaginar cómo definir una función de compilación de P’ a P: asignar a cada p’ P’ un programa como int pero con p’ ocupando el lugar del parámetro de entrada.

Lema 3

Sean i P → B e i’ P’ → B’ dos funciones de intepretación, I e I’ los intérpretes que implementan i e i’ respectivamente. Si I’ I, entonces I’ I.

Interpretación e implementación

Reconsideremos la definición de la relación de interpretación. El nombre elegido para referirnos al programa característico int puede resultar confuso en principio, pero no es arbitrario. Previamente introducimos el concepto de intérprete como una generalización del concepto, comúnmente comprendido como un programa que “ejecuta” otros programas. El programa-intérprete int es tal programa.

Además, los programas-intérpretes juegan un papel fundamental en la relación de implementación. Un programa-intérprete es un intérprete de acuerdo con la relación de implementación que presentamos, en el siguiente sentido. Consideremos dos funciones de interpretación i ∈ P → B e i’ ∈ P’ → B’, e I un sistema computacional respecto a i. Consideremos además que existe un programa-intérprete int ∈ P, tal que

i.int = i’

Es fácil ver que el intérprete I instanciado con int (i.e. fijando int como la entrada de I) satisface el criterio para ser considerado una implementación de la función de interpretación i’, y por lo tanto es un intérprete. Esto nos permite decir informalmente que “la composición de un intérprete con un programa-intérprete es un intérprete”. Además, para cualquier otro sistema I’ que implementa i’, se satisface que I’ ∝ I.

Cabe remarcar que no es el mero sistema (físico) I quien implementa a i’, sino que la función de interpretación i interviene en la relación. Así es que I, considerado como sistema computacional respecto a i y provisto con int, es también computacional respecto a i’. Esto muestra que la relación de implementación es lo suficientemente general como para considerar no solo sistemas “concretos”.

Ejemplo 5

Según el ejemplo 1, el “computer” es una implementación del formalismo de las máquinas de Turing (T). Ahora, la Máquina de Turing Universal (utm), “ejecutada” por el computor, es un intérprete que toma una codificación de la tabla de transición de una máquina arbitraria junto con su entrada, y se comporta como ella. En otras palabras

T.utm = T

Como consecuencia, el formalismo de las máquinas de Turing es auto-interpretable, y el programa particular utm codifica el poder computacional completo del formalismo.

Ejemplo 6

El ejemplo más común de un intérprete es un programa-intérprete ejecutándose en una computadora digital, que “ejecuta” un script escrito en un lenguaje de programación corriente. El script, sus datos y el valor resultante son codificados en alguna estructura de datos del programa-intérprete. El conjunto de comportamientos queda definido por la semántica del lenguaje.

Por ejemplo, los programas perl y python son programas-intérpretes de los lenguajes homónimos, y ghci para el caso de Haskell.

Los programas-intérpretes se utilizan extensivamente en la teoría de la computación y en la ingeniería de software para dar cuenta de la complejidad de los sistemas informáticos. Y las funciones de interpretación juegan un papel importante, porque son utilizadas profusamente para mediar entre las relaciones de implementación. Es muy común “componer” diversos programas-intérpretes en una pila, cada uno de los cuales presenta una “interfaz abstracta” (dada por la respectiva función de interpretación), ocultando las particularidades de su funcionamiento (que podríamos denominar sus “detalles de implementación”), que se basan en la funcionalidad provista por el programa-intérprete de un nivel más abajo. En el nivel inferior siempre encontramos un intérprete, encargado de producir el comportamiento.

Ejemplo 7

Una máquina virtual Java es un programa-intérprete para el lenguaje de programación Java. A su vez está diseñada para correr sobre un sistema operativo dado, que provee una abstracción de la computadora digital sobre la que el mismo se ejecuta. Esta abstracción es caracterizable por una función de interpretación, y el sistema operativo es luego, en tanto programa, un programa-intérprete. Finalmente el sistema operativo se define en términos de la abstracción que provee el lenguaje máquina propio de la computadora, sobre la electrónica que lo implementa.

La composición de programas-intérpretes es muy común incluso en la arquitectura y la organización interna de los sistemas informáticos. La relación de implementación que definimos generaliza la relación más específica, conocida como “implementación” en la comunidad de ciencias de la computación, entre “especificaciones” y “programas” escritos en un lenguaje de programación. Debemos tener en cuenta que cualquier programa puede ser considerado como un programa-intérprete elemental de una función de interpretación que relaciona los datos de entrada con la salida de tal programa. Es decir, su “especificación” puede ser vista como una función de interpretación. Y en la tarea de programar una “implementación” de una “especificación” dada, siempre se asume la existencia de un programa-intérprete que garantiza la semántica pretendida del lenguaje, y que es el encargado de ejecutar tal programa.

Ejemplo 8

Consideremos la “especificación” de un tipo abstracto de datos T, y un módulo M programado en el lenguaje Python que la “implementa”. El programa-intérprete python ejecutándose con el módulo M cargado es ahora un intérprete del lenguaje de programación Python extendido con el tipo abstracto T.

El pancomputacionalismo

El pancomputacionalismo es la tesis que afirma que todo sistema físico abierto realiza cualquier computación. Como consecuencia, la noción de computación se volvería trivial a través del concepto de realización en un sistema físico. El primer argumento riguroso a favor del pancomputacionalismo ilimitado es presentado por Putnam (1988), quien sostiene que todo sistema abierto ordinario implementa cualquier sistema de transición finito abstracto (sin entradas ni salidas). Primero asume que los campos electromagnéticos y gravitacionales son continuos y que un sistema físico está en diferentes estados maximales en diferentes momentos. Luego considera un sistema de transición finito arbitrario cuya función de transición da lugar a la secuencia de estados ABABABA. Toma un sistema físico arbitrario S en un intervalo de tiempo arbitrario, desde las 12:00 hasta las 12:07, y sostiene que S implementa la secuencia ABABABA. Dado que, tanto el sistema de transición como el sistema físico son arbitrarios, el argumento generaliza a cualquier sistema de transición y cualquier conjunto de estados físicos. El núcleo del argumento es el siguiente:

Let the beginnings of the intervals during which S is to be in one of its stages A or B be t1, t2, …, tn (in the example given, n = 7, and the times in question are t1=12:00, t2=12:01, t3=12:02, t4=12:03, t5=12:04, t6=12:05, t7=12:06). The end of the real-time interval during which we wish S to “obey” this table we call tn+1 (tn+1=t8=12:07, in our example). For each of the states ti to ti+1, i=1, 2, …, n, define a (nonmaximal) interval state si which is the “region” in phase space consisting of all the maximal states St(S, t) with ti ≤ t < ti+1 (i.e., S is in si just in case S is in one of the maximal states in this “region”). Note that the system S is in s1 from t1 to t2, in s2 from t2 to t3, …, in si from ti to ti+1 (left endpoint included in all cases but not the right – this is a convention to ensure the “machine” is in exactly one of the si at a given time.) The disjointness of the states si is guaranteed by the Principle of Noncyclical Behavior.

Define A = s1 or s3 or s5 or s7; B = s2 or s4 or s6. Then, as is easily checked, S is in state A from t1 to t2, from t3 to t4, and from t5 to t6, and from t7 to t8, and in state B at all other times between t1 and t8. So S has the table we specified, with the states A, B we just defined as the realizations of the states A, B described by the table.

En resumen, Putnam toma un sistema físico arbitrario con dinámica continua, parte su dinámica en intervalos de tiempos discretos, y luego secuencia las partes de manera que se correspondan con una secuencia arbitraria de estados computacionales abstractos. Esto es lo que se conoce como el simple mapping account. Así concluye que todo sistema físico implemente cualquier sistema de transición finito.

Tiempo después, Searle (1990) propone un argumento similar. De acuerdo con este trabajo, si tenemos en cuenta la caracterización de Turing se dan las siguientes consecuencias:

1. For any object there is some description of that object such that under that description the object is a digital computer. 2. For any program and for any sufficiently complex object, there is some description of the object under which it is implementing the program.

Existen diferentes intentos de dar cuenta del desafío del pancomputacionalismo. Para algunos investigadores, el principal problema reside en cómo encontrar características o propiedades específicas de la computación para imposibilitar el pancomputacionalismo. Para otros autores, la pregunta es cómo definir la realización de una descripción de un sistema computacional en un sistema físico. Copeland (1996) sugiere el concepto de “arquitectura”, junto con la idea de modelos “honestos”, como una respuesta. Piccinini (2007) presenta la noción de mecanismo como una propiedad específica de la computación. Scheutz (1999) trabaja sobre la idea de “realización de una función” y sus condiciones físicas como el concepto clave contra el pancomputacionalismo. Chalmers (1996) intenta evitar la trivialización del concepto de computación sosteniendo que el argumento de Putnam no considera una teoría adecuada de implementación.

Copeland analiza la noción de computación, intentando establecer criterios para explicar cómo identificar computaciones en sistemas particulares, y cómo discernir si un sistema está computando o no. Distingue por un lado la “arquitectura” de un sistema, que caracteriza de forma axiomática su programabilidad en términos de operaciones elementales. Cada axioma es de la forma: si se da la configuración abstracta x, entonces se ejecuta la operación o entre los valores dados por la configuración. Por otro lado, introduce la noción de “algoritmo”, que utiliza tales operaciones para computar, a partir de los valores de entrada de una función dada f, los valores de salida de f. Pero luego, para utilizar una relación respecto a modelos como la usual en lógica, los une en una teoría lógica SPEC en la cual es imposible distinguirlos. Para Copeland, computar es ejecutar un “algoritmo”. De forma más precisa, que una entidad e compute una función f equivale a que exista una correspondencia entre los estados de e y las configuraciones de SPEC de manera que todos los axiomas de la “arquitectura” se validen. Los estados de e se distinguen a partir de un esquema de labeling L determinado. Dicho de otra forma, e computa f si (e, L) es un modelo de SPEC.

Lamentablemente, y como principal consecuencia de unir un “algoritmo” y la “arquitectura”, los argumentos de Putnam y Searle se aplican aquí también: es posible especificar un esquema de labeling para cada computación. Para esquivar esta dificultad, Copeland requiere que el esquema de labeling no sea ex post facto, que puede ser un buen requerimiento metodológico, pero es difícil de establecer sobre un sistema dado. Para evitar el pancomputacionalismo, Copeland requiere que los modelos de SPEC sean “honestos”, donde esto significa que las relaciones lógicas deben interpretarse de la forma que se pretende, satisfaciendo ciertos contrafácticos de forma que las operaciones elementales de la “arquitectura” no puedan interpretarse de forma no estándar. Pero esto último arrastra el mismo problema original: ¿cómo podemos caracterizar que cierto modelo representa el pretendido significado de computación?

Un enfoque interesante, con el cual nuestra propuesta establece un diálogo fértil, es la explicación mecanicista de Piccinini. Su tesis principal es que una computadora es un tipo especial de mecanismo (i.e. un sistema sujeto a una descripción mecanicista) cuya función es generar strings de salida, a partir de ciertos strings de entrada y (posiblemente) los estados internos, de acuerdo con una regla general que describe el comportamiento de la computadora en cuestión. La confiabilidad del mecanismo computacional es capturada por el hecho de que es posible reconocer una correspondencia entre ciertas configuraciones temporales y espaciales de entidades físicas o estados del sistema (dígitos) y la operación de concatenación de los símbolos formales (que conforman los string arriba mencionados), que da lugar a una relación de realización entre la descripción abstracta del sistema computacional y el mecanismo. Basado en esta caracterización, Piccinini (2007 y 2008) propone una taxonomía de diferentes tipos de computadoras de acuerdo con sus componentes y las interacciones entre ellos.

Aunque el enfoque de Piccinini establece una taxonomía bien organizada de diferentes realizaciones de sistemas computacionales, y más aun, provee una explicación completa de cuando un sistema es una computadora sin recurrir a ninguna caracterización semántica, no provee un criterio de demarcación claro. Por un lado, el enfoque es demasiado reducido, dado que la caracterización estructural funciona bien con la tecnología actual de implementación de computadoras, pero no necesariamente con tecnologías anteriores (como la máquina analítica de Babagge), no convencionales (como las computadoras de ADN, computadoras cuánticas), o futuras. El solo hecho de que artefactos tales puedan ser considerados computadoras requiere que cualquier criterio de demarcación no sea dependiente de una clase particular de realizaciones. Por otro lado, el enfoque es poco preciso, dado que clasifica como equivalentes sistemas computacionales que son claramente diferentes desde el punto de vista computacional (por ejemplo, las máquinas tabuladoras de Hollerith y una computadora digital). Este último problema parece salvable solo a partir de una caracterización gradual. Cualquier clasificación binaria tiene el mismo problema. Por otro lado, el enfoque de Piccinini parece unir en una misma caracterización el criterio de demarcación y la demostración de que esos tipos de máquinas satisfacen ese criterio. Mantener separadas ambas cuestiones permite que esa demostración o justificación de que ciertos tipos de máquinas realizan ciertos intérpretes pueda ser construida de manera específica para cada tecnología particular. Esto es necesario, ya que hay maneras muy diferentes de realizar un intérprete (y seguramente se seguirán desarrollando nuevas), pero no por eso el criterio de demarcación cambia.

Si bien el objetivo principal de nuestro concepto de intérprete es caracterizar la noción de computación, tiene ciertas implicaciones en el problema del pancomputacionalismo. En particular, proponemos que un sistema es considerado computacional en cierto grado si puede ser programado. Cuanto más grande el conjunto de comportamientos programables, más computacional es el sistema. Una “computadora” que pueda ser programada solo para un conjunto muy limitado de tareas difícilmente sea considerada un sistema computacional “real”. Tal es el caso, por ejemplo, de un termostato o un regador automático. La máquina de sumar de Pascal puede ser un sistema más interesante, pero aún está muy lejos del poder computacional de una computadora digital. Un intérprete para el cálculo inductivo de construcciones, aunque incompleto (porque solo permite funciones totales) probablemente sea considerado como un sistema de cómputo útil. Así, creemos que el desafío ontológico del pancomputacionalismo se disuelve en la pregunta sobre cómo clasificar sistemas computacionales de acuerdo con su programabilidad.

Podemos considerar la computación física en términos de entrada-salida a partir de la siguiente caracterización de máquina dada por Gilles Dowek (2012):

Giving a meaning to this thesis requires to give a definition of the notion of a machine. A machine is any physical system, equipped with an interaction protocol defining a way to communicate some information to the system by choosing some parameters a = (a1,…,an), when preparing the system, and to extract some information from the system, by measuring some values b = (b1, …, bp).

Such a machine defines a relation: the relation R such that a R b if b is a possible result for the measurements, when the chosen parameters are a. We say that this relation R is realized by this machine.

Nuestra noción de computación es paramétrica respecto de la manera de observar los resultados y al formato de entrada de datos, es decir que un sistema será computacional relativamente a cómo se eligen los parámetros a1, …, an y a cómo se observan los resultados b1, …, bp. Uno de los parámetros particulares será el programa mismo (en algunos casos podrá tener una manera específica de input, en otros será un dato más, indistinguible de los otros).

Podemos aceptar las afirmaciones de Putnam y Searle de que, en algún sentido, cualquier sistema puede ser visto como ejecutando una computación particular, sin acordar con, desde nuestra perspectiva, la obviamente falsa afirmación de que cualquier sistema computa en ese mismo sentido (o dicho de otro modo, que cualquier sistema es un sistema computacional en toda su generalidad). La clave de la trivialización de la noción de computación, consecuencia del pancomputacionalismo de Putnam y Searle, es una libertad ilimitada en la forma de observación. El sentido en que una piedra o una pared computa está dado por el observador. Los estados que describen una computación abstracta pueden ponerse uno a uno con un sistema físico suficientemente complejo. Pero el establecimiento de tal mapping es una tarea computacional que debe ser llevada a cabo, en este caso, por el observador. Pero aun dejando de lado la tarea en sí misma, esta forma de ejercer la libertad de observación choca con la programabilidad del sistema. Cada uno de los comportamientos de un sistema computacional está generado por un programa, una prescripción que lo codifica. Un mapping para cada computación de cada programa cambia las reglas del juego constantemente. Así, se sustituye el proceso generativo que imparte un programa, por un conjunto de observaciones sustancialmente diferentes sobre el sistema. Esto se agrava aun más si consideramos que la presencia de una realización del programa como parte del sistema es lo que distingue un sistema computacional de una simple descripción computacional de un sistema.

En contraste, nuestra propuesta conserva la libertad en las múltiples formas de realización que determinan la relación de implementación, permitiendo comprender los estados de un sistema de cualquier manera. Esto está de acuerdo con la investigación en el desarrollo de nuevo hardware donde se intenta permanentemente explotar nuevas propiedades de los sistemas físicos para mejorar la eficiencia en las implementaciones. Nuestro enfoque acepta la hipotética afirmación de que “todo puede computar”; el desafío es encontrar cómo. Pero la libertad que otorga, de ninguna manera implica la afirmación de que “todo computa”. Para mostrar que un sistema lleva adelante ciertas computaciones es necesario indicar cómo se realiza el programa, cómo se observan los resultados, y más generalmente, cómo los comportamientos se relacionan con los programas, sean cuales sean los aspectos considerados relevantes (i.e. cómo se “obedece” la prescripción). Estas condiciones delimitan el problema del pancomputacionalismo.

Nuestro enfoque tiene algunas conexiones con las propuestas que presentamos previamente. Acordamos con Copeland cuando responde a la pregunta sobre cuándo un “dispositivo computa” postulando que “computar es ejecutar un algoritmo” (un programa en nuestro caso). Un “algoritmo” es un procedimiento mecánico, específico de una “arquitectura”, que utiliza las operaciones primitivas que esta provee. La “arquitectura” es lo que determina la semántica funcional del “algoritmo”, de forma más específica, pero en el mismo espíritu que lo hace nuestra función de interpretación. Pero la relación de modelización entre una “arquitectura” en conjunto con un “algoritmo” y un sistema queda mediada por un esquema de labeling que, aunque en menor grado, introduce la libertad que utilizan Putnam y Searle. Así la solución final de Copeland depende de la noción de modelos “honestos”. Por el contrario, nuestra noción de implementación, aunque otorga libertad en la interpretación de los estados de un sistema físico subyacente, versa sobre todos los posibles programas que el sistema computacional tiene como entrada. Esta universalidad obliga a una correspondencia sistemática que limita drásticamente la libertad en la observación. Respecto del teorema “débil” de Putnam, es decir que para cualquier sistema, dada una manera de observación de los resultados y una codificación particular de los parámetros, no podría distinguirse si está realmente computando o si aleatoriamente está dando esos resultados, es decir que esa salida no está relacionada con la entrada sistemáticamente por un programa. La manera en que afirma esto es diciendo que cualquier sistema con la entrada-salida adecuada implementaría cualquier programa. Lo que Putnam parece olvidar en esa construcción es que el programa mismo es un dato posible. Ahora, si el comportamiento es el esperado para todo programa de entrada (codificado de una manera preestablecida), entonces afirmar que dicho sistema es computacional (si se quiere esta noción se considera relativa al conjunto de comportamientos posibles y concomitantemente al conjunto de codificaciones válidas de los programas) requiere solamente reconocer una propiedad extensional, un comportamiento de entrada-salida que demarca perfectamente cuáles sistemas computan y cuáles no. Como decía Webb refiriéndose a la máquina universal, sería un extrañísimo caso de armonía preestablecida que un sistema cualquiera se comportara como una máquina universal, lo cual es el caso en nuestra caracterización cuando el conjunto de programas aceptables para el sistema es Turing-complete.

En el caso de la propuesta de Piccinini, coincidimos en que los estados computacionales no se individúan semánticamente, y consideramos que su descripción mecanicista de computadoras es correcta y arroja luz sobre la naturaleza computacional de los sistemas. Proponemos que nuestro concepto relacional de intérprete (y las jerarquías que se desprenden) establece un criterio de demarcación más general y bien definido sobre cuán computacional es un sistema. Bajo este marco, se puede interpretar el trabajo de Piccinini como una demostración de que una familia de dispositivos con ciertas arquitecturas satisface este criterio. Los requerimientos que impone sobre las entidades manipuladas por los sistemas computacionales parecen ser condiciones necesarias para la realizabilidad de los intérpretes. Pero como mencionamos más arriba, el enfoque mecanicista de Piccinini parece estar demasiado sesgado por ejemplos particulares de computadoras.

Discusión

En este artículo, nos enfocamos en tres problemas relacionados: qué es computar, cuándo un sistema es computacional, y cuál es la relación entre los aspectos abstractos y concretos de una computación. Los tres problemas están relacionados, y es difícil dar cuenta de uno sin considerar los otros. Pero son problemas diferentes. Ensayamos respuestas que están de acuerdo con las nociones tanto de la teoría de la computación como de la práctica de las ciencias de la computación. Al mismo tiempo, discutimos el problema del pancomputacionalismo, propio del ámbito de la filosofía de la mente. La noción generalizada de intérprete que proponemos permite discutir estos problemas en términos más adecuados.

La principal característica de un intérprete es su habilidad para ser programado para comportarse de diferentes maneras. La variedad de posibles comportamientos que pueden ser codificados determina su nivel de programabilidad. Consideramos que este es un rasgo distintivo para aceptar un sistema como computacional. Así, ser computacional es relativo a un conjunto dado de comportamientos, una forma de codificar tales comportamientos (los programas, o la sintaxis del lenguaje de programación, cuando aplica), y la forma de observar el sistema que determina la relación de implementación. En otras palabras, no tiene sentido usar el verbo “computar” de forma intransitiva. Un sistema puede computar un cierto conjunto de comportamientos vía una codificación y observado en una forma predeterminada. Cuando un intérprete está computando, da lugar a un proceso que produce a partir de una prescripción particular (y como tal, abstracta) un comportamiento particular del sistema (y como tal, concreto). La relación de implementación es la que media entre los aspectos abstractos y concretos, y entendida como una relación entre relaciones, da cierta preeminencia a los aspectos prescriptivos.

Creemos que el concepto de intérprete es central para una filosofía de la computación. Por un lado, los intérpretes son ubicuos en las ciencias de la computación. Por otro lado, su introducción permite iluminar algunos problemas persistentes. Algunas de las ventajas de su uso se resumen a continuación:

  • Algunas cuestiones ontológicas, como qué es un programa, qué es una computación y qué es un sistema computacional, pueden ser planteadas en términos más precisos, admitiendo así respuestas más claras.
  • Se establecen condiciones mínimas para que un sistema sea computacional en cierto grado. Estas condiciones no dependen de la tecnología actual.
  • Las jerarquías que se derivan de la concepción de intérprete pueden ser utilizadas para relacionar y comparar diferentes sistemas. La pregunta acerca de si un sistema es computacional o no puede ser reformulada en una pregunta más general sobre la variedad de comportamientos que produce un sistema y/o su programabilidad.
  • La caracterización de un sistema como computacional difumina la distinción entre software y hardware, uno de los mitos denunciados por Moor (1978), lo cual es coherente con las prácticas de las ciencias de la computación (programar una máquina “virtual” o “real” es transparente para el programador; operaciones de “bajo nivel” pueden estar implementadas en hardware, firmware o directamente software, etc.).
  • La “composición” de intérpretes, compiladores y programas-intérpretes permite caracterizar los diferentes “niveles de abstracción” que se suceden hacia el interior de los sistemas informáticos. El concepto de intérprete es el vínculo entre tales niveles.

Bibliografía

Chalmers, D. J. (1996). “Does a rock implement every finite-state automaton?”. Synthese, 108(3), 309-333.

Copeland, B. J. (1996). “What is computation?”. Synthese, 108(3), 335-359.

Eden, A. H. (2007). “Three paradigms of computer science”. Minds and machines, 17(2), 135-167.

Eden, A. H. y Turner, R. (2007). “Problems in the ontology of computer programs”. Applied Ontology, 2(1), 13-36.

Gandy, R. (1980). “Church’s thesis and principles for mechanisms”. Studies in Logic and the Foundations of Mathematics, 101, 123-148.

Dowek, G. (2012, March). “Around the physical Church-Turing thesis: Cellular automata, formal languages, and the principles of quantum theory”. In International Conference on Language and Automata Theory and Applications (pp. 21-37). Springer Berlin Heidelberg.

Jones, N. D. (1997). Computability and complexity: from a programming perspective (Vol. 21). MIT press.

Davis, M.; Sigal, R. y Weyuker, E. J. (1994). Computability, complexity, and languages: fundamentals of theoretical computer science. Newnes.

Piccinini, G. (2007). “Computing mechanisms”. Philosophy of Science, 74(4), 501-526.

Piccinini, G. (2008). “Computers”. Pacific Philosophical Quarterly, 89, 32–73.

Piccinini, G. (2015). “Computation in Physical Systems”, The Stanford Encyclopedia of Philosophy (Summer 2015 Edition), Edward N. Zalta (ed.), dispoinble en https://goo.gl/hvhEcu.

Putnam, H. (1988). Representation and reality (Vol. 454). Cambridge, MA: MIT press.

Scheutz, M. (1999). “When physical systems realize functions…”. Minds and Machines, 9(2), 161-196.

Searle, J. R. (1990, November). “Is the brain a digital computer?”. In Proceedings and Addresses of the American Philosophical Association (Vol. 64, No. 3, pp. 21-37). American Philosophical Association.

Turing, A. M. (1936). “On computable numbers, with an application to the Entscheidungsproblem”. J. of Math, 58(5), 345-363.

Turner, D. A. (1995). “Elementary strong functional programming”. In Funtional Programming Languages in Education (pp. 1-13). Springer Berlin Heidelberg.



Deja un comentario