Теорема Сэвича

Пусть . Тогда существует недетерминированная машина Тьюринга, распознающая этот язык.

Рассмотрим вспомогательную функцию , вычисляющую возможность перехода из конфигурации  в конфигурацию  за не более, чем  переходов:

 Reach(I, J, k):
   if (k = 0)
     return (I  J) or (I = J)
   // запись (I  J) означает возможность перехода МТ из конфигурации I в конфигурацию J за один шаг
   else
     for (Y) // перебор промежуточных конфигураций
       if Reach(I, Y, k-1) and Reach(Y, J, k-1)
         return true
   return false

Эта функция имеет глубину рекурсии , на каждом уровне рекурсии использует  памяти для хранения текущих конфигураций.

Рассмотрим машину Тьюринга , распознающую язык . Эта машина может иметь  конфигураций. Объясняется это следующим образом. Пусть  имеет  состояний и  символов ленточного алфавита. Количество различных строчек, которые могут появиться на рабочей ленте . Головка на входной ленте может быть в одной из  позиций и в одной из  на рабочей ленте. Таким образом, общее количество всех возможных конфигураций не превышает .

Рассмотрим функцию, которая по заданному слову  проверяет его принадлежность языку :

 Check(x, L):
   for (T) // перебор конфигураций, которые содержат допускающие состояния
     if Reach(S, T, )
       return true
   return false

Если слово принадлежит языку, то оно будет допущено, так как будут рассмотрены все возможные пути допуска. Это обеспечивается указанной нам глубиной рекурсии для функции . И если слово не допускается за  шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено. В итоге функция  имеет глубину рекурсии , на каждом уровне рекурсии используется  памяти. Тогда всего эта функция использует  памяти.