Brecha entre y "segundo más grande"

13

Si es el conjunto de tiempos de detención de máquinas Turing de estado en un alfabeto binario con cinta inicial vacía, entonces .n B B ( n ) = máx. H T ( n )HT(n)nBB(n)=maxHT(n)

¿Qué podemos decir sobre el segundo número más grande en HT(n) ? Llame a esto BB2(n) .

BB2(n) es trivialmente incuestionable, ya que permite calcular BB(n) : solo espere a que una máquina más se detenga. Ingenuamente, esperaría que la brecha BB(n)−BB2(n) esté "ocupada como un castor", creciendo más rápido que cualquier función computable. ¿Es esto demostrable?

computability Geoffrey Irving
fuente
Supongamos que uno de los n estados no es accesible.
micrófono
@mic: No creo que sea relevante. parece altamente improbable. BB(n−1)=BB2(n)
Geoffrey Irving
1
Esto dependerá de la codificación. Si voltea los estados de aceptación / rechazo, el número de estados sigue siendo el mismo y, por lo tanto, es el momento de detenerse, lo que haría que . BB(n)=BB2(n)
Lance Fortnow
66
Es por eso que dejé que sea ​​el conjunto de tiempos de detención, para que la brecha no sea cero por construcción. HT(n)
Geoffrey Irving
1
¿Es posible probar que la brecha no es eventualmente 1?
Geoffrey Irving

Respuestas:

-1

  1. El número de estados es solo una noción de complejidad de la descripción de funciones computables en un modelo, puede elegir cualquier modelo de computación y cualquier codificación de ellos como cadenas binarias y luego tomar la longitud como n y definir BB (n) en función de eso y todos los resultados interesantes sobre BB (n) seguirían siendo ciertos, hay un aburrido especial sobre el modelo TM y el número de estados.

  2. No hay nada que les impida elegir cualquier modelo modificado de TM. En general, las preguntas que no son invariables bajo tales cambios de representación de TM no son sobre computabilidad o TM sino sobre la representación particular (como BB (n) mod 2, etc.) y, a menos que haya alguna razón particular para que sean interesantes, no lo hacen Vale la pena seguir en mi humilde opinión. Son buenos rompecabezas pero no tienen mucho valor. l Tenga en cuenta que "BB (n) no es computable" es invariable bajo el cambio de representaciones de TM.

  3. Entonces, ¿esta pregunta es invariable bajo el cambio de representación de funciones computables? La respuesta creo que es no.

yo. Considere una representación donde tenemos dos estados especiales 0 y 1 y 0 es inicial y solo puede pasar a 1 o 0 es inalcanzable y 1 es inicial. En esta codificación, la diferencia es 1.

ii. Considere otra representación donde tenemos un UTM más una parte que escribe n bits en cinta antes de pasar a UTM. Entonces la pregunta se convierte en max f (x) - 2ndmax f (x) donde maxes están sobre cadenas de n bits y donde f es una función computable arbitraria. Solo necesitamos encontrar una función computable donde esto no sea computable. No lo he pensado mucho, pero mi instinto dice que existe una función computable.

Kaveh
fuente
2
Nada de esto es relevante, porque elegí máquinas estándar de Turing como mi noción de computación. Estoy de acuerdo en que existen algunas definiciones comunes diferentes (cinta de uno o dos lados, ya sea que la cinta comience con cero o algún símbolo vacío especial), pero nada como los UTM precodificados que menciona.
Geoffrey Irving
1
Usar para contar una codificación completamente diferente sería una pregunta diferente y mucho menos interesante, ya que, como usted dice, la codificación se puede elegir para romper la pregunta. n
Geoffrey Irving
Permítanme decirlo de otra manera: ¿por qué está interesado en la respuesta? Es un buen rompecabezas como muchos otros sobre BB para una representación particular de TM, pero no revelan nada sobre computabilidad y computación. La elección del estándar para la representación de TM fue una acción arbitraria, uno podría haber elegido mi primera representación anterior y la respuesta a su pregunta habría sido 1. El hecho de que se llame estándar no lo hace especial entre las representaciones.
Kaveh
Esto no es diferente de preguntar si alguna ecuación de Diophantienne E elegida arbitrariamente tiene una solución entera. Hay infinitas ecuaciones de este tipo, sin una razón por la que uno esté interesado en E no es una pregunta muy interesante. Cuando las personas hacen preguntas como "computabilidad de BB (n) mod 2", piensan que están haciendo preguntas profundas sobre computabilidad, mientras que en realidad es más como pedir solubilidad de alguna ecuación de Diophantienne elegida arbitrariamente, es solo que algunas de ellas parecen más agradables para el ojo.
Kaveh
2
Estoy interesado porque creo que la respuesta es la misma para todas las codificaciones no degegerate: no se puede probar, no se puede probar que no se puede probar, etc. Pero no sé cómo expresar esto, así que elegí una. El hecho de que sea trivial para codificaciones especialmente elegidas es similar al problema de detención que puede resolverse para las máquinas detenidas por construcción.
Geoffrey Irving