Interpretación Geométrica de la Computación

Siendo de Física, he sido entrenado para investigar muchos problemas desde un punto de vista geométrico. Por ejemplo, la geometría diferencial de múltiples en sistemas dinámicos, etc. Cuando leo los fundamentos de la informática, siempre trato de encontrar interpretaciones geométricas. Como una interpretación geométrica plausible de conjuntos recursivamente enumerables (trabajé en una parte en la que intenté conectarlos con la geometría algebraica explotando la equivalencia con conjuntos de diofantina, pero la conexión parecía forzada y no pude encontrar una expresión "natural" de los hechos en eso formulación) o un hermoso resultado geométrico para un algoritmo simple para ordenar números. Aunque no soy un experto, he leído encuestas sobre la teoría de la complejidad geométrica y seguramente es un programa interesante, pero estoy más interesado en tener una visión geométrica de conceptos extremadamente fundamentales como la dinámica de una máquina de Turing, el cálculo de Lambda o la estructura de ( un) conjuntos computables (en lugar de problemas específicos). ¿Es un trabajo inútil encontrar una estructura geométrica en estos objetos o uno puede esperar algunos resultados intrincados? ¿Existe alguna formulación de TCS que lo trate geométricamente?

La semántica de los programas de computadora se puede entender geométricamente de tres maneras distintas (y aparentemente incompatibles).

• El enfoque más antiguo es a través de la teoría de dominios . La intuición detrás de la teoría del dominio surge de la asimetría detrás de la terminación y la no terminación.

  Al tratar los programas de manera extensional (es decir, solo observando su comportamiento de E / S, y no su estructura interna), siempre es posible confirmar en un tiempo finito que un programa se detiene, solo espere hasta que se detenga. Sin embargo, no es posible confirmar que un programa no se detenga, porque no importa cuánto tiempo espere, siempre hay un programa de detención que se ejecutará por unos pocos pasos más de los que esperaba.

  Como resultado, la detención y el bucle pueden verse como formando un espacio topológico ( el espacio Sierpiński ). Esto se eleva a nociones más ricas de observación (a través de la topología de Scott), y de este modo puede interpretar los programas como elementos de espacios topológicos. Estos espacios son generalmente bastante sorprendentes desde un punto de vista tradicional: los dominios generalmente no son Hausdorff.

  La mejor introducción topológica que conozco de estas ideas es la breve y extremadamente accesible Topología de Steve Vickers a través de Logic . Se puede entender como una especie de calentamiento para los espacios de piedra significativamente más formidables de Peter Johnstone .

  Si está buscando notas de clase en línea, permítame sugerirle la topología sintética de Martin Escardo sobre tipos de datos y espacios clásicos .

• Otra opinión surge de la teoría de la concurrencia. Se puede entender que un programa concurrente tiene múltiples ejecuciones válidas (secuencias de estados), dependiendo de cómo se resuelvan las razas. Entonces, el conjunto de ejecuciones puede verse como un espacio, con cada posible secuencia de estados entendida como una ruta a través de este espacio. Luego, los métodos de la topología algebraica y la teoría de la homotopía se pueden aplicar para derivar invariantes sobre la ejecución del programa.

  Nir Shavit y Maurice Herlihy utilizan esta idea para demostrar la imposibilidad de ciertos algoritmos distribuidos, por los cuales ganaron el premio Gödel 2004. (Consulte La estructura topológica de la computación asincrónica ). Eric Goubault tiene un estudio que explica las ideas relevantes en Algunas perspectivas geométricas en la teoría de la concurrencia .

• Más recientemente, se ha observado que la estructura del tipo de identidad en la teoría del tipo dependiente se corresponde muy estrechamente con la noción de tipo de homotopía en la teoría de la homotopía; de hecho, tan estrechamente, esa teoría del tipo dependiente se puede ver como una especie de ¡"teoría de la homotopía sintética"! (Vladimir Voevodsky bromeó diciendo que pasó varios años desarrollando un nuevo cálculo para la teoría de la homotopía, solo para descubrir que sus colegas en el departamento de CS ya lo estaban enseñando a estudiantes universitarios).

  Vea el enlace de Cody arriba al libro de teoría del tipo de homotopía .

Curiosamente, estos tres puntos de vista parecen incompatibles entre sí, o al menos muy difíciles de conciliar. La teoría del tipo dependiente es un lenguaje total, por lo que no surge la no terminación (y la topología de Scott). También es confluente, por lo que tampoco surge la vista de los cálculos como espacios. Del mismo modo, formular concurrencia en términos de teoría de dominio ha resultado extremadamente difícil, y una explicación completamente satisfactoria sigue siendo un problema abierto.

De hecho, ha habido un desarrollo reciente en la teoría de los tipos dependientes , en la que los tipos, que tradicionalmente representan una invariante estática para un programa de computadora, pueden interpretarse como un espacio topológico, o más bien una clase de equivalencia de tales tipos. espacios (un tipo de homotopía ).

Este ha sido el tema de una intensa investigación en los últimos años, que culminó en un libro .

$\lambda$

Usted está al tanto de GCT, pero es posible que no esté al tanto del trabajo anterior de Mulmuley para mostrar una separación entre un subconjunto de cálculos PRAM y P, que utiliza ideas geométricas de cómo se puede ver un cálculo como tallar un espacio.

Muchos límites inferiores para problemas en el modelo de árbol de decisión algebraico se reducen al razonamiento sobre la topología de los espacios subyacentes de soluciones (los números de Betti se muestran como un parámetro relevante).

En cierto sentido, TODA la optimización es geométrica: los programas lineales implican encontrar el punto más bajo de un politopo en altas dimensiones, los SDP son funciones lineales sobre el espacio de las matrices semidefinidas, y así sucesivamente. La geometría se usa mucho en el diseño de algoritmos aquí.

Sobre ese tema, existe una conexión larga y profunda entre nuestra capacidad de optimizar ciertas funciones en gráficos y nuestra capacidad de incrustar espacios métricos en ciertos espacios normados. Esta es una vasta literatura ahora.

Finalmente, en los últimos años ha habido un gran interés en los llamados mecanismos de "levantar y proyectar" para resolver problemas de optimización, y estos hacen un uso intensivo de la geometría subyacente y se elevan a espacios dimensionales superiores: nociones del juego de geometría algebraica Un papel importante aquí.

$T_1$

Una forma de entender la relación entre el procesamiento de la información (también conocido como "cálculo") y la geometría es que el procesamiento de la información precede a la geometría. Esta vista debería ser familiar desde ciertas partes de la física. Por ejemplo, en la teoría de la relatividad, estudiamos tanto la estructura causal del espacio-tiempo (su procesamiento de información) como su estructura geométrica . Muchos considerarían que este último es más básico que el primero.

Estas conexiones se han notado en el pasado y hace varios años hubo un esfuerzo por conectar los aspectos teóricos de la información de la informática con la teoría de la relatividad. Una de las tareas que la gente quería resolver era: a partir de la estructura de causalidad del espacio-tiempo (que es solo un orden parcial en el espacio-tiempo), reconstruir la topología del espacio-tiempo, o posiblemente también la geometría. Recuperar la topología de un orden parcial es el tipo de cosas en las que la teoría de dominios es buena, por lo que hubo algo de éxito.

Referencias

• Estructuras computacionales para modelar espacio, tiempo y causalidad , Seminario Dagstuhl 06341, 20-25 de agosto de 2006

• Key Martin y Prakash Panangaden: geometría del espacio - tiempo a partir de la estructura causal y una medición

$U$

Al interpretar creativamente su pregunta, le vienen a la mente algunas posibilidades distintas de GCT como usted menciona. una forma es buscar problemas indecidibles (también conocidos como integridad de Turing) que son bastante ubicuos.

• aperiódico Azulejos del avión y azulejos de Penrose . Se ha demostrado que la cuestión de si existe un mosaico aperodico del avión es indecidible.

• Autómatas celulares que también muestran cada vez más conexiones profundas con la física, muchos problemas indecidibles relacionados, TM probado completo, y naturalmente se interpretan como (y se convierten entre) cuadros computacionales TM.

• algoritmos como fractales . un área más poco desarrollada (es decir, ¡investigación activa / en curso!), pero varias preguntas indecidibles, como un punto complejo$(x,y)$¿Está en el set de Mandelbrot ?

• Indecidibilidad en sistemas dinámicos (Hainry), nuevamente a veces estrechamente relacionado con la física. Los sistemas dinámicos generalmente tienen una interpretación geométrica multidimensional.

• Lenguajes de programación visual . un programa puede verse como un tipo de gráfico (¿dirigido?) con diferentes tipos de vértices (por ejemplo, operación condicional, aritmética), etc.