logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro