Modelos de Computación
Muchos marcos formales definen lo que significa computar, desde la reescritura de funciones del cálculo lambda hasta los circuitos booleanos y los sistemas cuánticos, y la comparación de su potencia revela qué modelos son equivalentes y cuáles difieren genuinamente.
Definition
Un modelo de computación es un marco abstracto preciso que especifica qué operaciones están permitidas y cómo procede una computación; diferentes modelos pueden computar la misma clase de funciones, pero difieren en concisión, paralelismo o los recursos que explicitan.
Scope
Esta área cubre el cálculo lambda y los modelos funcionales, las funciones recursivas y las máquinas de registro, los circuitos booleanos y la complejidad de los circuitos, y la computación cuántica, examinando cómo cada modelo expresa algoritmos, cómo su poder de computabilidad se relaciona a través de la tesis de Church-Turing, y cómo su eficiencia puede divergir.
Sub-topics
Core questions
- ¿Qué diferentes formas existen para formalizar la noción de computación?
- ¿Qué modelos son equivalentes en las funciones que pueden computar, y por qué?
- ¿Cómo difieren los modelos cuando la eficiencia, el paralelismo o la realizabilidad física importan?
- ¿Puede un modelo físicamente motivado, como la computación cuántica, superar la eficiencia clásica?
Key theories
- Equivalencia bajo la tesis de Church-Turing
- El cálculo lambda, las funciones recursivas, las máquinas de registro y las máquinas de Turing computan exactamente la misma clase de funciones, la convergencia que fundamenta la identificación de la computación con la computabilidad de Turing.
- Divergencia en eficiencia
- Los modelos que concuerdan en computabilidad pueden diferir drásticamente en los recursos: los circuitos exponen la computación paralela y no uniforme, y los modelos cuánticos parecen ofrecer aceleraciones, por lo que la elección del modelo importa mucho para la complejidad, incluso cuando no lo hace para la computabilidad.
Clinical relevance
Diferentes modelos iluminan distintos aspectos de la computación real: el cálculo lambda es la base teórica de los lenguajes de programación funcional, los circuitos modelan el hardware y la computación paralela, las máquinas de registro reflejan los procesadores convencionales, y los modelos cuánticos guían el diseño de hardware y algoritmos cuánticos emergentes.
History
En la década de 1930, el cálculo lambda de Church, las funciones recursivas de Gödel y Kleene, y las máquinas de Turing fueron propuestos y luego demostrados como equivalentes. Modelos posteriores añadieron nuevas dimensiones: la complejidad de los circuitos formalizó la computación paralela y de hardware, y la propuesta de Feynman de 1982 de simulación cuántica sembró el modelo cuántico de computación.
Key figures
- Alonzo Church
- Alan Turing
- Stephen Kleene
- Richard Feynman
Related topics
Seminal works
- church1936
- sipser2013
- aroraBarak2009
Frequently asked questions
- ¿Por qué estudiar muchos modelos si computan las mismas funciones?
- La equivalencia solo se aplica a lo que se puede computar en principio. Diferentes modelos facilitan la expresión o el análisis de distintas cosas: el cálculo lambda clarifica la programación funcional, los circuitos revelan el paralelismo y los costos de hardware, y los modelos cuánticos capturan fenómenos físicos, por lo que cada uno es la lente adecuada para diferentes preguntas.
- ¿Son todos los modelos de computación equivalentes?
- Todos los modelos clásicos razonables computan la misma clase de funciones, lo que apoya la tesis de Church-Turing. Pero pueden diferir enormemente en eficiencia, y los modelos que explotan diferentes recursos, como la superposición cuántica, pueden resolver ciertos problemas más rápido, incluso mientras computan las mismas funciones.