Конспект установочных лекций по комплексному курсу Информатика, Теория информации




Проблема выполнимости для булевских выражений - часть 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.


Содержание  Назад  Вперед