Математическая логика. Шапорев С.Д (1019113), страница 37
Текст из файла (страница 37)
Это определение, если перейти ог словарных функций к представляющим их числовым функциям, выглядит так (,., Г (хохл,...„тя,О) = б(хох„...,х„) 15.5.2) У(хохл,....х„, руч-г)=1г (хилз„...хну,~(хохл,....хь, г)) г =! 2,,р Предсгаыяющвя функция 1 расписывается следующим образам: 2'(хох„...,х„,з) = Честь С аттемам ннял гин дед 5 (хих„...,х„, т) = Операция словарной минимизации проводится аналогично, хотя и более сложным способом; вместо одной операции минимизации рассматривается минимизация по кюкдой букве алфавита а,. уеорема 5 5 Длв того чтобы зяданнаи в алфавите А словарная функцна г (п,,пз,...,пн) была частично рекурсивной, необходимо и доствточпо, чтобы опа могла быть получена «з простейшнз словврныя функций Я,О, 1;„коиечныьз чисяом операций суперпозквни, словарной рекурсии н словарной миннмизяпни.
Пример 1, В алфавите А = (А, В,С, О) рассмотрим словарную функт 3 н цию г(п,,п ) и определим рекурснвно второй аргумент а . Пусть функцил определяется следующим образом: г(пи Л) = С(п, ), г (ам 33 А) = Н, (п,,33, Е(по 33)), Е(а,,33 В)= На(п~,33,Р(ацб)), Е(ап33 С)= Н (а3,33,Е(ппВ)), г(а,,33 О)= не(а„33,Р(пцр)).
Н, (п,33, у) = а33у, Н,(аф,у)=лабу, Пусть, кроме того, 6(п) = пВ и Нз(п В.у) = п33(3у. Н, (п,33,у) = п33уу. и"(а,,Л)=п,В, Р(п,,В А)=пфг(ао(3), Тогда г (ацр В)= п3п3ВР(п„33), г (а,, (3 С) = а3333г (а и В), Е(пи 33 Р) = агрг (п3,33)г (а„33). Тлела д Т я юкоркгмав 243 При таком определении может сложиться впечатление, что количества функций Н, недостаточно для построения функции Г(а„аз) при ягобом 33, ведь Г(аг,33 А )= Н (пп(1Г(гг„33)) и В(ао(3) неизвестно. Однако если (3 = Л, то можно найзи Г(поЯ,) дла всех букв алфавита А, т.
к. Г(цг,дг)= Н,(п„Л,Р(пг,Л))=Нг(п»,ЛАЗ(о!)). Затем взяв за (»=»3, иы можем определить функцию Р для (3=ЛЯ, итд, для всеь слов произвольной длины. Пусть, например, а, = РЯС, 33 = ВС. Вычислим только Р(аг,(3 О) = Е(ОАС,ВСО). Ддя этою необьолимо определить несколько промсжугочиык значений этой функции Г(а,,Л)= ОЯСВ, с(п,, В)= Г(аоЛВ)= Н,(поЛ,Р(а,,Л))= ОАСОАСОАСВ, Р(п,, ВС) = Н,(п,, В, Г(пп В)) = ОЯСВВОЯ СОЯСОЯСВ, Г(пи В СО) = =Н»(амВС,Г(ппВС))= ОАСВСОАСВВОАСОАСОАСВОАСВВОАСО. АСОАСВ и г д. Найдем все представляющие функции. 6(п) = пВ, б(х)= с(й(Кх)), где К— первоначальная нумерация атфавитных символов Л= Я,В С,О, р =4, 1к~ з 3 В(х)=-с(пВ)=2 р +с(а) р' = 2+с(а) р=2т4х.
Итак, й(х) = 2+ 4х — функциа, представляю»ива словарнщо функцию 0(п). Нг(а33,у)= а331, /3 (ху,х) = с(Н (Кх,Ку,Кя)) = = с(п333)= с(у)+ рс()3)ь р с(а)= р х+ ру+ я = 1бх+ 4у+ х; Нз(а33у)=оп(31, Лг(ху,х)=с(Нз(КхКуКх))=с(па331)= с(Т)+ рс(В)»- + Р с(п)+ р с(п) = (р + р )х+ ру+ т = ЗОх+ 4 у+ х ! Н(а 33 у) = пЯЬ, йз (х у х) = с(о(333у) = с(у)+ рс(33)» рэс(33)+ р с(п) = р х г (р» р')у+ +- =б4х+20у+з; НЯа (11)=а(УТр, Ь»(х,ух)=с(а33Т3)=с(у)+ +рс(у)ь р с(33)ь р с(п)= р я+ р у+(1+ р)с= 64х+!бу+5з. Перейлем теперь ог формул (5 5.!) к формулам 15.5.2) для предсгавляющик функций Т'(х,О) = б(х), Г(х 4 у»- г ) = Ь, (х, у, Г (х, у)) г' = 1 2,3,4.
Часа Г Ылгемагиче лая лепна Вычислим несколько значений представляющих функций 7(00)=8(0)= 2+4 0=2, Г(10)=6, Г(20)=10. г = 1, зг(1 4 0+ 1) = г(11) = 6>(1 О, Г(! 0)) = 15 (1 О 6) = 22, з = 2, Г (1 4 О+ 2) = г(!2) = ~ (1 О, Г(1 0)) = бз (1 О 6) = 86, 1=3,Г(1 4 Ос 3)=г(13)=ба(1 О, г (10))фб (106)= 70, г=4,!(!4 Ос4)=7(14)фб (!О,Д(10))фь (106)=94, г = 1 /(1 4. 1+ 1) = 7 (!5) = 6 (117 (1 1)) = Ь (11 22) = 40, э =27(14 1+2)= /(1 6)=Аз(11/(11))=~(1 ! 22)=106, г = 3 /(1 4 1ч 3) = Г(1 7) =.
Ьз (1 1 Д(11)) = бз (!! 22) =! 06, !=4,/(1 4 !ч-4)=/(18)=Ьс(11,/(1 !))=64(1122)=190 у=1, Проверим совпадение номеров слов и значений представляющих функций Пусть п = А, Н(А) = АВ, с(АВ) = 2 +! . 4 = 6, с(А) = 1, 8(1) = 2+ 4 1 = 6. То же наблюдается, например, щи функции Н, Н,(с,07)=Н,(А,Л,АВ)=ААВ, с(ААВ)=2 )+1 4+1 16=22, с(А)=1, с(Л)=0, с(АВ)=б, 6,(106)=22 ит.д, 5.6. Машины Тьюринга Тезис Ч«рча нельзя доказать, т. к. он связывает нестрогое матеьгатическое понятие интуитивно вычислимой функции со строгим математическим понятием частично рекурсивной функции.
Но а поддержку этого тезиса впослслствни другими авторами были приведены очень веские доводы. В 1936 г. Тьюрингом был определен еще один класс интуитивна вычислимых функций и сфорьгуяирован тезис Тьюринга, эквивалентный тезису Черча В результате попыток разложить интуитивно известмые нам вычислительные процедуры иа элементарные операции построена математическая модеяь, называемая машиной Тьюризгю. Повторения элементарньзх операций, опредеяенных в этой малине, достаточно лля проведения любого возможного вычисления.
Ог чсловека-вычислителя эта машина отличается двум» ссо. бенностями: О она не ошибются, т е. она без всяких отклонений выполняю правила, установленные для се работы; О оиа снабжена потенциальна бесконечной памятью. Это значит, что хотя в каждый момент количество наив~ленной ею информации конечно, для Гл е д теор»»кто»испо» 24» этого нет никакой верхней грани. В качестве накопителя рассматривается бесконечная лента. Машина Тьюринга включает: 1. Внешний алфавит А = (ае,ао...,а„), т.
е. конечное множество символов. В этом алфавите (в символах этого алфавита) инфорчаци» вводится в машину Ма»зина перерабатывает введенную информапию в новую. 2. Внутренний алфавш С, Р, Е отсУгствУют. Символы дм((ы...,ди выР»ж»ют конечное число состояний машины, причем д, — начально«состояние, дт — стопссстоянне. 3. бесконечную в обе стороны ленту, представляющую память машины. Э га память разбита н» клетки.
В «ажлую «летку может быль записана только одна буква. аз — пустая югш ка, она всегда может появиться при движении вправо или влево, есяи закончится санно исходной информации птп)пт,л„. 4. Управляюшую головку. Она передвигается вдоль ленты и могкет останавлиеатьсн напротив какой-либо клетки и воспринимать записанный там символ исходного слова.
В одном такте работы машины управляющая головка ьюжет сдвигаться только на олпу клетку или оставатьен на месте. Работа машины складывается из тактов, по ходу которых происходит преобразование начальной информации в промелгуточную В ка ~естес началь'дой информации иа ленту можно подать любую конечную систечу знаков внешнего алфавита, расставленную произвольным образом по яченкам. При этом работа ьгашины Тьюринга может заканчиаатьс» так: П после конечиога числа тактов машина оеганавливаетс» в ((„сссю»нии.
При этом на ленте оказыв» гся переработанная информация В этом случае говорят, что машина применима к начальной информации 1, и перерабатывает ее в резульгнруюшую информацию (»; бт машина никогда не останавливасюя ( е переходит в ((ь ссгояние) В этом случае машина не при»мнима к начальной информации (, Чв ь! Магам тече яа л еш В кзхгдом такте работы машина Тьюринга действует по единой функцио. К иальной схеме, которая имеет вид а,д, ~ а, С д,, где аз,аз ц А, Р д.,д, ц зз и и, — буква на ленте, обозреваемая управляющей головкой на данном такте, ц — текущее ссатоянис машины иа данном тв общем случае не Г-м н нс ) -ьз ) такте.
На каждом такте функциональной схемой вырабатывается команда, состо»- ща» из т)мх элемента» тправая часть формуяы).' 1. Буква внешнего алфавит» а,, нв шцорую заменяегс» обозреваемая буква а, 2. Адрес внешней памяти и Лополннзельиьш действия для выполнения на следующсмтвкте )),7„С,Р иаи Е. 3. Слепующсс состояние машины. Формирование правой часги фуикциоиатьной схемы происходит по командам, совокупность которых образует программу манзины Тьюринга. Программа прелсшвляею» в виде двумерной таблицы ттабл. 5.6.1), называемой мысли»гасой 1йуикцисиазьлсй схезгой, а каждой клетке которой записываются отдельные команды. Таблице 5.б.! Глав В Те ри г сигм Работа машины Тьюринга полнгютью опредьшяется ее программой.
Две машины Тьюринга с общей функциональной схемой идентичны, разные мапшны имеют разные программьь т. е. различные функцнональныс схемы. В качестве символов алфавита могут быть нс только буквы, часто используется, например. символ ~ Говорят, что непуспю слово и в алфавите Л воспринимштс» машиной в стандартном полозкснни, сеян оно записано в посчедовательных «веткак ленты, все другие клетки лусии.
и машина обозревает крайшою «яшку справа из тех, в которых записи ю слово ц. Рассмотрим сначала несколько примеров с полным алфавитом. Пусть начальная конфигурация имеет вид п,п,аг аз и,, а машина Тьюринга управлястая функциональной схемой, представленной в табл 5.6 2 Тпбл Ге 5.6.2 Так «ак управляющей головкой обозревается буква а„а машина находится в состоянии фы при этом пусть вырабатывается комвнда азу й, т. е, головка сдвигается влево, аз заменяется иа Пз, состояние гй меняется на й, г. е.
получается конфигурация а„а, аз атас. Следугощая конфигурация булет и Шкой — ав а, п,а,п„третья — а„а, и, а,пр, четвертая — п,п, а, и,а,, па- в таа — аьа, ат азль Таким обРазом, мы пРишли в начальное ссстоаиис. ПРоцесс работы машины начал повторяться, и, следовательно, коне нзый результат не может быль получен, т, с данная машина Тьюринга не применима к исходной информации. Чвсш Г. Ыеюмвпкесин логчю Пусть теперь для той же машимы начыьная информация нмеш вид ар а, а„ е Тогда, действуя аналогично, придем к следующим конфигурациям: леа, а, аеа, а, ое. Так как машина перешла а иачыьное состояние, то слово а,п,— о результат ее работы, н машина применима к исходной информации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
