Математическая логика. Шапорев С.Д (1019113), страница 38
Текст из файла (страница 38)
Видно, чю понятие машины Тьюринга возникает в результате прямой попытки разложить интуитивно нзиестнме нам вмчислительнче процедуры нв элементарные операции. Тьюринг привел ряд доводов в полиу того, что повторения его элементарных операций было бч достаточно дл» проведения любого возможного вычисления. Если данное состояние опнсмыегся машинным словом М, то машинное слово, опнсьгвающес следу«ощы состояние машины, будет обозначаться через М1 1. 2!алае аналогично М !н«= ( М 1)) ', г = О 12 .. Переход машины Тьюринга из начшшного в последующие иютояни» изображается в аиде цепочки слов М(- М!1(- Мй)(- .... Чтобы описывать работу машины Тьюринга более удобным образом, текущие состояния машины пишут не внизу алфавита, а перед обозрсвымой ячейкой.
Например, пусть А = 10„11 Д = )де,д„ут) де — символ остановки, а программа состоит из команд д Π†« д«Е, д 0 †« дг1, д 1 †« д,Я, дз! -« дз)! н начальная конфигурация д,11. Тогда д,11 ! — 1д,! ( — 1!д,О ( — 110д,О ! — 110д 1, где 0 — символ пустой ячейки ленты ь«ашины. Если же начальная конфигурация д,!01, то дз!01 )- 1д 01 )- 1д 11. Такич образом, каждая машина Тьюринга с произвольными алфавитами А и Гк' и зааанной программой перерабатывает з-ку сяов а„пз,...,а,, записаннмх в алфавите А, в слово О, если машина применима к начальной информации, и машина не применима к 3-кс слов а„цг,...,а,, если вмрюкение (слово) после ее работы имеет неопределенное значение. Словарная функция называется вмчиолимой по Тьюрингу, если она вмчислича на подходящей ман«иие Тьюринга. Теореме 5.б.
Все словарные функции, вычислимые ио Тьюрннгу, ввлв. ются частично рекурснвныии. Тезис Тчорякао. Любав выч пеликан функции вычислнча по Тьюрнигу. Глл Л. Г Лк т ишан гео Тесрсми 5.7. Длн кшкдой частично рекурсивной словарной функции Р(цоаэ,...,п,), опРеделеиной иа онюкУппостн слов какого-иибУдь алфавита Ут„аэ,...,а„у, сУп«сствУет машина ТыоРипга с символами 1. Од») -)((о; 8.
1» «-! ) ( дэ) О; 9. 1» + ! ! дэ! ) О; 1О. 1» +( д,) ( ! О; 11. 1» + д,( ) ! ! О; 12. (» дэ;-( ! ! ! О; 2,оод~ 4!1!О; з. о! д, ь ) ) ! о; 4. О! + дт! ) ! О, 5. 1» 4! дэ)!О, б. 1» +! ! дэ/ О; 7. 1» +) ) ) дто, гз. Од) 4!!)! о; 14, д«Р» 4) ! ) ) О; аоа„...,а„и подходнщими внутренннмн соствиинимн, котора» правнлыю вычисляет функцию Г. Рассмотрим несколько машин Тьюриигж преобразующих машинные слова одного заданного вида в машинные слова другого заданного вида. Программы машины будем писать в столбец Пример 1. Пусть на легпу подается два числа, заданных набором палочек, например 2 и 3. Нужно сложить зти числа.
Обозначим символ сложениЯ "+". Итак, А=«асио,Усу, аа — начальное состоЯние Найти программу, которая будучи примененной к слову и, =1» ) +) ( ! О,давалабы в результате сумму чиссл2 и З,т. с, слово пэ=(»))!)О. Программы для одного приь«сра могут быть разными, т. е. могут реализовивщъся на разных машинах Тьюринга. Опишем процесс работы машины лля решения этой залачи. Пусть в начальный момент обозревается самая левая палочка. Ее нужно сдвинуть вправо, ыинуя все палочки и знак '- до тех пор, пока не будет достигнута пустая клетка. В эту пустую клетку вписывается первая палочка. Зкшм нуэкно вернуться за второй палочкой и ес перенести вправо аналогичным образом. После этой процедуры нужно вернуться к знаку +, стереть его и остановиться.
Изобразим все такты машины в виде соответствующих конфигураций. Часть Г, Маммагичеглеялсгика 3О. ОЦ)()(О. Подчеркнугьг состояния, получаемые навей командой. Этот процесс позеоляет записать алгоритм в виде следующей цепочки команд д,~ — «01265, дз! -ь~ Яд',, д,+ — «е!!д«, д,ое~ Сд«, д«! — «( !д,, дч- — «еАды до-«0«дд, д+ — «ОСдз или еш» более компактно в виде двумерной таблицы (табл. 5.6.3). Тевлина 5.65 Пример 2.
Введем следующие обозначения; 1' = 11...1, 0* = 00...0 и Р 0 =1 =Л. Составим програь«му "пареное нуяя": е а д,оо!'0=«д«01 "ОО. В левой колонке табл. 5.64 будем располагать программу, в правой — результат ее преобразования исходного слова. Исходное слово пусть будет доо!"О. 15. Од«( +) ! ) ( 0; 16. Оодз +! ! ! ! 0; рд о+д,! ! ! ! о; 18. 0 ь1 д«( ) ( О; Вд о+( ( д,) ( о; 20 О+(!(дз(0; г1. о -( ) ( ) д,о г г. Ое()(! д) о; 23.
О+) ! ) дз! ) 0; 26. 0,-) ( д,Д ( ) о; 25, Ое) дД ()) О; 26. О+ дз( ( ) ) ( 0; 27. Од, е! ( ) ( ) 0; 28. д,ос! ( ! ! ! 0; 29. Од, е ) ) ( ) ! 0; Тлаеа д Теория алто нпюе гщ Теалщгя 5.6.4 Пример 3. Левый сдвиг О! "60~ д 01'О, ! 1рограмьза эюго примера очень короткая и абсолютно очевидна» !табл, 5.6.5) Тявллкя 5.6.5 Во втором и третьем п римерах в текстах программ опущен символ С. Пример 4. Правый сдвиг: д 01'0 ~ 01'де О. Программа агой машины получается из предыдущей программы заменой символа 1.
на Л. Пример 5. Транспознция. 01'д,01'0 ~ 01'д,01'О. Сггачыга переведем слово О!д010 в слово 01'д100 При у >0 зго постигается очевидной программой, записанной в табл. 5.6 6 А ньгенно сначала по программе правого сдвига из исходного слова 01'д 01'0 получаем слово 01'ОР6,0.Заем выполняемсгщдующиекоманды. аз ззм Ческе (. Магвмапмасквя лагика Тайяаца 5.6,6 г(тсбьг получить слово О1'6,01гОО и при 5 =0,добавим команду Таблица 5.6.6 (проб ежеаае 0 01*6, 2ЧЮ(у В О) 60- 60 Теперь иа поделана 1' перебрасьпмем один сними 1 в промежуток между двум» пссяедними нулями.
Зго дсстигасгсл следующеб программой: Тайлица 5.6 б (пргдаеэсеег г 21 Главвб Г о яалг рипюв Этот кусок программы работает прн х> О, у > О. Чтобы тот лес резульшт получился н прн у = О, добавляем к записанной программе еще приказы: Таблице хйб)лр Сш е еЗ) Теперь запнклнвае» програмьзу приказами. Тиблие)и 5.6.6 ( рсдшохем е 4) Если .з — ! > О, то слово 01*лбе!'010 псреработаекя в слово О!' 'рт!г01!О. Если лге х — 2 > О, то пронесс дальнейшей переработки даст слово 01' 'рг Р01110 и т, д.
Через х циклов получим слово ОО,ПО!"О. тебеици 5,6.6 (иро)с хесе е 5) Пример 6. Комбинируя между собой примеры 2, 3, 4 и 5, легко получать машины, выполняющие более шюжные преобразования слов. Твю например, применяя двшкды попряд программу правого сдвига !см. пример 4), получаем машину, вынолняюшую двойной перенос; О,ОГО! "0 ~ 01 "01 "г)ьО. Часп ) Мл маги геснаялмлка Пример 7. Программа циклического сдвига получщтая применением друг за другом программы траиспозиции, левого сдвига и опять транс- позиции !примеры 5 и 3): О!'01~0, 01'0 ~ 01'рз01'01гО.
Достаточно научиться строить машины, правилыю вычисляющие простейшие функции и функции, возникающие из правильно вычислимых функций с помощью операций суперпозицни, примитивной рекурсии и минимизации. Пример 8. Вмчислить функцию 0(х)=0, т.е, 9,01'О~бз00 ч !табл.
5.б.7). Тлалицв 5,6, т сдвига Л(х)= хе 1, Пример 9. Вычислить оператор т. е. 9,0!' ~ 9,01ьч !табл. 5.8.8). Тей вкл 5гйа Глв Л, Г наалгс игмсв Пример 1й. Составим программу функции усеченной разности х-'! а табл. 5.6.9, если начальное и конечное слово заданы следующим образом, д,О!'О~д 01 00 Тигмвле 5.Е,У Пример 11. Построить машину Тьюринга, рсаяизующую алгоритм вычислени» функции 7(п) = и + 2 в десятичной системе счисления. В этом примере за внешний алфавит необходичо взять А =)пэ,0,1,2,3,4,5,8,7,8,9).
Нуагно, чтобы машина, находясь в стандартном сосгоинии, заменяла последнюю цифру чисяа И (сели эта цифра меньше 8) цифрой, на две единицы большей, и переходила в стоп-состояние. Есаи последняя цифра числа л равна 8, то се нужно заменить на О и перейти влево в новое состояние д, которое добавило бы к следующему разряду единицу. Аналогично, если последив» цифра числа равна 9, то ее нужно заменить па единицу и перейти влево в состояние д,. Например, пусть 7)59), тогда начальнав «онфигурацив а,5д,9п, (ввиду того, что символ О входит в алфавит А в качостве рабочего сиьгвола в эюм примере, в отличие от всех предыдущих, содержимое пустой ячейки машины Тьюринга обозначено через аэ), а сана программа имеет вид, представленный в табл. 5.б.10. Ч см Ь Маюмвтлеесиы полиса реял на дато Для всех возможных цифр программа выглядит следующим образом (табл.
5.6.1 1). тавлмяе Дфы Пример 12. Построить машину Тьюринга, правильно вычисляюшую функцию (1, хи О, вбп(х) = ~ Пусть исходное состояние (6 01110 . Тогда програыма может быль такой (табл. 5.6,12). теллллл Хбтя Гл в 5. Те влпригмов 257 6.7.
Неразрешимые алгоритмические проблемы Введение понятия машины Тьюринга уточняет понятие алгоритма и указывает цуть решения клковйго массовой проблемы. Однако машина Тьюринга бывасг неприьынима к начальной информации (исходному слову алфавита) Та же ситуация повторяется относительно некоторых задач, для решения козорых не удасзся создшь машины Тьюринга. Один из первых результатов такого типа получен Чсрчеьз в 1936 г. Он квсаезся проблемы распознавания выводимости в математической логике 1. Аксиоматический метод в математике заключается в тоьз, что все теорсьзы данной теории получаются посредством формально-логического вывода из нескольких аксиом, принимаемых в данной теории без доквзательсгв. Например, в математической логике шзисывштся специальный язык формул, позволяющий любое предлозкение математической теории эщ~исать в виде вполне определенной формулы, а процесс логического вывода из посылки А следствия В может бьггь представлен в виде процесса формальных преобразований исходной формулы.
Ого достигается путем использования логического исчисления, в котором указана сисюма допустимых преобразований, изображающих эяементариьы щтты логического умозаключения, из которых скяадывается любой, сколь угодно сложный формально-яогический вывод. Вопрос о логической вывадимссти следствия В из посылки А является вопросом о существовании дедуктивная цепочки, ведущей от формулы А к формуле В.
В связи с этим возникает проблема распознавания выводи- мости.' существует ли для двух формул А и В делуктивнвя цепочка, велущал ст А к В или нет Решение этой проблемы понимается в смысле вопроса а существовании алгоритма, дающею ответ при любых А и В. Черчеи эта проблема была решена отрицательно Теорема 5 5 йлеорема Черта), Проблема распознавания выволимости алгоритмически неразрешима. 2.
Проблема распознавания самоприменимости — вторая проблема, положительное решение которой не найдено ло сих пор. Ее суть заключается в следующем Программу машины Тьюринга можно закодировать каким- либо определенным шифром На ленте машины можно изобразить ее же собственный шифр, записанный в алфавите машины Здесь как и в случае обычной программы возможны два случая ° машина применима к своему шифру, т.е. она перерабатывает этот шифр и после конечного числа тактов останавливается; Часть !.
Мапгмэпые каяяшкха машина неприменима к своему шифру, т. е. машина никогда не пере- ходит в стоп-состояние. Таким сбразоьг, сами ммпины !или нх шифры) разбиваются на два кзасса: самопримеиимых и несачоприменимых тьюринговых машин. Проблема заключается в следующем; как по любому заданному шифру установить, к какому классу отнгюится машина, зашифрованная им, к классу саыоприменимых или несамоприченимых. Теоремп 5.9.
Проблема рвсиознанаин» самопрнмеинмости алгернтми. чески нерюреигима. 3. Проблема эквивалентности слов для ассопиагивных исчислений. Рассмотрим некоторый алфавит А =)а,б,с,...) и множество сяов в этом алфавите. Будем рассматривать преобразования одних слов в другие с помощью некоторых допустимых подстановок ц-ь !), где а и !) — два слова в том же алфавите А . Если слово у содержит а как подслово, например п,ац,а,ц, то возможны следующие подстановки: п,разцгп .
ц,аазазб, п,))азат!). Яссояеоыквеым кгчкгяекяем называется совокупиоеп всех слов в некотором алфавите вместе с какой-нибудь конечной системой допустимых оодстаиовок. Для задания ассоциативного исчисления достаточно задать соответствующиб алфавит и систему подстановок. Если слово Я может быть преобразовано в слово 5 путем однократного применения опредюенной подстановки, то Я и 5 называются смюкнымн словами. Последовательность слав Я„Яз,...,Я„пЯ„таких, что все пары слов Я,,Я, „г =1,2, .,и — 1 являются смежныьги, называется дедукяг иной ггелочкой, ведущей от слова А', к слову Аю Если существует цепочка, ведущая от слова Я к слову 5, то Я и 5 называются эквивалентными; Я-5, Для каждого ассоциативного исчисления возникает своя специыьная проблема эквивалентности слов: для любых двух сяов в данном исчислении требуеюя узнать, эквивалентны они или нет. Теорема Я 10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
