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

14

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?

swarnim_narayan
fonte
2
Eu acho que a pergunta é muito extensa e não muito clara e precisa ser melhorada. Parece-me que, em essência, você está fazendo uma pergunta de solicitação de referência sobre a formulação geométrica e o tratamento da TCS.
Kaveh
1
Se você está procurando que eles possam aprender a teoria da computabilidade, não terá muita sorte, pois esses trabalhos geralmente são escritos para pessoas que são bem versadas no tratamento clássico da teoria da computabilidade. Você precisa aprender o novo idioma se quiser aprender a teoria da computabilidade. Dito isto, existem tratamentos categóricos da teoria da computabilidade (mas como eu disse, eles são escritos para pessoas que conhecem a teoria da computabilidade).
precisa saber é o seguinte
5
@ Kaveh, Seria extremamente útil se você pudesse me fornecer uma referência a um tratamento categórico da Teoria da Computabilidade. Embora, como você disse, possa não ser compreensível sem uma compreensão rigorosa do tratamento clássico da computabilidade, estou tentando o meu melhor para chegar lá.
swarnim_narayan
Você pode esclarecer o que você quer dizer com geometria no contexto da sua pergunta?
22813 Martin Berger
@ Wang, acho que "a solicitação de referência para computabilidade da perspectiva da teoria das categorias" pode ser uma nova pergunta separada, e há outras como Andrej (por exemplo, veja isso ) que podem responder muito melhor do que eu.
Kaveh

Respostas:

12

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.

Neel Krishnaswami
fonte
"Como resultado, parar e dar laços pode ser visto como formando um espaço topológico (o espaço de Sierpiński). Isso eleva as noções mais ricas de observação (via topologia de Scott) e, portanto, você pode interpretar programas como elementos de espaços topológicos". é uma boa referência para isso que está disponível online?
T ....
1
@JAS: Adicionei um link para algumas das anotações de Martin Escardo sobre o assunto.
Neel Krishnaswami
6

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 .

λ

cody
fonte
6

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.

Suresh Venkat
fonte
".... modelo de árvore de decisão algébrica reduz a raciocínio sobre a topologia de espaços subjacentes de soluções" É verdade que muitos resultados sobre cálculos podem ser reduzidos para encontrar informações sobre conjuntos conectados? Ou esse resultado é especial?
T ....
1
@JAS: Há alguns resultados que podem ser reduzidos a limitar o número de componentes conectados, mas eu não diria "muitos". Na complexidade algébrica, a técnica mais comum (pelo menos nos últimos 10 a 15 anos) é limitar as dimensões de vários espaços de derivadas parciais e espaços relacionados. Isso pode ser visto como encontrar equações que desaparecem em certas variedades algébricas, que são, em certo sentido, "geométricas". Mas eu ainda não diria que isso abrange "a maioria" dos resultados, esp. Resultados de complexidade booleana, que usam uma variedade de (pelo menos aparentemente) técnicas não geométricas.
Joshua Grochow 21/09
@ JoshuaGrochow Yah Eu não vi muito trabalho topológico tanto quanto o AG clássico, mesmo em derivadas parciais. Eu estava pensando nas respostas para esta pergunta aqui cstheory.stackexchange.com/questions/5907/… quando vi essa pergunta.
T ....
5

T1 ). 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:

Andrej Bauer
fonte
5

você

Adam Bouland
fonte
4

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.

vzn
fonte
re autômatos celulares, veja também jogo da vida . Conway geralmente recebe crédito por provar que Turing está completo, embora uma referência exata pareça difícil de encontrar. provavelmente é também a prova mais antiga da integridade de Turing associada às autoridades de certificação.
vzn