Problemas abiertos fáciles de enunciar en teoría de computabilidad

14

Estaba buscando problemas abiertos interesantes y fáciles de expresar en computabilidad (comprensible para estudiantes de pregrado que toman su primer curso en computabilidad) para dar ejemplos de problemas abiertos (y obviamente quiero que los estudiantes puedan entender el problema sin necesitar demasiados nuevos definiciones y también ser interesante para ellos).

Encontré esta lista, pero los problemas en ella parecen demasiado complicados para los estudiantes de pregrado y necesitarán pasar un tiempo considerable dando definiciones antes de señalar el problema. El único problema que he encontrado hasta ahora es

¿El problema de la diofantina sobre los números racionales es decidible?

¿Conoces algún otro problema abierto interesante y fácil de enunciar en la teoría de la computabilidad?

computability Kaveh
fuente
1
¿Qué cantidad / tipo de conocimiento previo podemos asumir, por ejemplo, con respecto a autómatas, lenguajes formales, algoritmos?
Raphael
@Raphael, puede asumir el conocimiento de la teoría básica de computabilidad, por ejemplo, saben lo que se cubre en la parte de computabilidad del libro de Sipser "Introducción a la teoría de la computación".
Kaveh
La teoría de la computabilidad es definitivamente más abstracta que, por ejemplo, la teoría de la complejidad especialmente para estudiantes universitarios. No he oído hablar de clases completas de pregrado para la teoría de la computabilidad. que cubres ¿Tiene un plan de estudios en línea o es similar a otro en línea? podría ser útil repasar la historia del décimo problema de Hilbert, que permaneció abierto durante la mayor parte del siglo XX y es uno de los "grandes" temas en el campo. Algunos dicen que con justificación real es uno de los más importantes del siglo XX.
vzn

Respuestas:

4

(re,≤T)F:re→reun≤TsiF(un)≤TF(si)

Carl Mummert
fuente
1
¿Cómo es este problema interesante para el estudiante universitario promedio? ¿Hay alguna consecuencia conocida que pueda derivarse de la existencia de tal automorfismo? Creo que la motivación es primordial al introducir nuevos conceptos, especialmente si es solo para mostrar a los estudiantes un "famoso problema abierto".
Janoma
2
@Janoma: la motivación es estudiar (y comprender) la estructura global de los grados de Turing. Sería fácil establecer sin probar algunos resultados, como la densidad, y mencionar esto como un problema abierto fácil de establecer pero difícil de resolver.
Carl Mummert