Problemas de computação infinitamente grandes, mas localmente finitos

14

Essa pergunta é inspirada em um comentário que Jukka Suomela fez em outra pergunta .

Quais são exemplos de problemas (e algoritmos) de computação infinitamente grandes, mas localmente finitos?

Em outras palavras, quais são os exemplos de cálculos que são interrompidos em tempo finito, nos quais cada Máquina de Turing lê e processa apenas dados finitos, mas, no conjunto, a computação resolve um problema de tamanho infinito se houver infinitas máquinas de Turing conectadas em rede?

Aaron Sterling
fonte
Eu ia comentar que essa ideia parece a mesma de uma única MT com infinitas fitas, que eu pensava ter visto antes, mas agora não consigo encontrar uma referência. Estou sonhando ou isso é uma ideia explorada? Certamente outras extensões de hipercomputação, como TMs de tempo infinito, foram estudadas. A idéia de "rede" da TM adiciona algo a este modelo?
Huck Bennett
@ HuckBennett: Eu não sei; pode ser o mesmo. Percebi no comentário original de Jukka que ele estava pensando em problemas como o Graph Coloring em um gráfico infinito de graus delimitados (embora eu não saiba se esse problema em particular seria uma resposta a essa pergunta). Cada TM executaria o mesmo algoritmo e conversaria com um conjunto finito de vizinhos. Parece que uma TM com infinitas fitas pode ser capaz de simular um gráfico com infinitas arestas entre dois nós, o que é diferente em princípio do que tenho em mente. Mas eu sei muito pouco sobre esses modelos.
Aaron Sterling:

Respostas:

13

Apenas para dar algumas idéias do que é possível (mas de certa forma não trivial), aqui está um exemplo: um algoritmo distribuído que encontra uma borda máxima compactada em um gráfico de graus limitados.

Definição de problema

Dado um gráfico simples e não direcionado , um empacotamento de aresta (ou correspondência fracionária) associa um peso w ( e ) a cada aresta e E, de modo que, para cada nó v V , o peso total de arestas incidentes para v é no máximo 1 . Um nó está saturado se o peso total das bordas do incidente for igual a 1 . Uma gaxeta de aresta é máxima se todas as arestas tiverem pelo menos um ponto final saturado (ou seja, nenhum dos pesos pode ser estendido com avidez).G=(V,E)W(e)eEvVv11

Observe-se que um máximo correspondentes define uma embalagem borda mima (conjunto w ( e ) = 1 sse e H ); portanto, é fácil resolver em um cenário centralizado clássico (assumindo que G é finito).MEW(e)=1eMG

As gaxetas de borda realmente têm algumas aplicações, pelo menos se uma define uma aplicação no sentido comum do TCS: o conjunto de nós saturados forma uma aproximação de uma cobertura mínima de vértice (é claro que isso só faz sentido no caso de um G finito ) .2G

Modelo de computação

Vamos assumir que existe uma constante global tal que o grau de qualquer v V seja no máximo Δ .ΔvVΔ

Para manter isso o mais próximo possível do espírito da pergunta original, vamos definir o modelo de computação da seguinte forma. Assumimos que cada nó é uma máquina de Turing e uma borda { u , v } E é um canal de comunicação entre u e v . A fita de entrada de v codifica o grau deg ( v ) de v . Para cada v V , as arestas incidentes em v são rotuladas (em uma ordem arbitrária) com números inteiros 1 , 2 , vV{você,v}Evocêvvdeg(v)vvVv ; esses são chamados derótulos de borda locais(o rótulo de { u , v } E pode ser diferente para u e v ). A máquina possui instruções com as quais pode enviar e receber mensagens através de cada uma dessas bordas; uma máquina pode endereçar seus vizinhos usando as etiquetas de borda locais.1,2,...,deg(v){você,v}Evocêv

Exigimos que as máquinas de calcular uma margem válida embalagem para G . Mais precisamente, cada v V deve imprimir em sua fita de saída uma codificação de w ( e ) para cada borda e incidente em v , ordenada pelas etiquetas da borda local e depois parar.WGvVW(e)ev

Dizemos que um algoritmo distribuído encontra um empacotamento máximo de arestas no tempo T , se o seguinte for válido para qualquer gráfico G de grau máximo Δ e para qualquer rotulagem local de arestas de G : se substituirmos cada nó de G por uma cópia idêntica de a máquina de Turing A e inicie as máquinas, depois de T etapas todas as máquinas imprimiram uma solução válida (consistente globalmente) e pararam.UMATGΔGGUMAT

Infinities

Agora, todas as opções acima fazem todo sentido, mesmo que o conjunto de nós seja infinitamente contável.V

A formulação do problema e o modelo de computação não têm nenhuma referência a , diretamente ou indiretamente. O comprimento da entrada para cada máquina de Turing é limitado por uma constante.|V|

O que é conhecido

O problema pode ser resolvido em tempo finito, mesmo que seja infinito.G

O problema não é trivial no sentido de que é necessária alguma comunicação. Além disso, o tempo de execução depende de . No entanto, para qualquer Δ fixo , o problema pode ser resolvido em tempo constante, independentemente do tamanho de G ; em particular, o problema é solucionável em gráficos infinitamente grandes.ΔΔG

ΔΔ

Jukka Suomela
fonte
3

Encontrando a próxima geração de um autômato celular .

Isso pode ser resolvido como você descreveu em tempo constante. (ou seja, independente da entrada)


fonte
Eu acho que é necessário mais cuidado para realmente formular um problema computacional (não trivial, interessante) que seja solucionável em tempo finito usando autômatos celulares?
Jukka Suomela
1
Eu concordo com @Jukka. Considero que a versão atual desta resposta está no nível de um comentário, e não no informativo. Não descreve um problema computacional ou um algoritmo. Votado.
Aaron Sterling
2

Essencialmente, todo problema que seja pelo menos tão difícil quanto colorir exige um algoritmo com um tempo de execução dependente do número de nós na rede e, portanto, não pode funcionar em um gráfico infinito, mas localmente finito. Isso segue o log seminal do Linial * n limite inferior.

Pedro
fonte
2
Mas qual é exatamente o seu modelo de computação aqui? Linial assume que todos os nós têm identificadores numéricos exclusivos; se tentarmos mapeá-lo na configuração sugerida na pergunta original, teríamos máquinas de Turing que recebem seus identificadores numéricos em suas fitas de entrada. Mas agora o tamanho do identificador é ilimitado; apenas esperar até que todas as máquinas leiam seus próprios identificadores leva um tempo infinito. Eu argumentaria que o obstáculo não é realmente o limite inferior de Linial, mas é o modelo de computação: identificadores únicos são o modelo errado quando lidamos com infinitos.
Jukka Suomela
1
@Jukka: Eu imaginava um sistema em que todos os processadores eram anônimos quando escrevi a pergunta, exatamente para evitar IDs que crescem sem limites. Mas agora parece-me que pode haver uma questão não trivial aqui. Se você escolher um tamanho de programa e alguma função computável que limita o tamanho da vizinhança de qualquer processador, talvez o todo-poderoso adversário possa escolher um conjunto de IDs amplo, mas finito, para que o limite de Linial ainda seja um fator de alguma forma. O adversário pode precisar calcular uma função que cresce mais rápido do que qualquer função computável para fazer isso.
Aaron Sterling
0

UMAC0 0UMAC0 0

Joshua Grochow
fonte