Interpretação Geométrica da Computação

Sendo da Física, fui treinado para analisar muitos problemas do ponto de vista geométrico. Por exemplo, a geometria diferencial de variedades em sistemas dinâmicos etc. Quando leio os fundamentos da ciência da computação, sempre tento encontrar interpretações geométricas. Como uma interpretação geométrica plausível de conjuntos recursivamente enumeráveis ​​(trabalhei em uma parte em que tentei conectá-los à Geometria Algébrica, explorando a equivalência com os Conjuntos Diofantinos, mas a conexão parecia forçada e não consegui encontrar uma expressão "natural" dos fatos. formulação) ou um belo resultado geométrico para um algoritmo simples de classificação de números. Embora eu não seja um especialista, li pesquisas sobre a Teoria da Complexidade Geométrica e é certamente um programa interessante, mas estou mais interessado em ter uma visão geométrica de conceitos extremamente fundamentais, como a dinâmica de uma Máquina de Turing, o Lambda Calculus ou a estrutura de ( un) conjuntos computáveis ​​(em vez de problemas específicos). É um trabalho sem esperança encontrar estrutura geométrica nesses objetos ou podemos esperar resultados intricados? Existe alguma formulação de TCS que a trate geometricamente?

A semântica dos programas de computador pode ser entendida geometricamente de três maneiras distintas (e aparentemente incompatíveis).

• A abordagem mais antiga é via teoria de domínio . A intuição por trás da teoria do domínio surge da assimetria por trás do término e do não-término.

  Ao tratar programas extensionalmente (ou seja, apenas olhando para o comportamento de E / S, e não para a estrutura interna), sempre é possível confirmar em tempo finito que um programa é interrompido - basta aguardar até que ele pare. No entanto, não é possível confirmar que um programa não é interrompido, porque não importa quanto tempo você espere, sempre há um programa de interrupção que será executado por mais algumas etapas do que o esperado.

  Como resultado, a parada e o loop podem ser vistos como formando um espaço topológico ( o espaço de Sierpiński ). Isso leva a noções mais ricas de observação (via topologia de Scott) e, portanto, você pode interpretar programas como elementos de espaços topológicos. Esses espaços geralmente são bastante surpreendentes do ponto de vista tradicional - os domínios geralmente não são Hausdorff.

  A melhor introdução topológica que conheço a essas idéias é a topologia curta e extremamente acessível de Steve Vickers via Logic . Pode ser entendido como uma espécie de aquecimento para os espaços de pedra significativamente mais formidáveis ​​de Peter Johnstone .

  Se você estiver procurando notas de aula on-line, deixe-me sugerir a Topologia Sintética de Tipos de Dados e Espaços Clássicos de Martin Escardo .

• Outra visão surge da teoria da concorrência. Um programa simultâneo pode ser entendido como tendo várias execuções válidas (sequências de estados), dependendo de como as corridas são resolvidas. Então, o conjunto de execuções pode ser visto como um espaço, com cada sequência possível de estados entendida como um caminho através desse espaço. Em seguida, métodos da topologia algébrica e da teoria da homotopia podem ser aplicados para derivar invariantes sobre a execução do programa.

  Nir Shavit e Maurice Herlihy usam essa idéia para provar a impossibilidade de certos algoritmos distribuídos, pelos quais eles ganharam o prêmio Gödel de 2004. (Veja A Estrutura Topológica da Computação Assíncrona .) Eric Goubault tem um documento de pesquisa explicando as idéias relevantes em Algumas Perspectivas Geométricas na Teoria da Concorrência .

• Mais recentemente, foi observado que a estrutura do tipo de identidade na teoria dos tipos dependentes corresponde muito à noção de tipo de homotopia na teoria da homotopia - tão intimamente, de fato, que a teoria dos tipos dependentes pode realmente ser vista como uma espécie de "teoria das homotopias sintéticas"! (Vladimir Voevodsky brincou que ele passou vários anos desenvolvendo um novo cálculo para a teoria da homotopia, apenas para descobrir que seus colegas do departamento de CS já a estavam ensinando aos estudantes de graduação.)

  Veja o link de cody acima para o livro de teoria dos tipos de homotopia .

Curiosamente, essas três visões parecem incompatíveis entre si, ou pelo menos muito difíceis de conciliar. A teoria do tipo dependente é uma linguagem total; portanto, o não-termo (e a topologia de Scott) não surge nela. Também é confluente, de modo que a visão de computações como espaços também não surge. Da mesma forma, formular concorrência em termos de teoria de domínio se mostrou ferozmente difícil, e uma conta completamente satisfatória ainda é um problema em aberto.

Por acaso, houve um desenvolvimento recente na teoria dos tipos dependentes , na qual os tipos, que tradicionalmente representam uma invariante estática para um programa de computador, podem ser interpretados como um espaço topológico, ou melhor, como uma classe de equivalência de tais tipos. espaços (um tipo de homotopia ).

Este tem sido objeto de intensa pesquisa nos últimos anos, que culminou em um livro .

$\lambda$

Você conhece o GCT, mas pode não estar ciente do trabalho anterior de Mulmuley em mostrar uma separação entre um subconjunto de computações PRAM e P, que usa idéias geométricas de como uma computação pode ser vista como escavando um espaço.

Muitos limites inferiores para problemas no modelo de árvore de decisão algébrica reduzem-se ao raciocínio sobre a topologia dos espaços subjacentes das soluções (os números de Betti aparecem como um parâmetro relevante).

Em certo sentido, TODA a otimização é geométrica: programas lineares envolvem encontrar o ponto mais baixo de um polítopo em altas dimensões, SDPs são funções lineares no espaço de matrizes semidefinidas e assim por diante. A geometria é muito usada no design de algoritmos aqui.

Sobre esse tema, há uma conexão longa e profunda entre nossa capacidade de otimizar determinadas funções nos gráficos e nossa capacidade de incorporar espaços métricos em certos espaços normatizados. Esta é uma vasta literatura agora.

Finalmente, nos últimos anos, houve um grande interesse nos chamados mecanismos de "levantamento e projeto" para resolver problemas de otimização, e eles fazem uso pesado da geometria subjacente e elevam-se para espaços dimensionais mais altos: noções da geometria algébrica um papel importante aqui.

$T_1$ ). Eles são "direcionados" em um sentido, então seria preciso criar uma geometria direcionada para explicar o fenômeno. E há truques para simular a situação (essencialmente você fica de cabeça para baixo).

Uma maneira de entender a relação entre processamento de informações (também conhecido como "computação") e geometria é que o processamento de informações precede a geometria. Essa visão deve ser familiar em certas partes da física. Por exemplo, na teoria da relatividade, estudamos tanto a estrutura causal do espaço-tempo (seu processamento de informações) quanto sua estrutura geométrica . Muitos considerariam o último mais básico que o anterior.

Essas conexões foram notadas no passado e, há vários anos, houve um esforço para conectar os aspectos teóricos da informação da ciência da computação à teoria da relatividade. Uma das tarefas que as pessoas queriam resolver era: a partir da estrutura de causalidade do espaço-tempo (que é apenas uma ordem parcial no espaço-tempo), reconstruir a topologia do espaço-tempo ou, possivelmente, também a geometria. Recuperar a topologia de uma ordem parcial é o tipo de coisa em que a teoria do domínio é boa; portanto, houve algum sucesso.

Referências:

• Estruturas computacionais para modelagem de espaço, tempo e causalidade , Seminário Dagstuhl 06341, 20–25 de agosto de 2006

• Key Martin e Prakash Panangaden: geometria do espaço- tempo a partir da estrutura causal e uma medição

$U$

interpretando de maneira criativa sua pergunta, lembre-se de outras possibilidades além do GCT, como você menciona. Uma maneira é procurar problemas indecidíveis (também conhecidos como Turing), que são bastante onipresentes.

• Aperiodic Ladrilhando o avião e Penrose lado a lado . Está provado que a questão de saber se existe ou não um mosaico aperódico do avião é indecidível.

• Autômatos celulares que também demonstram cada vez mais conexões profundas com a física, muitos problemas indecidíveis relacionados, MT completo e comprovado, e são naturalmente interpretados como (e convertidos entre) os quadros computacionais da MT.

• $(x,y)$

• Indecidibilidade em sistemas dinâmicos (Hainry), novamente às vezes intimamente ligada à física. sistemas dinâmicos geralmente têm uma interpretação geométrica multidimensional.

• Linguagens de programação visual . um programa pode ser visto como um tipo de gráfico (direcionado?) com diferentes tipos de vértices (por exemplo, operação condicional, aritmética) etc.