86384 (612733), страница 2
Текст из файла (страница 2)
Вхождение какой-либо переменной в формулу, называется свободным, если оно не входит в область действия никакого квантора по этой переменной.
Формулами логики предикатов являются:
– всякая нульместная предикатная переменная;
– 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. Понятие машины Тьюринга
Машина Тьюринга есть математическая (воображаемая) машина, а не машина физическая. Она есть такой же математический объект, как функция, производная, интеграл, группа и т.д. И так же как и другие математические понятия, понятие машины Тьюринга отражает объективную реальность, моделирует некие реальные процессы.
Машины Тьюринга – это совокупность следующих объектов
-
внешний алфавит A={a0, a1, …, an};
-
внутренний алфавит Q={q1, q2,…, qm} – множество состояний;
-
множество управляющих символов {П, Л, С}
-
бесконечная в обе стороны лента, разделённая на ячейки, в каждую из которых в любой дискретный момент времени может быть записан только один символ из алфавита А;
-
управляющее устройство, способное находиться в одном из множества состояний
Символом пустой ячейки является буква внешнего алфавита а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;
Данную программу можно записать с помощью таблицы
| 0 | 1 | |
| q1 | 1 Л q2 | 0 С q2 |
| q2 | 0 П q0 | 1 С q1 |
Посмотрим, в какое слово переработает эта машина слово 110, исходя из начального положения:
q1
| … | 1 | 1 | 0 | … |
На первом шаге действует команда: q1 0 → 1 Л q2 (управляющее устройство находится в состоянии q1, а в обозреваемой ячейке записана буква 0, в ячейку вместо 0 записывается 1, головка сдвигается влево, управляющее устройство переходит в состояние q2), в результате на машине создается следующая конфигурация:
q2
| … | 1 | 1 | 1 | … |
На втором шаге действует команда: q2 1 → 1С q1 и на машине создается конфигурация:
q1
| … | 1 | 1 | 1 | … |
Третий шаг обусловлен командой: q1 1 → 0 С q2. В результате нее создается конфигурация:
q2
| … | 1 | 0 | 1 | … |
Наконец, после выполнения команды q2 0 → 0 П q0 создается конфигурация
q0
| … | 1 | 0 | 1 | … |
Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки q0.
Таким образом, исходное слово 110 переработано машиной в слово 101.
Полученную последовательность конфигураций можно записать более коротким способом (содержимое обозреваемой ячейки записано справа от состояния, в котором находится в данный момент машина):
11q10 => 1 q211 => 1q111 => 1q201 => 10q01
Машина Тьюринга – не что иное, как некоторое правило (алгоритм) для преобразования слов алфавита A Q, т.е. конфигураций. Таким образом, для определения машины Тьюринга нужно задать ее внешний и внутренний алфавиты, программу и указать, какие из символов обозначают пустую ячейку и заключительное состояние.
4. Доказательство неразрешимости проблемы остановки
Проблема остановки машины Тьюринга – это проблема построения такого алгоритма, который мог бы определить закончится или нет вычисление по некоторой задаче. Оказывается, что в общем случае такой алгоритм нельзя построить в принципе, то есть невозможно найти алгоритм, позволяющий по произвольной машине Тьюринга Т и произвольной ее начальной конфигурации qiaj определить придет ли машина Т в заключительное состояние q0, если начнет работу в этой конфигурации.
Если машина Т, запущенная в начальной конфигурации qiaj, останавливается (т.е. попадает в заключительное состояние) через конечное число шагов, то она называется самоприменимой, в противном случае – несамоприменимой.
Теорема.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
