Математическая логика. Шапорев С.Д (1019113), страница 54
Текст из файла (страница 54)
Зт ° итогошя программа предатавляет собой произведение четырех мшвии Тьюринга. Конечная команда дп =де. Нижнис индексы программ счита»отса следующим образом: последнЯЯ команда бс пРедыдУщей пРогРаммы ЯвлЯетсЯ пеРвой командой сюдующей, при зтом учитывастсл чиала букв внугреннею алфавита предыдущей машины Тьюринга (см иркмерм 3. 4, 5. 8 равд. 5.б). Для машины, реализующей 1„(х„хз,.,., т„)=х„„начальное слово г(,0!а 01*К..01ы01*"'..,01чО, конечное бсО!ыО.
Воапатьзуемся программой циклического сдвига Ц=ВБ В, д 01" О!е.,.О)чО=»О.О!н01,. О!" 01 О. еаг Гмма га Теория олго ипюв Если прилшнить ее (т — 1) раз, то получим слово 1«аО(чО(ь"'...О!ь01*Ч.,О!'" 'О. затем пРименнм к зтачУ словУ (л — 1) Рвз программу правого сдвига, получим О!чО)ч'Ч..О!ьО!л...г«еО!ч'0 Наконец, пРимсним (и — 1) Раз цРоизвелени» программ вычисления функции 0(х) и левога сдвиш (ОБ ), В результне будем иметь. Р„О!чО Итак, машина Тьюринга, правидьно вычисляюшаи функци1а «„"', такаваг (ц«"' БР « .
кд Б « 5.8.8. Пусть Р и П вЂ” машины Тьюринга, прашглы1о вычисляющие функции «(х) и 8(т) соответственно. Тогда «! = Пир правильно вычисляет Ь (см иочолозооочи5.8.7). 5.8.9. (х — у,х В у, а) х — у= Задача решается с помощью произведения О,х< у. машин Тьюринга.
Рассмотрим две програчмьг слозксния хе у (ю- дача 5.8.6) и усеченной разности х — 1 (сч прап« «О угад 5.6). Обозначим первую программу С, вторую УР1, Пусть начальное слово д,01 ОГО. После применения програчмы сложения получим конечное слово це01*"О, ано будет начявьиым двл вюрой программы, применив астору~о олин раз аулом иметь 1«с01 О.
Ясно, что использовав программу УР! 2у раз, получим требуемый результат. Итак, УР = С (УР1)г (УР1)г. Написанная программа не аамая коротка» и не единственная Очевидно, что згот зкс результат можно достигнуть и другими путями; б) «(х)о ~ — ~ = Х збп т 1 — х . Программу машины Тьюринга, реализуюжую зту функцию, можно составить, например из узкс рассмотренных раисе программ: !. Вычисление произведения 2.«по программе слозкения й'= 2т2т.. 1-2 (С) (задача 5.8.б); Ч и |Г. Ошеш, роше ия, ушеаим 2. Вычисление усеченной ршностн 2з — х УР !задача 5.8.9 (а))! 3.
Вычисление ф) нкции збпх Б (задача 5.8,3); 4. Вычисление суммьз 'г ябщ' (С) !задача 5.8.6). ! Таким абршам, машина Тьюринга, правильно вычнсляющвя функ Гх) цию ( — ~, имеет вид (С) УР 8.(С) . Конкретнып текст програм- )2~ мы можно написать при заданном значении х.
з.8.10. Если функция 8(х,у) правильно вычислнма, то существует программа Б, вычиолязашая зту функцию для любого х>0 и у>0. Пусть иачильное слово для 8(х, у) 9 01"01тО. Рассмотриы вычисление по опному аргументу х: В О!'0(ГГЛ 01' 7, О!'0(ш)„0!'О! 9„01'! ьс)0, где Гà — программа копирования, переводящая слово В 01*01'0 в слово 01"0)гбеО!'01, ГГ=Б'ВГВБ'ВГВ, à — удвоение: 8 01'О=з О 01*01"О, программа Г приведена атаби.!028 Итак, начало программы таково (табл.
10.6). Таа еда 1кб Далее вставляем команды, которые при 8 (х,))> 0 преобразовывали бы слово 01*01'9„0!гц') волово О!"Орнб,„О!г!"и . Гл в !О Т ркяалг кг ов Т йлв ! ° !йй Шродаишает Камаззда 0,0 — з л,„О зацикпивает програьзму и машина от состояния О!'0!'п„,О!"!"! преобразуется в состояние 01'01 0„,01Я!' 1 н т л Пушь по прошествии иесколькик циклов машина ггерепгла в сошояннс 01 01 д„,01ц"! и й(л!) = 0 Тогда поскольку !о = Л, та долягна выполняться команда д 0 — з д „!1, которая переведет машину в состояние 01*01'Ор„оО, Так как ! (л)=! па операции минимизации, та необлодимо пьигучш ь отвез — сс тояние О!я01 .
Это мпжно сделать так. Тяйллял !6.6 !о . ммц йом Я. Отвелз, Программа удвоения Гз дз 01 О ~ Чоа!' О! О. Комо змя д,а- дзю Ч51-здзо крлз Чза- дзЕ дз!.о дза д,о- д,а дз! -' Чзг д,а- д,г дта-з )з! дв) 9 деЕ дво — 9 дзЕ Ч91 з Ч9Е д,о-зд,о Через к, ннклов работы два -з дзЕ А (перепое нуля) пример 2, рвзл. Кб д,о)1*0 д,а!"Оа (ь'), (Б ), до- до Тиблиия 10.7 Зиячснле од,го о!'Ч,а о)* 'д,!о о!"лд,ао О! 05150 О)мад,! 0)*ло!Ч,о 01'ло)алто О)"ла!Од,! О)*лаа), О! о! лод,о! а!'лд,ааа) О)"'д,а!О! Од, О)*ОГО 15001 01 О д,а!"Оа) О 01'д„,аа!'О О)*д,а!"Оа д,о!*о! о д,а! О)'О Список литературы 1 Аламенко А. Н., Кучугюд А. М Лошчес ое программирошнис и У1ьп 1 Р СПбс БХВ-Петербург, 2003.
2 Акимов О Е. д скретнвя математика Логика, тру ы, графы. — Мл Лабора орфея Базовых Энаний, 2003 3. Гаврил в Г П, Сапоженко А. А Эадачи и упражнения по курсу дискретной математики. — М г Наука, 1992 4 ГннлнкннС. Г. Алгебралсгикн в гвдачш. — М Нау«а, 1972. 5 1орбатов В. А Основы дискретной математики — Мг Высша ша. 1986. 6 Дискрегнаа математика ° иатематические вопросы «ибернепгкиу Под ред. Яблонского С. В и Лупвнова О Б. — Мл Наука, 1974.
7 Гршсв КХ Л., Палютин Е. А Математическая логика — М. Наука,1987 8. Клпни С. Мвтематичсснвя логика — М. Мир, 1973. 9 Косовский Н К. Эш ептъг атсмапгчесшй логики и ее приложеггия к теории субре«урсивиых алгоршмов. — Л .. Ияд-во Л1 У, 1981 10 Косовский Н. К Основы сории тлсмснтариых алгоритмов — Л г Илмво Л1'У, 1987 11. Лавров И А., Мансимова Л. Л.
Задачи по теории множеств, матемшичесшй логике и теорн» алгоршмов — Мл Наука, 1984 12 Лихтврников Л. М., Сукачева Т. Г. Математическая логика. — СПб.. Лань, 1998. 13 Мальцев А. И. Алгебраические системы — М. Наука, И70.
14 Мальцев А. И. Алгоритмы и рекурсивные функции — М Науиа. 1986 15. МеншльсонЭ Введение в математ тоскую логику — М. Наука, М84 16. Нефедов В. Н, Осипова В. А. Курс дискретной машмамжи. — М. Итд во МАИ, 1992 17. Новиков П С.
Элементы матемшической логики -Мл Науке, 1973 18. Проблемы математической допек» Сложиосш алгоритмов п классы вы испнмых функций 1 Пол роя. Козмиллади В А. и Мучника А А.— М, Мир, 1970 19 Робинсон А Введение в тесрюо моделей и мспшашмвгику алшбры. — М. Наука, 1967. 20 Роллере Х Теория рсьурснвних функаий и тффскпшиа» вычислимесш. — М. Мир, 1972. 21 Судсшжгов С В., Овчиннншва Е В Элвис ты д с«ре ной ыаш а нки — М.„Новонбирс» ИНФА-М-НГТ1, ЗООЗ 22 Успенский В А. Лакшгн о вьюислимых функциях. — М..
Фихмаггиз, 1960 23 Успенский В. А. Машина Поста — М.. Наука, 1979. 24 Фрил а А., Меион П. т'сори и рос«т ро анис переключатечьны с ем. М Мир, 1978. 25 Чшь Ч., Л Р М шматическяя яопн а и авюматичесьое доказательство теорем. М; Науш, 1983. 26 Дг филд Д . Ма емшическа л гига — М. Наука, 1975 Предметный указатель Аксиома 4. 98 Акаиомапг закал апаш а 4 Аксна шический магов 93 Акаиочагичеснсс исчисление и узком смысл 135 полное в ° ира смыыс!36 Алш бра Вебб» 66 Ромера-Т а 66 Аспгригм 215 Кввйна 129 ал редтюшн !3! уиифнюшюг201 Автор п ическак р б а рвр шина и 2!г Алф т10,91,217 Алфван и й а ер239 Антецсленг 7 Ассоциативное на нс и 258 Аюзци ивнасзь юпьюн ц 12 «анъюнкции 12 А омна» )атомариы) фориула си шуры 150 Бвзгю 53 Буква 217 Вгл а бра 21 Булевы акгабр н марфиые22 В кторм ейно зависим 177 В арыф рчулар сшылеии 12 Вшш 74 Вх лфувщион л а зле ипв Вха деи юла форму у 14 Вы ад.
в ис юнни родню 190 из сошку и формул 102 свойссва 102 йырюкение 19 В зваюи5 абса о напшиае 5 лбаолк .о нос 5 проспи !эле. р се) 5 вшивое 5 Вм л74 Г Г рфизм 22 Дюйнаешр ивине выск зы 5 Д ) алнкннк14 Дыук и цеаочк» 258 Дерево вы ода 98 Д 3 юикг29 у 629 очный 134 укшарвын пю юв н 134 кар!вас ий 133 рна скина г «й)34 Цшъюн н нармальнаа ферма 27, 28 мив авьюи 37 мальиаа О н а и 39 тупика 39 Деэъюавгик б обобш ние 62 ю ра ю ви мюм нпгрны ЗО прави * р ЗО прели апю 143 зююн шрнав 29 Д "грбу д кп огласи льна к иьюиюии 12 Дистрнбу св канъв ции Дакввты апю ию л рева 98 «нс ен с аз 698 407 И Иынннюии 7 Убувйм ечый унвавунла 3 Злклю юн 7 ю ни ив й21 ленво и е лю ю«н «11 упюввый 2 ! К Кар»К рво40 К»лрм йе ню»234 »особым "и !4б «баас нейман» !50 й 40 Кыюеи ус ю у»люб р, 30 К »наи см 74 и ю анан 77 арюелслыю- о л вм ю» 74 в 74 К еакп ы«см Кю ИВ л Лы н некий »акое! ПО Л п псков унннюснне б М М « 12! Ме ол рме монин 13! М лл М о «сею М оюы ем П Юмвгний янюгюш Нсобкплимый пр н олнмости реле 363 Неполное клеьмевне 39 Непшрслагвевиое алов теис сек цнй 95 Нс ! Ииеорсчиа:ю е и ыпвтьавн й 135 Нпмер еве 239 Норма нан форме 159, 194 преЛварсвнея 159 щвлеарегная 4прн л н ! 195 скувюоюк 159 Пбрашю швзь 72 Обраш нне функпн 230 Опервюрг овну равенна 218 Рсекгнраевннв 218 сленга 218 0 рнпанас Щмл и» 143 ыпшзываннв 5 йукассвм а б! Паси 61 ОЩсн нссрв си цч не 50 сршь вмете 50 Первы форму.
а расшюгю ня 12 Псременню вушюг енп 24 ро щца нв 94 свотшлнзв 146 ° вязвнвю !46 ушссгюннв фн пмн 24 Полопаю 91, 239 Полшшювка сипгатурь 200 200 Полфор у.а!О,Ю. НП !82 Полны мы Ьаюгочвевыу Же юки а 45 Полно скл вв вне39 Пс л с возраагающая 4убыаающан! 177 ся лшцюся к чисву 177 фу ла гены!Иная 177 Посылка 7 ПРВВНВО' !Р ]з л е 184 ввеленивл ъюмкция !87 юслсння пмгинюцн 187 веления кюнтара всюбщнаагн 188 вселения квмпарв аущесгвования 188 авеленин юнъю гпи 187 ввеленн р нанн 187 вова95 вывола пачиоле ня вмскюываннй 96 «Ре мешммвмамзвнн р л е нык псрсмспн 186 ср ма авантора черю атрннвнне 158 перссиповкп 188 повсгвнавкп 184 рююанненн» поаыяок ПО рвсшпрсня 188 авалов противоречию 188 авюыванив везнтором 186, 189 силлогнзма 189 соелпнсиия пое ла 110 сокрвщ нн 188 ул сына лизькшкцнн 187 улвленнн нмпликапнп 187 удаления квмпар бшиссгн 188 улавсин рвсущеепюванпя 188 ул е няконъюнкннн187 улвлення юриаанн П8 уцшчеинв 188 ПР внес ам ло у и ое97 правила ввслецп внюшишшн 96 пращ!по ваше и м акация 96 р в о еаеннв кеньюнкпнн 96 прсвшю вселения огрннанн 96 прзвнво контр пя 100 р .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
