Алгоритм Тарского – Куратовского - Tarski–Kuratowski algorithm

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

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

Алгоритм

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

  1. Преобразуйте формулу в пренекс нормальная форма. (Это недетерминированная часть алгоритма, поскольку для данной формулы может быть несколько допустимых предваренных нормальных форм.)
  2. Если формула не содержит кванторов, она находится в и .
  3. В противном случае подсчитайте количество чередований кванторов; назови это k.
  4. Если первый квантификатор , формула находится в .
  5. Если первый квантор , формула находится в .

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

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