sobre productividad y complejidad en el análisis computable a través de teoremas de estilo Rice para funciones reales
Autores: Xie, Jingnan; Hunt, Harry B.; Stearns, Richard E.
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
sobre productividad y complejidad en el análisis computable a través de teoremas de estilo Rice para funciones reales
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Funciones reales
Complejidad
Productividad
Indecidibilidad
Teoremas al estilo de Rice
Continuidad
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 38
Citaciones: Sin citaciones
Este trabajo investiga la complejidad de las funciones reales a través de técnicas de demostración inspiradas en la teoría del lenguaje formal. La productividad, que es una forma más fuerte de enumerabilidad no recursiva, se emplea para analizar la complejidad de varios problemas relacionados con las funciones reales. Nuestro trabajo proporciona una profunda reexaminación del décimo problema de Hilbert y la equivalencia al problema de la función idénticamente 0, extendiendo los resultados de indecidibilidad de estos problemas al ámbito de la productividad. Además, estudiamos la complejidad de la equivalencia al problema de la función idénticamente 0 en diferentes dominios. Luego construimos reducciones many-one altamente eficientes para establecer teoremas de estilo Rice para el estudio de funciones reales. Específicamente, mostramos que muchos predicados, incluidos los relacionados con la continuidad, diferenciabilidad, continuidad uniforme, diferenciabilidad derecha e izquierda, semi-diferenciabilidad y diferenciabilidad continua, son tan difíciles como la equivalencia al problema de la función idénticamente 0. Debido a su alta eficiencia, estas reducciones preservan casi cualquier nivel de complejidad, lo que nos permite abordar simultáneamente los resultados de complejidad y productividad. Al demostrar estos resultados, que destacan un aspecto más matizado y potencialmente más intrigante de la teoría de funciones reales, proporcionamos nuevas perspectivas sobre cómo se pueden analizar diversas propiedades de las funciones reales.
Descripción
Este trabajo investiga la complejidad de las funciones reales a través de técnicas de demostración inspiradas en la teoría del lenguaje formal. La productividad, que es una forma más fuerte de enumerabilidad no recursiva, se emplea para analizar la complejidad de varios problemas relacionados con las funciones reales. Nuestro trabajo proporciona una profunda reexaminación del décimo problema de Hilbert y la equivalencia al problema de la función idénticamente 0, extendiendo los resultados de indecidibilidad de estos problemas al ámbito de la productividad. Además, estudiamos la complejidad de la equivalencia al problema de la función idénticamente 0 en diferentes dominios. Luego construimos reducciones many-one altamente eficientes para establecer teoremas de estilo Rice para el estudio de funciones reales. Específicamente, mostramos que muchos predicados, incluidos los relacionados con la continuidad, diferenciabilidad, continuidad uniforme, diferenciabilidad derecha e izquierda, semi-diferenciabilidad y diferenciabilidad continua, son tan difíciles como la equivalencia al problema de la función idénticamente 0. Debido a su alta eficiencia, estas reducciones preservan casi cualquier nivel de complejidad, lo que nos permite abordar simultáneamente los resultados de complejidad y productividad. Al demostrar estos resultados, que destacan un aspecto más matizado y potencialmente más intrigante de la teoría de funciones reales, proporcionamos nuevas perspectivas sobre cómo se pueden analizar diversas propiedades de las funciones reales.