Основы дискретной математики В.А. Осипова (552659), страница 15
Текст из файла (страница 15)
Имеется управляющая головка, которая может перемещаться вдоль ленты таким образом, что в каждый момент времени она находится в определенной ячейке ленты. Принято говорить, что машина воспринимает эту ячейку. Машина действует не непрерывно, а лишь в дискретные моменты времени. В зависимости от внутреннего состояния и от символа, записанного на воспринимаемой ячейке, в следующий момент времени машина переходит в новое внутреннее состояние (возможно, в то же самое), записывает новый символ в ту же ячейку (возможно, тот же самый) и либо сдвигает управляющую головку на одну клетку влево или вправо, либо оставляет ее на месте.
Если управляющая головка воспринимает самую правую (левую) ячейку, а машина по ходу работы должна сдвинуть головку в отсутствукяцую ячейку справа (слева), то она пристраивает недостающую ячейку. Попав в заключительное состояние, машина прекращает работу. Конфигурацией на ленте (или машинным словом) называется совокупность, образованная: 1)последовательностью а;„ а;„ ..., а;, символов, записанных в ячейках ленты, где а;, — символ, записанный в первой ячейке слева, а,, — символ, записанный во второй ячейке слева, и т. д. (любая такая последовательность называется словом в алфавите (2.8)); 2) состоянием внутренней памяти д", 3) номером й воспринимаемой ячейки.
2.3. Логика преликвтов а;„ а;, ... а;, , — а,, , ...а,, В М=(А,Я,П>, (2. П) в конфигурацию вида 82 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ Конфигурацию машины будем записывать так: Так как каждая машина имеет конечный алфавит и конечное число внутренних состояний, то из описания ее работы видно, что она может выполнять конечное число действий. Если машина, находясь во внутреннем состоянии д; и воспринимая ячейку с символом а, записывает к следующему моменту времени в эту ячейку символ а„переходит во внутреннее состояние д, и сдвигается по ленте, то говорят, что машина выполняет команду ЧФу + Част Б~ (2.10) где Я вЂ” сдвиг.
Вместо Я будем писать букву Ь, если сдвиг осуществляется влево, букву В, если сдвиг происходит вправо, и С, если головка остается на месте. При этом говорят, что машина переводит конфигурацию а;,... а;,— а;,„,,а;, где а;„..., а;, а. Ъ и а;,„„..., а; — произвольные слова в алфавите (2.8), в конфигурацию а;,... — а„а;,,... а;, а;,... а;,а, — '+' ... а; или а;,...а;,— а;,, ...а; в зависимости от того, какое значение Ъ принимает сдвиг в команде. Совокупность всех команд, которые может выполнить машина, называется ее программой. Программа машины должна содержать одну и только одну команду, начинающуюся словом аа, 1 = 1, ..., т, 1 = О, 1, ..., и. Каждая машина Тьюринга определяется своим алфавитом, состояниями внутренней памяти и программой. Чтобы полностью определить работу машины, надо указать ее конфигурацию для начального момента времени.
Будем считать, что в начальной конфигурации головка воспринимает самую правую непустую ячейку. Итак, машина Тьюринга есть, по определению, набор где А — внешний алфавит (2.8) с выделенным пустым символом ао, Я вЂ” алфавит внутренних состояний (2.9) с выделенными символами конечного и начального состояний до и д1, П— программа, т. е. конечная последовательность упорядоченных пятерок символов (2.10).
Если машина, начав работу с некоторым словом, записанным на ленте, придет в заключительное состояние, то она называется применимой к этому слову. Результатом ее работы считается слово, записанное на ленте в заключительном состоянии. Если же машина ни в какой момент времени не придет в заключительное состояние, то она называется не применимой к данному слову, и результат ее работы не определен.
Пример 2.22. Рассмотрим машину М1 с внешним алфавитом (О, !), двумя внутренними состояниями (до, д1) и програм- мой Машина М1 выполняет следующую операцию: к любому слову, состоящему из символов ~, она прибавляет еще один символ ~ и останавливается. Если, например, в начальном состоянии на ленте записано слово ~ ~ ~, то в процессе работы машины появятся следующие конфигурации: — начальная конфигурация (для краткости здесь н Ц1 далее в записи конфигурации опускаем все пустые символы, расположенные левее первого непустого и правее последнего непустого); ! ! !0 — следующая конфигурация; Д1 ~ ! ! ! — заключительная конфигурация.
Я1 Машина М1 применима к любому слову в алфавите (О, 0. Пример 2.23. (Удвоение слова.) Построим машину с алфавитом (О, ~), которая по любому слову в алфавите (и строит два таких слова; точнее, эта машина переводит конфигурацию вида 84 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ 85 2.3. Логика предикатов Можно указать несколько таких машин. Одна из них имеет следующую программу: в! †. й10 Чз ~ Д20 чз! дзΠ— + д40 Д4 ~ о50 Ч5 ! В| В~1 й80 — ~ й70В й21~ й,ос йз)Ь о40С й100Ь йэОТ, д4 ) С йе)С йз!С Ч7 ! ~ Д7 й70 -- йз С Чз ! ~ 98 0 » ОВ йз ?9 Ч9 ~ — + 99 1 «л о90 — ~ й20С д190 й,0.5 д19 ~ — й19 1 С Команда о90 — о20С зацикливает программу, и машина перерабатывает слово до тех пор, пока не придет в состояние оо, воспринимая при это»1 пустой символ.
Пусть М1 и М2 — две машины Тьюринга с общим алфавитом (аэ~ а11 " ав) И (ЧО) 91~ ". ~ амтв) ВнуТРЕННИЕ СОСТОЯНИЯ МИШИ- ны М1, (до, о1, ..., й1) — внутренние состояния машины М2. Композицией М машин М1 и М2 называется»зашина с алфавитом (ао, а1, ..., а„), внутренними состояниями (до, о1, ..., о О,в+1, ..., О +1) И ПрОГраММОй, ПОЛуЧаЮщсйея СЛЕдуЮщИМ Образом. Во всех командах машины М1 заменим заключительный символ до символом о +1, а остальные символы оставим без изменения.
Во всех командах машины М2 символ до оставим неизменным, а все остальные символы д, '(л = 1, ..., 1) заменим соответственно символами о,„+ь Совокупность всех команд машин М1 и М2, измененная указанным способом, и будет программой композиции М машин М1 и Мз. «Работа» машины М равносильна последовательной «работе» машин М1 и М2. А.
Тьюринг выдвинул следуюшую гипотезу. Тезис Тьюринга. Всякий интуитионьгй алгоритм может быть реализован с помощью некоторой машины Тьюринга. Выше уже приводились доводы в пользу этого тезиса. Как показывает опыт, любые действия, которые может выполнить вычислитель — человек, могут быть разложены в последовательность действий некоторой машины Тьюринга. С другой стороны, обладая точным формальным понятием алгоритма, можно доказать неразрешимость некоторых алгоритмических проблем. Задачи и упражнения 1. Будут ли следующие выражения формулами, и если это формулы, то какие переменные в них являются свободными, а какие связанными: а) (чх1)(Зх2)(гхз)А~ (х1, хз, хз, х4); б) (Чх1)А2 (х1, х2) Э (Зхз)А1 (х1, хз); в) (Зх1)(Зх2)(А2 (х1, хз)йАз (х2, х4))? 2. В интерпретации ОЛ =< М, ~ >, где М = Р(А), А — некоторое множество, Т" — соответствие, сопоставляющее предикатному символу Р(х, у) предикат х С у, записать, что: а) х — пересечение у и г; б) х — объединение у и г; в) х = 1о; г) х = А; д) х — дополнение у.
3. Доказать или опровергнуть следующие равносильности (формула В не содержит вхождений переменной х): а) (17х)(А(х) З В) = (Чх)А(х) З В; б) (Зх)(А(х) З В) = (Зх)А(х) З В; в) (Чх)(В З А(х)) = — В Э (эх)А(х); г) (Зх)(В э А(х)) ив з В з (Зх)А(х). 4. Доказать, что следующие формулы равносильны: а) (17х)(А(х)44С(х)) = (гх)А(х)ез(гх)С(х); 6) (Зх)(А(х) 1l С(х)) = (Зх)А(х) л/ (Зх)С(х). 5. Выполнимы ли следующие формулы: а) (1Ух)А) ~(х); б) (Зх)(1Уу)(А~~ ~(х, х)34- А~~ ~(х, у)); в) (Зх)А~~И(х) з А) ~ (у)? 6. Будут ли общезначимыми следующие формулы: а) (Зх)А(х) з А(у); б) А(х) 'З (Чу)А(д); в) (Зх)А(х) З (Чх)А(х); г) (Зх)(7'у)А(х, у) (Чу)(Зх)А(х, у)? 7.
Выполнимы ли следующие формулы: а) (Чх)(Зу)(А10(х) — А10(у)); б) (Зу)(Чх)(АОО(х) АОО(у))? 3.1. Комбвнаторнъ|е схемы Глава 3 основные понятия КОМБИНАТОРИКИ Комбинаторика — раздел математики, посвященный решению задач пересчета и перечисления элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Первые труды по комбинатарике, опубликованные в ХИ1 веке Б. Паскалем и П. Ферма и связанные с теорией азартных игр, составили основу теории вероятностей.
Камбинаторные методы применяются в математической статистике, теории случайных процессов, вычислительной математике и в различных прикладных областях. 3.1. Комбинаторные схемы 3.1.1. Правила суммы и произведения Пусть Х вЂ” конечное множество, состоящее их т элементов или, иначе, т-элементное множество.
Тогда говорят, что в этом случае объект нз Х можно выбрать т способами и пишут )Х( = т. Пусть У вЂ” конечное множество, ~У~ = и и Х й У = 9. Тогда )Х 0 У) = (Х(+ )У) = т+ и. Этот факт в комбинаторике называется правилом суммы, которое формулируется так: если произвольный объект из Х можно выбрать т способами, а произвольный объект из У вЂ” и способами, то выбор одного объекта либо из Х, либо из У можно осуществить т+ и способами (Х Г1 У = 9). Правило суммы можно обобщить на произвольное число множеств: ь й ~ ~Х; =~) ~Х;~, еслидлялюбыхг, «' «ф1 ХПУ=Ф.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
