Por que podemos assumir que um algoritmo pode ser representado como uma sequência de bits?

Estou começando a ler um livro sobre Complexidade Computacional e Máquinas de Turing. Aqui está citação:

Um algoritmo (ou seja, uma máquina) pode ser representado como uma sequência de bits, uma vez que decidimos alguma codificação canônica.

Essa afirmação é fornecida como um fato simples, mas não consigo entender.

Por exemplo, se eu tiver um algoritmo que aceite como entrada e calcule ( x + 1 ) 2 ou:$x$$(x+1)^2$

int function (int x){
   x = x + 1; 
   return x**2; 
}

Como isso pode ser representado como string usando o alfabeto ?$\{0, 1\}^*$

A resposta mais ingênua e simples para sua pergunta é que o código fornecido (e o código de máquina compilado) são de fato representados como sequências sintáticas de {0,1} *. Além disso, como você está falando de máquinas de turing, os programas executados são uma lista linear de operações / instruções, não há razão para que elas não possam ser representadas como bits / bytes.

Você já tem uma representação dessa função como texto. Converta cada caractere em um valor de um byte usando a codificação ASCII. Então o resultado é uma sequência de bytes, ou seja, uma sequência de bits, ou seja, uma string sobre o alfabeto . Esse é um exemplo de codificação.$\{0,1\}^*$

Não consigo resistir ...

⡂⡀⣀⢀⣄⡀⣰⡉⡀⠀⡀⡀⣀⠀⢀⣀⢀⣄⡀⡂⢀⣀⡀⢀⢀⡀⠀⡰⣀⠀⣀⠀⡂⡀⣀⢀⣄⡰⡀⢠⠂
⡇⡏⠀⡇⡇⠀⢸⠀⡇⢀⡇⡏⠀⡇⣏⠀⠀⡇⠀⡇⣏⠀⣹⢸⠁⢸⠀⡇⢈⠷⡁⠀⡇⡏⠀⡇⡇⠀⡇⢼⠀
⠁⠁⠀⠁⠈⠁⠈⠀⠈⠁⠁⠁⠀⠁⠈⠉⠀⠈⠁⠁⠈⠉⠁⠈⠀⠈⠀⠱⠉⠀⠉⠀⠁⠁⠀⠁⠈⠱⠁⠘⠄
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⢤⡀⡤⠀⣀⣀⣀⠀⢤⡀⡤⠀⠀⢰⠀⠀⢹⠠⠀
⠀⠀⠀⣠⠛⣄⠀⠒⠒⠒⠀⣠⠛⣄⠀⠉⢹⠉⠁⢸⢀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠀
⠀⠀⠀⣄⢄⠤⢄⢴⠤⢠⠀⢠⢠⡠⢠⡠⢄⠀⢤⡀⡤⢺⡖⠐⣷⠂⠊⢉⡆
⠀⠀⠀⡇⠸⣍⣉⠸⣀⠸⣀⢼⢸⠀⢸⠀⢸⠀⣠⠛⣄⠀⠀⠀⠀⠀⣴⣋⡀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

⢱⠀
⢸⠁
⠊

(Os pontos acima representam uns, os espaços em branco são zerados).

Seu computador armazena tudo como seqüências de 0e 1, incluindo a pergunta que você digitou para perguntar como é feita. Por exemplo, cada letra e símbolo é representado por 8 bits (estou falando sobre como as coisas costumavam ser, hoje em dia são 16 bits e mais complicado). Você pode vê- los aqui . Bem, eles não estão mostrando os bits, mas os códigos hexadecimal e octal. Você sabe como converter um número em sua representação digital?

A hipótese fundamental por trás desse conceito é a tese de Church-Turing . Pode ser difícil perceber que qualquer algoritmo pode ser representado como uma sequência de bits, porque o termo "algoritmo" pode ser pensado em termos muito informais. Na tese de Church-Turing, eles usam um conceito muito rigorosamente definido sobre o que é um algoritmo (e mesmo assim houve algumas perguntas sobre palavras). No entanto, sua terminologia tem obtido tanto influência que às vezes é argumentado que essas definições para palavras como "algoritmo" são tão eficazes que nós simplesmente aceitá-los como a definição.

Church-Turing afirma que todo algoritmo pode ser implementado como um cálculo em uma máquina de Turing. Dado que a descrição de uma Máquina de Turing é um conjunto finito de valores, é trivial ver como mapear essa descrição em uma sequência de números e, em seguida, em uma sequência de 0 e 1s.

Como as outras respostas mencionaram, é trivial representar seu exemplo de algoritmo usando codificação ASCII ou outras codificações.

Penso que a razão pela qual seu livro apresenta essa afirmação como fato deriva do fato de que muitos simplesmente usam a tese de Church-Turing como base para a definição de um algoritmo. Se você usar essa definição, é um fato tão óbvio quanto "5 é um número" porque você basicamente a definiu como tal.

Esta afirmação é baseada na existência de TMs universais . São basicamente TMs programáveis ​​que podem simular qualquer outra TM com no máximo sobrecarga de poli. Portanto, seu programa é simplesmente parte da entrada codificada como zeros e uns.

Bem, vamos falar sobre algoritmos que não podem ser representados como uma cadeia de bits finita para qualquer tipo de codificação.

Deixe-me digitar esse algoritmo para você ... Ah, mas se eu fizer isso, posso representar esse algoritmo com a codificação do meu texto digitado.

Que tal representar meu algoritmo usando alguns "meios analógicos", digamos pela posição de algumas moedas na minha mesa. Embora a posição dessas moedas possa ser modelada por alguns números reais (que em alguns codificações pode ser impossível de representar finitamente), toda essa descrição pode ser novamente considerada uma representação do meu algoritmo e pode ser codificada em uma cadeia de bits novamente!

Espero que esses exemplos deixem claro que, se algum algoritmo não puder ser representado por uma cadeia de bits finita, não teremos meios de descrever esse algoritmo!

Então, por que consideraríamos a existência de algo que não podemos falar? Talvez interessante para a filosofia, mas não para a ciência. Assim, definimos a noção de algoritmo forma que ela possa ser representada por uma cadeia de bits, pois pelo menos sabemos que somos capazes de falar sobre todos os algoritmos.

Embora a resposta acima responda à pergunta, acho que a confusão sobre o exemplo dado se deve principalmente ao fato de uma representação precisar apenas representar exclusivamente algum algoritmo. A maneira de representação não precisa envolver os cálculos reais invocados pelo algoritmo! Isso é muito útil, pois significa que também podemos representar algoritmos incontestáveis !

Outra maneira de ver isso é através da teoria da informação. Todas as codificações de informações / perguntas significativas / úteis podem ser transformadas em 'sequências' binárias.

Grande parte do campo vai para a pergunta "qual é a maneira de fazer o menor número médio de perguntas para comunicar uma informação significativa?" Na prática, é o mesmo que "qual é a abordagem ideal para fazer o menor número de perguntas de sim / não para entender o que foi comunicado ou dito?"