O que exatamente é computação?

Eu sei o que a computação é em algum sentido vago (é o que os computadores fazem), mas eu gostaria de uma definição mais rigorosa.

Dictionary.comAs definições de computação, computação, cálculo e computação são circulares, portanto, não ajuda.

Wikipediadefine computação como "qualquer tipo de cálculo que siga um modelo bem definido". Ele define cálculo como "o processo deliberado que transforma uma ou mais entradas em um ou mais resultados, com alteração variável". Mas parece que essa definição inclui muitas ações como cálculos, mesmo que não sejam tipicamente consideradas cálculos.

Por exemplo, isso não implicaria que, digamos, uma explosão de bomba seja um cálculo, com a entrada sendo o fusível aceso e a saída sendo a explosão?

Então, o que exatamente é computação?

Talvez o problema aqui seja procurar uma definição altamente específica de um conceito muito geral. Não vejo o problema de ver praticamente tudo como um cálculo. Embora não pensemos nisso, tudo o que fazemos é expressável em termos da física das partes componentes, até pelo menos quarks zumbindo. Temos a mesma situação com o cálculo. Existem entradas, saídas e um processo (todos os quais podem ser triviais). Se eles são interessantes ou úteis como cálculos ou modelos de cálculo, é uma questão muito diferente.

A definição de trabalho mais forte que temos vem da (forte) Tese de Church-Turing, que afirma que todo modelo de computação fisicamente realizável possível não é mais poderoso do que uma Máquina de Turing. Se você acredita que isso é verdade, embora possamos ter muitas maneiras de expressar as coisas, finalmente podemos reduzir todos os cálculos a uma Máquina de Turing, fornecendo uma definição de computação como "qualquer coisa que possamos reduzir a uma Máquina de Turing".

Neste modelo, a bomba explosiva é uma computação. Não é amplamente aplicável (esperamos;)), mas podemos modelar de alguma maneira com uma Máquina de Turing (embora exista um argumento aqui sobre a natureza da saída e a equivalência com a saída da TM). Também não é um bom modelo de computação em geral, na medida em que parece improvável que o modelo de bomba em explosão seja Turing completo.

Essa é a pergunta que Turing se propôs a resolver em seu famoso artigo de 1936, On numbers computable, com uma aplicação no Entscheidungsproblem , um trabalho no qual ele apresenta (o que ficou conhecido como) o modelo de máquina de Turing. Veja em particular a Seção 9.

O trabalho de Turing está no contexto de números computáveis . Existem outras noções de computação apropriadas para computar outros tipos de estruturas, e seu estudo faz parte da teoria da computação (também conhecida como teoria da recursão).

A principal diferença entre a noção comum de computação e o seu exemplo (uma bomba explosiva) é o que está sendo computado. O que está sendo computado por sua bomba explodindo? Outra diferença são os meios computacionais, mas pode-se imaginar uma engenhoca mecânica que usa bombas para calcular algo mais legítimo.

Outro ponto é se as noções clássicas de computação se aplicam ao que hoje percebemos como computação - ou seja, a interação bidirecional entre o computador e o usuário. Essa é uma crítica comum feita contra o noção clássica de computabilidade, embora a interação possa ser modelada usando as ferramentas da teoria da computação (não é apenas o que você aprende em sala de aula).

$A$$B$$x\in A$$y\in B$$x\in A$$x$

$x$$x$$y$$x$$y$

$t=0$$t=1$

Conclusão: qualquer mapeamento define uma computação. Qualquer "dispositivo" que transforma uma entrada na saída correspondente, executa ("calcula") essa computação específica.

⁽¹⁾ podemos estender a discussão para esses tipos de cálculos, o que fará sentido quando você pensar em funções que não são recursivas, mas eu prefiro não ir lá.

Não tentarei definir o que é uma computação, que foi bem feita por Luke Mathieson e Yuval Filmus.

No entanto, pensar em um dispositivo explosivo como uma computação me leva a uma questão secundária importante: se a explosão é uma computação, então o que ela calcula? Diferente de uma representação do dispositivo depois que ele explodiu.

O que pretendo é que possamos definir com bastante precisão o que consideramos uma computação e até o que pode ser visto (inventado?) Como um. Podemos descrever uma computação. Mas podemos dizer o que é computação?

A computação, como geralmente definida, é um jogo puramente sintático. É um jogo de estruturas físicas que estão sendo transformadas de acordo com regras precisas. Como nossa única ferramenta (até transformações padrão) para representar estruturas físicas é, em última análise, a sequência de símbolos, a computação acaba sendo definida como algum tipo de transformação formal em sequências de símbolos. Isso vale para máquinas de Turing, cálculo lambda, funções recursivas parciais e outros modelos menos populares. A palavra cálculo (como em lambda-calculus) na verdade reflete essa visão, pois, em latim, os cálculos são pequenas pedras usadas para representação.

Mas o que isso não diz é qual significado deve ser atribuído a essa sintaxe, o que ela representa. Aqui está o pouco que eu acho que entendo, pois não sou especialista em tais questões (então verifique-me). O problema é coberto pela teoria dos modelos .

Dado um sistema formal de representações, possivelmente associado a uma lógica (regras de axiomas e inferência) ou a um sistema de computação (regras de transformação), um modelo da teoria formal é uma estrutura matemática com componentes que seguem essas regras.

O mesmo cálculo, ou mais precisamente a mesma descrição de um cálculo, pode realmente ter muitos modelos correspondentes a entidades muito diferentes.

Por exemplo, um algoritmo GCD descreve uma computação. Mas pode ser interpretado em números naturais ou em polinômios.

Isso lembra a citação de Bertrand Russell :

A matemática pode ser definida como o assunto em que nunca sabemos do que estamos falando, nem se o que estamos dizendo é verdadeiro.

A situação é praticamente a mesma para computação. É um jogo formal, onde os movimentos podem ser entendidos de muitas maneiras diferentes. Mas, na verdade, existem laços profundos entre a matemática formalmente definida por sistemas axiomáticos e a teoria da computação.

A computação, a algorítmica, foi definida para resolver problemas matemáticos, e muitos dos conceitos modernos foram pensados ​​por lógicos que tentavam entender os mecanismos que nos permitem provar teoremas, partindo de axiomas e aplicando regras de inferência.

Portanto, voltando ao dispositivo de explosão, certamente pode ser interpretado como uma manipulação de uma representação, isto é, como um cálculo. Mas geralmente é muito difícil associar a ele qualquer outro significado que não seja ele próprio.

No entanto, isso nem sempre é verdade ou não era. O princípio da computação analógica baseia-se na idéia de que diferentes sistemas de representação podem ser usados ​​para cálculos relacionados de alguma maneira precisa. Em seguida, podemos calcular com um sistema para ter uma idéia do que o outro sistema (muito pesado para realmente usar, por exemplo, um universo :) calcularia na configuração correspondente.

Eu gosto de responder a esse tipo de perguntas sobre terminologia em termos etimológicos.

Portanto, o cálculo vem da palavra latina compŭtus, que literalmente significa "cálculo".

Em idiomas latinos, como francês, italiano, espanhol ou português (entre outros), essa etimologia é compartilhada com "conto" (uma história) em francês compte / conte em espanhol cuenta / cuento em português conta / conto etc ...

Portanto, calcular é calcular e contar como esse cálculo foi feito.

Portanto, eu diria que a computação é o processo de usar regras matemáticas e lógicas para processar uma determinada informação, de modo que novas informações significativas sejam deduzidas dos dados originais, acompanhando como essas novas informações foram geradas (processador, memória, entrada e saída são os fundamentos envolvidos)