WikiDer > Алгоритм Тарского – Куратовского

В теория вычислимости и математическая логика то Алгоритм Тарского – Куратовского это недетерминированный алгоритм что дает верхняя граница для сложности данной формулы в арифметическая иерархия и аналитическая иерархия.

Алгоритм назван в честь Альфред Тарский и Казимеж Куратовски.

Алгоритм

Алгоритм Тарского – Куратовского для арифметической иерархии состоит из следующих шагов:

1. Преобразуйте формулу в пренекс нормальная форма. (Это недетерминированная часть алгоритма, поскольку для данной формулы может быть несколько допустимых предваренных нормальных форм.)
2. Если формула не содержит кванторов, она находится в ${ displaystyle Sigma _ {0} ^ {0}}$ и ${ displaystyle Pi _ {0} ^ {0}}$.
3. В противном случае подсчитайте количество чередований кванторов; назови это k.
4. Если первый квантификатор ∃, формула находится в ${ Displaystyle Sigma _ {к + 1} ^ {0}}$.
5. Если первый квантор ∀, формула находится в ${ Displaystyle Pi _ {к + 1} ^ {0}}$.

использованная литература

• Роджерс, Х. Теория рекурсивных функций и эффективной вычислимости, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1

Эта математическая логика-связанная статья является заглушка. Вы можете помочь Википедии расширяя это. v т е