знайти один хід, при якому гарантує виграшну стратегію для Б. Якщо поточний хід у Ч, то при всіх варіантах повинна знайти виграшну стратегію для Б. Машина визначає наявність виграшної стратегії для Б на самому початку гри і для її роботи нам потрібно використовувати всю послідовність машин . Але кожна з цих машин використовує невелику (полиномиально обмежену) пам'ять, так що весь процес вимагатиме лише полиномиально обмеженою пам'яті.
Нехай є машина , що розпізнає входження слова в мову на поліноміальної пам'яті. По-перше, зауважимо, що обчислення на пам'яті безглуздо проводити довше, ніж час (все почне повторюватися після того, як ми вичерпаємо всі стани нашої системи, а їх не більше ніж , де - відповідно безліч станів керуючого пристрою та алфавіт розглянутої МТ). Тому можна вважати без обмеження спільності, що час роботи машини обмежено , де .
Щоб було простіше описувати гру, вимагатимемо, щоб після завершення обчислення МТ зберігала без змін досягнутий стан.
Гра полягає в наступному. Білі стверджують, що відповідь на вхідному слові дорівнює "так", а чорні хочуть це перевірити. Білі своєю першою ходом декларують стан машини (рядок, записана на стрічці, положення читаючої головки, стан керуючого пристрою) після тактів. Чорні своїм ходом вибирають один із проміжків: від початку до -го такту або від -го такту до кінця. Білі декларують стан в середині цього проміжку. Далі все повторюється: Ч вибирає одну з половинок, Б декларує стан в середині обраної половинки і т.д.
Гра закінчується, коли довжина проміжку стає рівною 1. Результат визначається так: для обох кінців цього проміжку в процесі гри були названі стану . Якщо стан правого кінця виходить зі стану лівого кінця за один такт роботи , то Б виграли, інакше виграли Ч.
Якщо відповідь на слові дійсно "так", то білим потрібно весь час говорити правду, це гарантує їм виграш .
Якщо відповідь на слові - "ні", то за будь ході білих на одному з проміжків (або на обох) буде міститися помилка. Ч повинен вказуват...
