Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Проблема выполнимости для булевских выражений - часть 2
Пусть {bi}0£ i £р(n) - последовательность конфигураций Т-машины М, которая соответствует последовательности вычислений машины М, причем пусть каждое из n состоит в точности из р(n)+1 символов (р(n) символов ленты, и один символ - состояние машины). Если вычисление заканчивается раньше, чем будут выполнены р(n) шагов, то повторим конфигурацию конечного состояния нужное число раз, так что имеется ровно р(n)+1 конфигураций. Основные идеи аргументации по сводимости таковы.
· Каждое вычисление машины М состоит из последовательности самое большее р(n)+1 конфигураций. Эта последовательность может быть представлена (р(n)+1)^2 знаками, если мы также и состояния закодируем знаками. Обратим внимание: за р(n) шагов машина М может рассмотреть самое большее р(n) ячеек ленты.
· Для каждого знака z в представлении последовательности конфигураций введем булевскую переменную Ci,z (1£ i £ (р(n)+1)^2), которая принимает значение true точно тогда, когда i-й знак есть z.
· Образуется булевское выражение, дающее значение true точно тогда, когда соответствующая последовательность соответствует принимающему вычислению.
· Формула может быть порождена из входного слова для М с затратой времени О(р(n)^2).
Свяжем состояние, знак под головкой и номер возможного для применения правила с одним новым знаком. Пусть теперь
# bо # b1— # bр(n)
есть последовательность вычислений, где #
b0 # -
это последовательность знаков с их номерами 0, 1, ..., р(n), р(n)+1 и т.д., а самый последний знак имеет номер (р(n)+1)^ причем этот последний знак есть # либо вновь введенный знак.
Для каждого знака z из алфавита Т-машины М, который может встретиться в таком вычислении, и для каждого числа i, 0£ i < (p(n)+l)^2 породим булевскую переменную Ci,z, которая задает, является ли i-й знак в последовательности конфигураций знаком z.
