Un cálculo es cualquier tipo de cálculo aritmético o no aritmético que esté bien definido. [1] [2] Ejemplos comunes de cálculos son las ecuaciones matemáticas y los algoritmos informáticos .
Los dispositivos mecánicos o electrónicos (o, históricamente , personas) que realizan cálculos se conocen como computadoras . El estudio de la computación es el campo de la computabilidad , en sí mismo un subcampo de la informática .
La noción de que los enunciados matemáticos deberían estar "bien definidos" había sido defendida por los matemáticos desde al menos el siglo XVII , [3] pero no se logró llegar a un acuerdo sobre una definición adecuada. [4] Varios matemáticos propusieron de forma independiente una definición candidata en la década de 1930. [5] La variante más conocida fue formalizada por el matemático Alan Turing , quien definió una declaración o cálculo bien definido como cualquier declaración que pudiera expresarse en términos de los parámetros de inicialización de una máquina de Turing . [6] Otras definiciones (matemáticamente equivalentes) incluyen la definibilidad lambda de Alonzo Church , la recursividad general de Herbrand - Gödel - Kleene y la definibilidad 1 de Emil Post . [5]
Hoy en día, cualquier declaración o cálculo formal que exhiba esta cualidad de bien definida se denomina computable , mientras que la declaración o cálculo en sí se denomina cálculo .
La definición de Turing distribuyó "bien definido" a una clase muy grande de enunciados matemáticos, incluidos todos los enunciados algebraicos bien formados y todos los enunciados escritos en lenguajes de programación de computadoras modernos. [7]
A pesar de la aceptación generalizada de esta definición, existen algunos conceptos matemáticos que no tienen una caracterización bien definida según esta definición. Esto incluye el problema de detenerse y el juego del castor ocupado . Sigue siendo una cuestión abierta si existe una definición más poderosa de "bien definido" que sea capaz de capturar declaraciones tanto computables como "no computables". [nota 1] [8]
Algunos ejemplos de enunciados matemáticos que son computables incluyen:
Algunos ejemplos de declaraciones matemáticas que no son computables incluyen:
La computación puede verse como un proceso puramente físico que ocurre dentro de un sistema físico cerrado llamado computadora . La prueba de Turing de 1937, Sobre números computables, con una aplicación al Entscheidungsproblem , demostró que existe una equivalencia formal entre enunciados computables y sistemas físicos particulares, comúnmente llamados computadoras . Ejemplos de tales sistemas físicos son: máquinas de Turing , matemáticos humanos que siguen reglas estrictas, computadoras digitales , computadoras mecánicas , computadoras analógicas y otros.
Una explicación alternativa de la computación se encuentra en las obras de Hilary Putnam y otros. Peter Godfrey-Smith lo ha denominado el "relato cartográfico simple". [9] El resumen de Gualtiero Piccinini de este relato establece que se puede decir que un sistema físico realiza un cálculo específico cuando existe una correlación entre el estado de ese sistema y el cálculo tal que los "estados microfísicos [del sistema] reflejan el estado transiciones entre los estados computacionales." [10]
Filósofos como Jerry Fodor [11] han sugerido varias explicaciones de la computación con la restricción de que el contenido semántico sea una condición necesaria para la computación (es decir, lo que diferencia un sistema físico arbitrario de un sistema informático es que los operandos del cálculo representan algo). . Esta noción intenta impedir la abstracción lógica de la explicación cartográfica del pancomputacionalismo , la idea de que se puede decir que todo está computando todo.
Gualtiero Piccinini propone una explicación de la computación basada en la filosofía mecánica . Afirma que los sistemas de computación física son tipos de mecanismos que, por diseño, realizan computación física o la manipulación (mediante un mecanismo funcional) de un vehículo "independiente del medio" de acuerdo con una regla. La "independencia media" requiere que la propiedad pueda ser instanciada [ se necesita aclaración ] por múltiples realizadores [ se necesita aclaración ] y múltiples mecanismos, y que las entradas y salidas del mecanismo también sean realizables de forma múltiple . En resumen, la independencia media permite el uso de variables físicas con propiedades distintas al voltaje (como en las computadoras digitales típicas); Esto es imperativo al considerar otros tipos de computación, como la que ocurre en el cerebro o en una computadora cuántica . En este sentido, una regla proporciona un mapeo entre entradas, salidas y estados internos del sistema informático físico. [12]
En la teoría de la computación se ha desarrollado una diversidad de modelos matemáticos de computación. Los modelos matemáticos típicos de las computadoras son los siguientes:
Giunti llama sistemas computacionales a los modelos estudiados por la teoría de la computación , y sostiene que todos ellos son sistemas dinámicos matemáticos con tiempo discreto y espacio de estados discretos. [13] : cap.1 Sostiene que un sistema computacional es un objeto complejo que consta de tres partes. Primero, un sistema dinámico matemático con tiempo discreto y espacio de estados discretos; segundo, un montaje computacional , que se compone de una parte teórica , y una parte real ; tercero, una interpretación que vincula el sistema dinámico con la configuración . [14] : págs. 179–80
