En la teoría de la computabilidad y la lógica matemática, el algoritmo de Tarski-Kuratowski es un algoritmo no determinista que produce un límite superior para la complejidad de una fórmula dada en la jerarquía aritmética y la jerarquía analítica .
El algoritmo lleva el nombre de Alfred Tarski y Kazimierz Kuratowski .
Algoritmo
El algoritmo de Tarski-Kuratowski para la jerarquía aritmética consta de los siguientes pasos:
- Convierta la fórmula a la forma normal prenex . (Esta es la parte no determinista del algoritmo, ya que puede haber más de una forma normal prenex válida para la fórmula dada).
- Si la fórmula no contiene cuantificadores, está en y .
- De lo contrario, cuente el número de alternancias de cuantificadores; llamar a esto k .
- Si el primer cuantificador es ∃ , la fórmula está en.
- Si el primer cuantificador es ∀ , la fórmula está en.
Referencias
- Rogers, H. La teoría de las funciones recursivas y la computabilidad efectiva , MIT Press. ISBN 0-262-68052-1 ; ISBN 0-07-053522-1