Cardinalidade do conjunto de algoritmos

15

Alguém em uma discussão levantou que (ele acha) que pode haver pelo menos um número contínuo de estratégias para abordar um problema específico. O problema específico era estratégias de negociação (não algoritmos, mas estratégias), mas acho que isso não vem ao caso da minha pergunta.

Isso me fez pensar sobre a cardinalidade do conjunto de algoritmos. Tenho pesquisado um pouco, mas não consegui nada. Eu estive pensando que, como as máquinas de turing operam com um conjunto finito de alfabeto e a fita precisa ser indexável, portanto contável, é impossível ter um número incontável de algoritmos. Minha teoria dos conjuntos é reconhecidamente enferrujada, então não tenho certeza de que meu raciocínio seja válido e provavelmente não seria capaz de provar isso, mas é um pensamento interessante.

Qual é a cardinalidade do conjunto de algoritmos?

qwe2
fonte
11
Como Yuval Filmus mencionou, existem inúmeras máquinas de Turing. Mas existem muitas famílias não uniformes de circuitos booleanos, pois eles podem calcular qualquer função com valor booleano. Mas isso provavelmente não é o que você quis dizer com "algoritmo".
Reinstale Monica

Respostas:

28

Um algoritmo é informalmente descrito como uma sequência finita de instruções escritas para realizar alguma tarefa. Mais formalmente, eles são identificados como máquinas de Turing, embora você possa igualmente descrevê-los como programas de computador.

O formalismo preciso que você usa não importa muito, mas o ponto fundamental é que cada algoritmo pode ser escrito como uma sequência finita de caracteres, onde os caracteres são escolhidos entre alguns conjuntos finitos, por exemplo, letras romanas, ASCII ou zeros e uns. Para simplificar, vamos assumir zeros e uns. Qualquer sequência de zeros e uns é apenas um número natural escrito em binário. Isso significa que há no máximo uma infinidade contável de algoritmos, já que todo algoritmo pode ser representado como um número natural.

Para crédito total, você deve estar preocupado com o fato de alguns números naturais não codificarem programas válidos; portanto, pode haver menos algoritmos do que números naturais. (Para crédito de bônus, você pode também estar se perguntando se é possível que dois números naturais diferentes representam o mesmo algoritmo.) No entanto, print 1, print 2,print 3 e assim por diante são todos os algoritmos e todos diferentes, então há pelo menos countably infinitamente muitos algoritmos.

Portanto, concluímos que o conjunto de algoritmos é infinitamente contável.

David Richerby
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Gilles 'SO- stop be evil'
10

O conjunto de algoritmos é infinitamente contável. Isso ocorre porque cada algoritmo tem uma descrição finita, digamos, como uma máquina de Turing.

O fato de um algoritmo ter uma descrição finita nos permite inserir um algoritmo em outro, e essa é a base da teoria da computabilidade. Isso nos permite formular o problema da parada, por exemplo.

Yuval Filmus
fonte
7

pelo menos número contínuo de estratégias para abordar um problema específico

Provavelmente, "Continuum" significa os números reais ... usar "pelo menos" junto com essa palavra é absurdamente exagerado. Para ser um pouco irônico: o número infinito é bastante grande, mas o número infinito é ... maior que o grande. Muito mais. Insondável.

Então vamos jogar isso pela janela. Para ver com que tipo de infinito estamos lidando, é absolutamente simples (e intuitivo, mesmo que seu amigo nunca tenha ouvido falar em ciência da computação teórica):

  • Qualquer algoritmo pode ser implementado com qualquer linguagem completa; escolha seu veneno favorito das linguagens do mundo real (Java, C, ...) para desmistificar um pouco isso. Tudo isso é equivalente ao conjunto teórico de algoritmos que qualquer um poderia inventar. Observe que todo algoritmo é finito em si, ou seja, não há algoritmos que precisariam de muitos símbolos para escrever.
  • Não pense em máquinas de Turing complicadas. Seu idioma preferido usa arquivos simples para armazenar seu código-fonte. Todo arquivo é uma coleção de pequenos números (também conhecidos como bytes). O importante é que esses números são definitivamente mais inteiros, não contínuos. (Se você é purista e deseja permanecer no regime teórico, substitua a palavra "byte" por "symbol", isso não muda nada.) Se você tem medo de grandes programas distribuídos por vários arquivos (e bibliotecas) e outras coisas) e depois compactá-las em um único arquivo compactado (ou seja, um único arquivo).
  • Agora, você pode atribuir um único número inteiro a todos os arquivos existentes, de forma bijetiva. Simplesmente escrevemos toda a bagunça de bits / bytes do arquivo, um após o outro, e terminamos com um número muito grande expresso em binário. No passado distante, as pessoas realmente faziam isso: imprimiam programas binários compilados como longas listas de números hexadecimais em revistas; você os digitaria, mas nunca os veria como números (geralmente agrupados em conjuntos de 8 ou 16 dígitos para facilitar a digitação).
  • Portanto: todo programa pode ser representado por um número inteiro, embora um número arbitrariamente grande. O contrário também funciona - todo número inteiro pode ser imediata e trivialmente transferido para um arquivo e lançado em um compilador (obviamente, apenas uma pequena parte deles será um programa válido, mas isso não importa para nós agora).
  • No final, programas e, portanto, algoritmos, são um subconjunto dos números inteiros; portanto, apenas muitos podem existir.
  • NB, o fato de haver muitas implementações diferentes de um único algoritmo é a nosso favor, ou seja, muitos desses números inteiros se condensam em (diferentes representações) no mesmo algoritmo. Portanto, se o infinito contável já não fosse o menor tipo de infinito, teríamos que nos preocupar com o número de algoritmos sendo ainda menores, mas certamente não maiores (isto é, incontáveis).

O problema específico era estratégias de negociação (não algoritmos, mas estratégias)

Não sei o que seu amigo quer dizer com "estratégia"; Eu suponho que ele quis dizer algo que é como um algoritmo, mas não completamente formulado com detalhes suficientes para invadir um computador? Ou que de alguma forma depende da "intuição" humana durante a execução? Nesse caso, esses são apenas detalhes irrelevantes. A humanidade ainda não encontrou nenhum tipo de descrição de processos que seja mais poderoso ou maior que os "algoritmos" no sentido que usamos no CS.

AnoE
fonte
3
Re: "'Continuum' provavelmente deve significar os números reais ... usar 'pelo menos' junto com essa palavra é absurdamente exagerado": Não há nada "exagerado" sobre isso, muito menos "absurdamente". . Existem mais conjuntos de números reais do que números reais; portanto, é normal falar sobre conjuntos maiores que o continuum.
Ruakh 28/08/19
6

Veja Gödel Numbering , é um fato básico na ciência da computação que os algoritmos são contáveis, assim como os conjuntos por extensão recursivamente enumeráveis.

Como os algoritmos são contáveis, é fácil mostrar que não existe um algoritmo para verificar todos os conjuntos em um sistema formal (atribua um valor verdadeiro a um problema). Isso seria equivalente a atribuir um algoritmo a todas as funções que mapeiam o conjunto de problemas para valores booleanos. O conjunto dessas funções é no entanto incontável (trivialmente da mesma cardinalidade que o conjunto de potências do conjunto de problemas, portanto incontável).

Espero que isso dê alguma intuição sobre por que os algoritmos precisam ser "menos poderosos" do que qualquer outra função, portanto contáveis ​​(vamos ignorar a hipótese do continuum aqui).

drilow
fonte
2

Se não se começar com o requisito de que uma estratégia precisa ser implementável com um algoritmo e ignorar os efeitos da discretização da vida real, pode-se, por exemplo, aceitar o seguinte como estratégia de negociação parametrizada:

abab

ab

Arno
fonte
0

Se concebermos algoritmos como programas de computador escritos em binário *, então o número de algoritmos é o número de números binários (inteiros). Assim, a cardinalidade dos algoritmos é a cardinalidade dos números inteiros.

* Uma prova de que as máquinas de turing podem executar todos os algoritmos e que os computadores podem executar qualquer máquina de turing de programa tornaria essa resposta desnecessariamente longa. O primeiro pode depender da definição de um algoritmo, mas não acho que você esteja usando estratégias de negociação incontestáveis.

user558317
fonte
11
O que isso acrescenta às respostas existentes?
David Richerby
"Uma prova de que as máquinas de turing podem executar todos os algoritmos ... tornaria essa resposta desnecessariamente longa". Ele faria a resposta impossível, desde que você não pode realmente provar a tese de Church-Turing
John Coleman
@DavidRicherby Acrescenta brevidade.
user558317
11
@JohnColeman Afirmando a impossibilidade de uma prova, sem uma prova? Eu quis dizer que a) o OP provavelmente não se importaria, pois b) é uma questão de definição. A pergunta parece conter a suposição: "como as máquinas de turing operam com um conjunto finito de alfabeto e a fita precisa ser indexável, portanto contável, é impossível ter um número incontável de algoritmos".
user558317
0

As outras respostas já explicaram que no modelo padrão de computação (máquinas de Turing, cálculo lambda, etc.) o conjunto de algoritmos é consideravelmente infinito.

No entanto, existem outros modelos teóricos de computação nos quais o conjunto de algoritmos é incontávelmente infinito. Por exemplo, as máquinas Blum-Shub-Smale têm um conjunto de instruções incontável e infinito 1 ; portanto, seu conjunto de algoritmos também é incontávelmente infinito.


1 Para ser preciso, o próprio conjunto de instruções é finito, mas é parametrizado usando um conjunto incontávelmente infinito (as funções racionais).

Florian Brucker
fonte
As funções racionais não são contáveis?
Ben Millwood
@BenMillwood Você pode esboçar brevemente uma prova de por que esse pode ser o caso?
C #
x0Rf:xx0
Ah, eu estava assumindo que as constantes também tinham que ser racionais. Deixa pra lá então.
Ben Millwood 5/09
-1

uma vez que as máquinas de turing operam com um conjunto finito de alfabeto e a fita deve ser indexável, portanto, contável

Dado um tamanho específico, existem finitas máquinas de Turing e muitos tamanhos. Um conjunto contável de números, desde que finitos, é contável. O tamanho do alfabeto é um fator no número de máquinas de Turing, mas o tamanho da fita não é. Se fosse permitido que o alfabeto contasse muitos caracteres, haveria inúmeras máquinas (cada número real poderia ser codificado como uma sequência de símbolos).

.5.5

Acumulação
fonte
n
E o que significaria ter incontáveis ​​muitos algoritmos, afinal? Você só pode escrever muitos. Em que sentido é algo que você não pode escrever um algoritmo?
David Richerby
@DavidRicherby Sim, eu misturei algumas coisas. Mas pode-se usar "algoritmo" em um sentido geral para se referir a uma sequência de escolhas. E, nesse sentido, escolher um dígito com base na entrada é um "algoritmo", embora não seja computável.
Acumulação
Na ciência da computação, "algoritmo" e "computável" são a mesma coisa. Um algoritmo é uma máquina de Turing.
David Richerby