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álculo son la resolución de ecuaciones matemáticas y la ejecución de algoritmos informáticos .
Los dispositivos mecánicos o electrónicos (o, históricamente , personas) que realizan cálculos se conocen como computadoras .
La informática es un campo académico que implica el estudio de la computación.
La noción de que los enunciados matemáticos deben estar "bien definidos" ha sido defendida por los matemáticos desde al menos el siglo XVII , [3] pero el acuerdo sobre una definición adecuada resultó difícil de alcanzar. [4] Una definición candidata fue propuesta independientemente por varios matemáticos en la década de 1930. [5] La variante más conocida fue formalizada por el matemático Alan Turing , quien definió un enunciado o cálculo bien definido como cualquier enunciado 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 lambda-definibilidad de Alonzo Church , la recursividad general de Herbrand - Gödel - Kleene y la 1-definibilidad de Emil Post . [5]
Hoy en día, cualquier enunciado o cálculo formal que exhiba esta cualidad de estar bien definido se denomina computable , mientras que el enunciado o cálculo en sí se denomina computación .
La definición de Turing asignó "bien definido" a una clase muy amplia de enunciados matemáticos, incluidos todos los enunciados algebraicos bien formados y todos los enunciados escritos en lenguajes de programación informática modernos. [7]
A pesar de la amplia aceptación de esta definición, hay algunos conceptos matemáticos que no tienen una caracterización bien definida según ella. Entre ellos se incluyen el problema de la detención y el juego del castor atareado . Sigue siendo una pregunta abierta si existe una definición más potente de "bien definido" que sea capaz de capturar tanto las afirmaciones computables como las "no computables". [nota 1] [8]
Algunos ejemplos de enunciados matemáticos que son computables incluyen:
Algunos ejemplos de enunciados matemáticos que no son computables incluyen:
La computación puede considerarse un proceso puramente físico que ocurre dentro de un sistema físico cerrado llamado computadora . La prueba de Turing de 1937, Sobre los números computables, con una aplicación al problema de Entscheidung , demostró que existe una equivalencia formal entre los enunciados computables y los sistemas físicos particulares, comúnmente llamados computadoras . Ejemplos de tales sistemas físicos son: las máquinas de Turing , los matemáticos humanos que siguen reglas estrictas, las computadoras digitales , las computadoras mecánicas , las computadoras analógicas y otros.
En las obras de Hilary Putnam y otros se encuentra una explicación alternativa de la computación . Peter Godfrey-Smith la ha denominado la "explicación de la correlación simple". [9] El resumen de esta explicación que hace Gualtiero Piccinini afirma que se puede decir que un sistema físico realiza una computación específica cuando existe una correlación entre el estado de ese sistema y la computación de tal manera que los "estados microfísicos [del sistema] reflejan las transiciones de estado 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 de computación es que los operandos de la computación representan algo). Esta noción intenta evitar la abstracción lógica de la explicación de la asignación 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 informáticos físicos son tipos de mecanismos que, por diseño, realizan computación física o la manipulación (por un mecanismo funcional) de un vehículo "independiente del medio" de acuerdo con una regla. La "independencia del medio" requiere que la propiedad pueda ser instanciada [ aclaración necesaria ] por múltiples realizadores [ aclaración necesaria ] y múltiples mecanismos, y que las entradas y salidas del mecanismo también sean realizables de forma múltiple . En resumen, la independencia del medio permite el uso de variables físicas con propiedades distintas del 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 . Una regla, en este sentido, proporciona un mapeo entre las entradas, salidas y estados internos del sistema informático físico. [12]
En la teoría de la computación se han desarrollado diversos modelos matemáticos de computación. Los modelos matemáticos típicos de las computadoras son los siguientes:
Giunti llama a los modelos estudiados por la teoría de la computación sistemas computacionales, y sostiene que todos ellos son sistemas matemáticos dinámicos con tiempo discreto y espacio de estados discreto. [13] : cap.1 Sostiene que un sistema computacional es un objeto complejo que consta de tres partes. Primero, un sistema matemático dinámico con tiempo discreto y espacio de estados discreto; segundo, una configuración 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] : pp.179–80
