Неразрешимость логики первого порядка

Вообще, говорят, что проблема распознавания какого-либо свойства разрешима, если существует допускающий механическое вычисление тест (вычислимая, или эффективная, процедура), который, будучи

Неразрешимость логики первого порядка

Курсовой проект

Математика и статистика

Другие курсовые по предмету

Математика и статистика

Сдать работу со 100% гаранией
цией связывания квантором существования переменной xi в n-местном предикате P(x1, x2,…, xn) называется операция, в результате которой получается n-1-местный предикат xi P(x1, x2,…, xi-1, xi+1,…, xn), который при значениях x1 = a1, …, xi-1 = ai-1, xi-1 = ai-1, …, xn = an истинен, если при некотором значении xi = ai высказывание P(a1, a2,…, an) истинно.

Вхождение какой-либо переменной в формулу, называется свободным, если оно не входит в область действия никакого квантора по этой переменной.

Формулами логики предикатов являются:

всякая нульместная предикатная переменная;

P(n) (x1, x2,…, xn), где P(n) n-местная предикатная переменная, а x1, x2,…, xn свободные переменные;

F, где F формула;

F1 F2, F1 F2, F1 ↔ F2, F1 → F2, где F1 и F2 формулы, в которых общие переменные являются одновременно свободными или одновременно связанными;

xi P(x1, x2,…, xi-1, xi+1,…, xn) и xi P(x1, x2,…, xi-1, xi+1,…, xn), где P(x1, x2,…, xn) формула, в которой xi свободная переменная

Определение истинности формул алгебры предикатов вводится с помощью интерпретации. В классическом случае интерпретация определяется следующими данными

1) предметная область;

2) всякой предметной константе ставится в соответствие некоторый предмет, определенный в области;

3) каждому пропозициональному символу ставится в соответствие некоторое значение 1 (истина) или 0 (ложь);

4) каждому предикатному символу языка ставится в соответствие некоторая характеристическая функция.

Классификация формул:

Формула называется

а) выполнимой (опровержимой) на множестве М, если существует ее истинная (ложная) интерпретация на этом множестве;

б) тождественно-истинной (тождественно-ложной) на множестве М, если любая ее интерпретации на этом на этом множестве истина (ложна);

в) выполнимой (опровержимой), если существует предметная область, на которой она выполнима (опровержима);

г) общезначимой (противоречием), если на любой предметной области она тождественно-истинная (тождественно-ложная).

Множеством истинности предиката P(x1, x2,…, xn), заданного на множестве M1ЧM2Ч…ЧMn, называется совокупность всех упорядоченных систем (a1, a2,… an), в которых a1 е M1 a2 е M2,…, an е Mn, таких, что данный предикат обращается в истинное высказывание Р(a1, a2,… an) при подстановке x1 = a1 x2 = a2,…, xn = an. Обозначается P+.

Два n-местных предиката Р(x1, x2,…, xn) и Q(x1, x2,…, xn), заданных на одном и том же множестве M1ЧM2Ч…ЧMn называются равносильными, если набор предметов a1 е M1 a2 е M2,…, an е Mn превращает первый предикат в истинное высказывание Р(a1, a2,… an) тогда же, когда этот набор предметов превращает второй предикат в истинное. Переход от предиката Р(x1, x2,…, xn) к равносильному ему предикату Q(x1, x2,…, xn) называется равносильным преобразованием первого.

Предикат Р(x1, x2,…, xn), заданный на множестве M1ЧM2Ч…ЧMn называется следствием предиката Q(x1, x2,…, xn), если он превращается в истинное высказывание на всех тех наборах значений предметных переменных из соответствующих множеств, на которых в истинное высказывание превращается предикат Q(x1, x2,…, xn).

 

3. Понятие машины Тьюринга

 

Машина Тьюринга есть математическая (воображаемая) машина, а не машина физическая. Она есть такой же математический объект, как функция, производная, интеграл, группа и т.д. И так же как и другие математические понятия, понятие машины Тьюринга отражает объективную реальность, моделирует некие реальные процессы.

Машины Тьюринга это совокупность следующих объектов

  1. внешний алфавит A={a0, a1, …, an};
  2. внутренний алфавит Q={q1, q2,…, qm} множество состояний;
  3. множество управляющих символов {П, Л, С}
  4. бесконечная в обе стороны лента, разделённая на ячейки, в каждую из которых в любой дискретный момент времени может быть записан только один символ из алфавита А;
  5. управляющее устройство, способное находиться в одном из множества состояний

Символом пустой ячейки является буква внешнего алфавита а0.

Среди состояний выделяются два начальное q1, находясь в котором машина начинает работать, и заключительное (или состояние остановки) q0, попав в которое машина останавливается.

Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы алфавита A. Управляющее устройство работает согласно командам, которые имеют следующий вид

 

qi aj → ap X qk

 

Запись означает следующее: если управляющее устройство находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то (1) в ячейку вместо aj записывается ap, (2) машина переходит к обозрению следующей правой ячейки от той, которая обозревалась только что, если Х= П, или к обозрению следующей левой ячейки, если Х= Л, или же продолжает обозревать ту же ячейку ленты, если Х= С, (3) управляющее устройство переходит в состояние qk.

Поскольку работа машины, по условию, полностью определяется ее состоянием q, в данный момент и содержимым а обозреваемой в этот момент ячейки, то для каждой возможной конфигурации qi aj имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Поэтому программа машины Тьюринга с внешним алфавитом A={a0, a1, …, an} и внутренним Q={q1, q2,…, qm} содержит не более m (n+ 1) команд.

Словом в алфавите А или в алфавите Q, или в алфавите A Q называется любая последовательность букв соответствующего алфавита. Под k-ой конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу k-того шага (или слово в алфавите А, записанное на ленту к началу k-того шага), с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина. Имеют смысл лишь конечные конфигурации, т.е. такие, в которых все ячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигурация называется заключительной, если состояние, в котором при этом находится машина, заключительное.

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

Будем говорить, что непустое слово б в алфавите А\ {а0} = {a1, …, an} воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю слева или крайнюю справа ячейку из тех, в которых записано слово б. Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q1 (соответственно в состоянии остановки q0).

Если обработка слова б переводит машину Тьюринга в заключительное состояние, то говорят, что она применима к б, в противном случае не применима к б (машина работает бесконечно)

Рассмотрим пример:

Дана машина Тьюринга с внешним алфавитом А = {0, 1} (здесь 0 символ пустой ячейки), алфавитом внутренних состояний Q = {q0, q1, q2} и со следующей функциональной схемой (программой):

 

q1 0 → 1 Л q2;

q1 1 → 0 С q2;

q2 0 → 0 П q0;

q2 1 → 1 С q1;

 

Данную программу можно записать с помощью таблицы

 

01q11 Л q20 С q2q20 П q01 С q1

Посмотрим, в какое слово переработает эта машина слово 110, исходя из начального положения:

 

q1

…110…

На первом шаге действует команда: q1 0 → 1 Л q2 (управляющее устройство находится в состоянии q1, а в обозреваемой ячейке записана буква 0, в ячейку вместо 0 записывается 1, головка сдвигается влево, управляющее устройство переходит в состояние q2), в результате на машине создается следующая конфигурация:

 

q2

…111…

На втором шаге действует команда: q2 1 → 1С q1 и на машине создается конфигурация:

 

q1

…111…Третий шаг обусловлен командой: q1 1 → 0 С q2. В результате нее создается конфигурация:

q2

…101…

Наконец, после выполнения команды q2 0 → 0 П q0 создается конфигурация

 

q0

…101…

Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки q0.

Таким образом, исходное слово 110 переработано машиной в слово 101.

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

11q10 => 1 q211 => 1q111 => 1q201 => 10q01

Машина Тьюринга не что иное, как некоторое правило (алгоритм) для преобразования слов алфавита A Q, т.е. конфигураций. Таким образом,

Похожие работы

< 1 2 3 4 5 > >>