Polinomio análogo del teorema del punto fijo de Gandy
Autores: Goncharov, Sergey; Nechesov, Andrey
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Polinomio análogo del teorema del punto fijo de Gandy
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Método general
P-calculable
Análogo polinomial
Teorema del punto fijo de Gandy
Operador
Generando familias de fórmulas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 30
Citaciones: Sin citaciones
El trabajo sugiere un método general para probar si un cierto conjunto es p-calculable o no. El método se basa en un análogo polinomial del teorema clásico del punto fijo de Gandy. El teorema clásico de Gandy trata sobre la extensión de un predicado a través de un operador especial y afirma que el punto fijo más pequeño de este operador es un conjunto -set. Nuestro trabajo utiliza un nuevo tipo de operador que extiende predicados de manera que el punto fijo más pequeño siga siendo un conjunto p-calculable. Además, si en el teorema clásico del punto fijo de Gandy se utiliza la -fórmula especial en la construcción del operador, entonces un nuevo operador utiliza familias generadoras especiales de fórmulas en lugar de una sola fórmula. Este trabajo abre amplias perspectivas para la aplicación del análogo polinomial del teorema de Gandy en la construcción de nuevos tipos de términos y fórmulas, en la construcción de nuevos tipos de datos y programas de complejidad computacional polinómica en lenguajes Turing completos.
Descripción
El trabajo sugiere un método general para probar si un cierto conjunto es p-calculable o no. El método se basa en un análogo polinomial del teorema clásico del punto fijo de Gandy. El teorema clásico de Gandy trata sobre la extensión de un predicado a través de un operador especial y afirma que el punto fijo más pequeño de este operador es un conjunto -set. Nuestro trabajo utiliza un nuevo tipo de operador que extiende predicados de manera que el punto fijo más pequeño siga siendo un conjunto p-calculable. Además, si en el teorema clásico del punto fijo de Gandy se utiliza la -fórmula especial en la construcción del operador, entonces un nuevo operador utiliza familias generadoras especiales de fórmulas en lugar de una sola fórmula. Este trabajo abre amplias perspectivas para la aplicación del análogo polinomial del teorema de Gandy en la construcción de nuevos tipos de términos y fórmulas, en la construcción de nuevos tipos de datos y programas de complejidad computacional polinómica en lenguajes Turing completos.