¿La categoría de máquinas de Turing?

Descargo de responsabilidad: sé muy poco sobre la teoría de la complejidad.

Lo siento, pero realmente no hay forma de hacer esta pregunta sin ser (terriblemente) conciso:

¿Cuáles deberían ser los morfismos en "la" categoría de las máquinas de Turing?

Esto es obviamente subjetivo y depende de la propia interpretación de la teoría, por lo que una respuesta a esta pregunta idealmente debería proporcionar evidencia y razonamiento que respalden la respuesta también.

Me gustaría enfatizar el punto de que estoy buscando una categoría de máquinas de Turing y no de lenguajes formales, por ejemplo. En particular, creo que mis morfismos deberían contener información más fina, luego reducciones o algo así (aunque no estoy seguro).

Por supuesto, si ya hay una categoría conocida y usada en la literatura, me gustaría saber de qué se trata.

cc.complexity-theory turing-machines ct.category-theory Saal Hardali
fuente

Lo dijiste tú mismo: funciones computables.

Yuval Filmus

@Raphael, la cosa es que nunca se define realmente una estructura hasta que se coloca en una categoría. Es entonces cuando se eliminan las características no esenciales de la definición específica.

Saal Hardali

@SaalHardali Tenga en cuenta que no todos suscriben la promesa de salvación hecha por los teóricos de la categoría. De hecho, muchos ruedan los ojos.

Raphael

@JoshuaGrochow Hay un morfismo etiquetado

reduce

(o quizás al revés), es decir

. Esto es, por ejemplo, para máquinas que en cada entrada se detienen o no, pero no tienen más salida.

f

$f$

T_{1}

$T_1$

T_{2}

$T_2$

f

$f$

T_{2}

$T_2$

T_{1}

$T_1$

T_{1} (x) = T_{2} (f (x))

$T_1(x) = T_2(f(x))$

Yuval Filmus el

Aparte: ¿por qué los TM deben ser objetos? También podrían ser morfismos.

Martin Berger

Respuestas:

Saal Hardali mencionó que quería una categoría de máquinas de Turing para hacer geometría (o al menos teoría de homotopía). Sin embargo, hay muchas formas diferentes de lograr objetivos similares.

Existe una analogía muy fuerte entre la computabilidad y la topología. La intuición es que la terminación / no terminación es como el espacio de Sierpinski, ya que la terminación es finitamente observable (es decir, abierta) y la no terminación no (no está abierta). Vea las notas de la conferencia de Martin Escardo Topología sintética de tipos de datos y espacios clásicos para una introducción moderada pero completa de estas ideas.
En la computación concurrente y distribuida, a menudo es útil pensar en las posibles ejecuciones de un programa como un espacio, y luego varias restricciones de sincronización pueden expresarse como propiedades homotópicas del espacio. (El hecho de que la ejecución tenga un orden temporal parece requerir una teoría de homotopía dirigida, en lugar de una teoría de homotopía ordinaria).

Vea el artículo de Eric Goubault Algunas perspectivas geométricas sobre la teoría de concurrencia para más detalles. También vea el artículo ganador del premio Goedel de Maurice Herlihy y Nir Shavit, The Topological Structure of Asynchronous Computability , que resolvió algunos problemas abiertos de larga data en la teoría de la programación distribuida.
Una tercera idea surge a través de la teoría del tipo de homotopía, a través del descubrimiento de que la teoría del tipo Martin-Löf es (¿probable?) Una presentación sintáctica (en el sentido de generadores y relaciones) de la teoría de los omega-groupoids, es decir, los modelos abstractos Teoría de la homotopía. La mejor introducción a estas ideas es el libro de teoría del tipo de homotopía .

Tenga en cuenta que todas estas ideas son muy diferentes entre sí, ¡pero todas siguen utilizando intuiciones geométricas! Y todavía hay otros, que no sé, como los usos que surgen en la teoría de la complejidad geométrica y la forma en que las teorías de los circuitos se pueden describir en términos de la teoría de (co) homología de los gráficos .

Básicamente, cuando está haciendo CS, la geometría es una herramienta : la usa para formalizar sus intuiciones, de modo que pueda obtener influencia a través del enorme cuerpo de trabajo que se ha realizado en ella. ¡Pero es un amplificador de ideas, no un sustituto de tener ideas!

Neel Krishnaswami
fuente

Si sus objetos son máquinas de Turing, existen varias posibilidades razonables de morfismos. Por ejemplo:

1) Considere las máquinas de Turing como los autómatas que son, y considere los morfismos habituales de los autómatas (mapas entre los alfabetos y los estados que son consistentes entre sí) que también conservan los movimientos de los cabezales de la cinta, o exactamente al revés ellos (por ejemplo, cada vez que la TM de origen va a la izquierda, la TM de destino va a la derecha y viceversa)

2a) Considere simulaciones o bisimulaciones .

$T_1$ $T_2$ $f$ $T_1(x) = T_2(f(x))$ $x$

3) Considere el gráfico de transición de la máquina de Turing (cada vértice es una descripción completa del estado de la máquina y las cintas, con bordes dirigidos correspondientes a las transiciones que la TM haría) y considere los morfismos de los gráficos. Sin embargo, para los TM es una relación muy burda, ya que esencialmente ignora la naturaleza local de la computación (ignora, por ejemplo, cuáles son los contenidos de las cintas).

Creo que la verdadera pregunta es: ¿qué es lo que quieres saber sobre TM o hacer con ellos? En ausencia de esto, es difícil dar argumentos para cualquier definición sobre otra, más allá de la naturalidad (en el sentido habitual de la palabra, no en el sentido categórico).

Joshua Grochow
fuente

Soy muy nuevo en este tipo de matemáticas. Leí en el pasado sobre la teoría de la complejidad, pero solo recientemente la volví a leer después de ver a alguien en Internet que decía que de alguna manera las técnicas cohomológicas entrarían en la teoría de la complejidad en el próximo siglo y me interesó. Después de leer un poco, me di cuenta de que, más allá de una comprensión superficial de la definición de una máquina de turing, básicamente no tengo idea de lo que codifica exactamente. Así llegué a la pregunta. Entonces se podría decir que a un nivel muy rudimentario estoy tratando de imaginar cómo la cohomología puede ingresar a la teoría de la complejidad.

Saal Hardali

Me doy cuenta de que esto es extremadamente prematuro para alguien como yo que entiende muy poco sobre este tema, pero quería jugar un poco con esta idea en mi cabeza de "hacer teoría de homotopía en la categoría de máquinas de turing". Su respuesta es agradable y ciertamente pretendo leer más sobre aspectos de ella. Gracias.

Saal Hardali

@SaalHardali: ¿Tengo curiosidad de dónde lees que la cohomología entrará en la teoría de la complejidad? Puedo pensar en dos formas, pero todavía no veo una ruta a través de la teoría del tipo de homotopía (tal vez porque todavía no entiendo HoTT lo suficientemente bien). Las dos formas en que puedo ver: (1) en computación distribuida esto ya ha sucedido, a saber. Herlihy y Rajsbaum, y (2) a través de la teoría de la complejidad geométrica.

Joshua Grochow

Según la teoría de la homotopía, me refería a la idea general de estudiar categorías con equivalencias débiles y no tanto HoTT. Lo leí en una encuesta sobre P =? NP no es difícil de encontrar, creo que estaba vinculado a una de las preguntas en este sitio. Supongo que mi primera suposición (como un extraño) fue que tal vez haya algún tipo de equivalencia débil interesante en alguna categoría de un modelo de cómputo que corresponda de alguna manera a las clases de complejidad y luego estudiar los functores invariantes bajo esas equivalentes débiles constituirá lo que yo llamo un " teoría de la homotopía "esto es probablemente muy ingenuo y totalmente extraño.

Saal Hardali

En caso de que su interés sea la teoría de la complejidad en lugar de la teoría de la computabilidad, tal vez esta respuesta le sea útil: cstheory.stackexchange.com/a/3422/4896

Sasho Nikolov

Puede interesarle las categorías de Turing de Robin Cockett y Pieter Hofstra. Desde el punto de vista de la teoría de categorías, la pregunta "cuál es la categoría de las máquinas de Turing" es menos interesante que "cuál es la estructura categórica que subyace a la computación". Así, Robin y Pieter identifican un tipo general de categoría que es adecuado para desarrollar la teoría de la computabilidad. Luego, hay varias posibilidades para definir dicha categoría a partir de las máquinas Turing. ¿Por qué tener una categoría cuando puedes tener una categoría completa de ellas?

Andrej Bauer
fuente