Disclaimer: Eu sei muito pouco sobre a teoria da complexidade.
Sinto muito, mas não há realmente nenhuma maneira de fazer essa pergunta sem ser (terrivelmente) conciso:
Quais devem ser os morfismos na categoria "a" das máquinas de Turing?
Isso é obviamente subjetivo e depende da interpretação da teoria, portanto, uma resposta a essa pergunta deve idealmente fornecer algumas evidências e raciocínios que também apóiem a resposta.
Eu gostaria de enfatizar que estou procurando uma categoria de máquinas de Turing e não de linguagens formais, por exemplo. Em particular, acho que meus morfismos devem conter informações mais precisas do que reduções ou algo assim (não tenho certeza).
É claro que, se já existe uma categoria bem conhecida e usada na literatura, eu gostaria de saber o que é.
fonte
Respostas:
Saal Hardali mencionou que queria que uma categoria de máquinas de Turing fizesse geometria (ou pelo menos a teoria da homotopia). No entanto, existem muitas maneiras diferentes de alcançar objetivos semelhantes.
Existe uma analogia muito forte entre computabilidade e topologia. A intuição é que o término / não término é como o espaço de Sierpinski, pois o término é finitamente observável (ou seja, aberto) e o não término (não aberto). Veja as notas da palestra de Martin Escardo Topologia sintética de tipos de dados e espaços clássicos para uma introdução moderada, porém abrangente, a essas idéias.
Em computação concorrente e distribuída, geralmente é útil pensar nas possíveis execuções de um programa como um espaço e, em seguida, várias restrições de sincronização podem ser expressas como propriedades homotópicas do espaço. (O fato de a execução ter uma ordem de tempo parece exigir teoria da homotopia direcionada, em vez de teoria comum da homotopia.)
Veja o artigo de Eric Goubault: Algumas perspectivas geométricas sobre a teoria da concorrência para obter mais detalhes. Veja também o artigo vencedor do prêmio Goedel, de Maurice Herlihy e Nir Shavit, The Topological Structure of Asynchronous Computability , que resolveu alguns problemas abertos de longa data na teoria da programação distribuída.
Uma terceira idéia vem da teoria do tipo homotopia, da descoberta de que a teoria do tipo Martin-Löf é (provavelmente?) Uma apresentação sintática (no sentido de geradores e relações) da teoria dos ômega-grupóides - ou seja, os modelos de resumo teoria da homotopia. A melhor introdução a essas idéias é o livro de teoria dos tipos de homotopia .
Observe que todas essas idéias são muito diferentes umas das outras, mas todas ainda usam intuições geométricas! E ainda existem outros, que eu não conheço, como os usos que surgem na teoria da complexidade geométrica e a maneira como as teorias dos circuitos podem ser descritas em termos da teoria (co) homológica dos gráficos .
Basicamente, quando você está fazendo CS, a geometria é uma ferramenta - você a usa para formalizar suas intuições, para que você possa aproveitar o enorme corpo de trabalho que foi feito nela. Mas é um amplificador de idéias, não um substituto para ter idéias!
fonte
Se seus objetos são máquinas de Turing, existem várias possibilidades razoáveis de morfismos. Por exemplo:
1) Considere as máquinas de Turing como os autômatos e os morfismos usuais dos autômatos (mapas entre os alfabetos e os estados consistentes entre si) que também preservam os movimentos dos cabeçotes da fita ou invertem exatamente eles (por exemplo, sempre que a TM de origem for para a esquerda, a TM de destino será para a direita e vice-versa).
2a) Considere simulações ou bisimulações .
3) Considere o gráfico de transição da máquina de Turing (cada vértice é uma descrição completa do estado da máquina e das fitas, com arestas direcionadas correspondentes às transições que a TM faria) e considere os morfismos dos gráficos. No entanto, para as TMs, esse é um relacionamento muito grosseiro, pois ignora essencialmente a natureza local da computação (ignora, por exemplo, qual é o conteúdo das fitas).
Penso que a verdadeira questão é: o que você quer saber sobre as MTs ou fazer com elas? Na ausência disso, é difícil apresentar argumentos para uma definição sobre outra, além da naturalidade (no sentido usual da palavra, não no sentido categórico).
fonte
Você pode estar interessado nas categorias de Turing de Robin Cockett e Pieter Hofstra. Do ponto de vista da teoria das categorias, a questão "qual é a categoria das máquinas de Turing" é menos interessante do que "qual é a estrutura categórica subjacente à computação". Assim, Robin e Pieter identificam um tipo geral de categoria que é adequado para o desenvolvimento da teoria da computabilidade. Então, existem várias possibilidades para definir essa categoria a partir das máquinas de Turing. Por que ter uma categoria quando você pode ter uma categoria inteira?
fonte