Modelos de Computação

Muitos arcabouços formais definem o que significa computar, desde a reescrita de funções do cálculo lambda até circuitos booleanos e sistemas quânticos, e a comparação de seu poder revela quais modelos são equivalentes e quais genuinamente diferem.

Definition

Um modelo de computação é um arcabouço abstrato preciso que especifica quais operações são permitidas e como uma computação prossegue; diferentes modelos podem computar a mesma classe de funções, mas diferir em concisão, paralelismo ou nos recursos que explicitam.

Scope

Esta área abrange o cálculo lambda e modelos funcionais, funções recursivas e máquinas de registradores, circuitos booleanos e complexidade de circuitos, e computação quântica, examinando como cada modelo expressa algoritmos, como seu poder de computabilidade se relaciona através da tese de Church-Turing, e como sua eficiência pode divergir.

Sub-topics

• Boolean Circuits and Circuit Complexity
• Lambda Calculus and Functional Models
• Quantum Computation Models
• Recursive Functions and Register Machines

Core questions

• Quais são as diferentes maneiras de formalizar a noção de computação?
• Quais modelos são equivalentes nas funções que podem computar e por quê?
• Como os modelos diferem quando a eficiência, o paralelismo ou a realizabilidade física importam?
• Um modelo fisicamente motivado, como a computação quântica, pode exceder a eficiência clássica?

Key theories

Equivalência sob a tese de Church-Turing

O cálculo lambda, as funções recursivas, as máquinas de registradores e as máquinas de Turing computam exatamente a mesma classe de funções, a convergência que fundamenta a identificação da computação com a computabilidade de Turing.

Divergência na eficiência

Modelos que concordam na computabilidade podem diferir acentuadamente nos recursos: os circuitos expõem a computação paralela e não uniforme, e os modelos quânticos parecem oferecer acelerações, de modo que a escolha do modelo importa muito para a complexidade, mesmo quando não importa para a computabilidade.

Clinical relevance

Diferentes modelos iluminam diferentes aspectos da computação real: o cálculo lambda é a base teórica das linguagens de programação funcionais, os circuitos modelam hardware e computação paralela, as máquinas de registradores espelham processadores convencionais, e os modelos quânticos guiam o design de hardware e algoritmos quânticos emergentes.

History

Na década de 1930, o cálculo lambda de Church, as funções recursivas de Gödel e Kleene, e as máquinas de Turing foram propostos e, em seguida, demonstrados como equivalentes. Modelos posteriores adicionaram novas dimensões: a complexidade de circuitos formalizou a computação paralela e de hardware, e a proposta de Feynman em 1982 de simulação quântica semeou o modelo de computação quântica.

Key figures

• Alonzo Church
• Alan Turing
• Stephen Kleene
• Richard Feynman

Seminal works

• church1936
• sipser2013
• aroraBarak2009

Frequently asked questions

Por que estudar muitos modelos se eles computam as mesmas funções?

A equivalência se mantém apenas para o que pode ser computado em princípio. Diferentes modelos tornam diferentes coisas fáceis de expressar ou analisar: o cálculo lambda esclarece a programação funcional, os circuitos revelam o paralelismo e os custos de hardware, e os modelos quânticos capturam fenômenos físicos, então cada um é a lente certa para diferentes questões.

Todos os modelos de computação são equivalentes?

Todos os modelos clássicos razoáveis computam a mesma classe de funções, apoiando a tese de Church-Turing. Mas eles podem diferir muito em eficiência, e modelos que exploram diferentes recursos, como a superposição quântica, podem resolver certos problemas mais rapidamente, mesmo enquanto computam as mesmas funções.