В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 4

Это являетсяоснованием для предположения о том, что для всех процедур, претендующихназываться алгоритмическими, существует (при подходящем кодировании)реализующая их машина Тьюринга.Даннное предположение носит названиетезиса Тьюринга. Данный тезис доказать нельзя, поскольку здесь используетсяинтуитивное понятие алгоритма. Подтверждением тезису является15математическая практика, а также то, что описание алгоритма в любой другойалгоритмической модели может быть сведено к описанию его в виде машиныТьюринга. Однако принятие тезиса Тьюринга позволяет истолковыватьутверждения о несуществовании машин Тьюринга для решения конкретныхзадач как утверждения о несуществовании алгоритмов вообще.16§ 3 Машины произвольного доступа ивычислимые функции10 ) . Опишем другую алгоритмическую модель, представляющую собойидеализированную ЭВМ и предложенную в 70-х годах с целью моделированияреальных вычислительных машин и анализа сложности вычислений.Машина произвольного доступа (МПД) состоит из бесконечного числарегистров R1 ,R2 , R3 ,.....

, в каждом из которых может быть записанонатуральное число из N0. Пусть rn есть число, записанное в регистре Rn, n ∈ N .Состоянием машины или конфигурацией назовем последовательность чисел (r1,r2,r3,..... ). Функционирование машины заключается в изменении конфигурацийпутем выполнения команд в порядке их написания.Машина имеет следующие типы команд:1) Команды обнуления. Для всякого n ∈ N имеется команда Z(n).Действие команды Z(n) заключается в замене содержимого регистра Rn на 0.Содержимое других регистров не меняется.

Обозначение действия Z(n)-rn := 0.2) Команды прибавления единицы. Для всякого n ∈ N имеется командаS(n). Действие команды S(n) заключается в увеличении содержимого регистраRn. на 1. Содержимое других регистров не меняется. Обозначение действияS(n) - rn :=rn+13) Команды переадресации. Для всех m, n ∈ N имеется команда T(m,n).Действие команды T(m,n) заключается в замене содержимого регистра Rnчислом rn - хранящимся в регистре Rm .

Содержимое других регистров неменяется (включая и Rm ) .Обозначение действияT(m,n)-rn:=rm или rm → Rn .4) Команды условного перехода. Для всяких m, n , q ∈ N имеется командаJ ( m, n , q ) . Действие этой команды заключается в следующем:а) Сравнивается содержимое регистров Rm и Rn ,затем :б) Если rn =rm , то МПД переходит к выполнению команды с номером(идентификатором) q в списке команд.в) Если rm ≠ rn , то МПД переходит к выполнению следующей команды всписке команд .Конечная, упорядоченная последовательность команд данных типовсоставляет програму МПД.Пусть зафиксирована начальная конфигурация K0 = ( a1 , a 2 ,...) чисел ипрограмма P = I1I2 ...Is .

Тогда однозначно определена последовательностьконфигугурацийK0 , K1 , K2 ,..., Kt , Kt + 1 ,...(1)K1 есть конфигурация, полученная из конфигурации K0 применениемкоманды I1 . Пусть на некотором шаге выполнена команда I t и полученаконфигурация Kt .

Тогда, если I t не есть команда условного перехода,где17Kt +1 есть конфигурация, полученная из Ktприменением команды It +1 . Если I t есть команда условного перехода, т.еI t = J ( m, n , q ) , то Kt +1 получается из Kt применением команды I q , если rn=rm в конфигурации Kt и команды It +1 , если rm ≠ rn . Последовательность (1)будет обозначаться также P( a1 , a 2 ,...) или P( K0 ) и называтьсяследующая конфигурациявычислением.Вычисление (работа машины) останавли -вается, если:а) Выполнена последняя команда, т.е.t=s и I t не есть команда условногоперехода.б) Если I t = J ( m, n , q ) , rn =rm - в конфигурации Kt и q > s .в) Если I t = J ( m, n, q) , rm ≠ rn в конфигурации Kt и t=s.Если вычисление остановилось) то последова -тельность ( r1 , r2 ,...)содержимого регистров R1 , R2 ,...

называется заключительной конфигурацией.Если последовательность (1) конечна, то говорим ,что МПД применима кначальной конфигурацииP( K0 ) ↓ .K0 = ( a1 , a 2 ,...)и пишемP(a1 ,a2 ,...) ↓ илиВ противном случае говорим, что МПД неприменима к начальнойконфигурации K0 = ( a1 , a 2 ,...) и пишем P( a1 , a 2 ,...) ↑ или P( K0 ) ↑ .Будем рассматривать только такие начальные конфигурации, в которыхимеется конечное число элементов, отличных от нуля.

Будем писать( a1 , a 2 ,..., a n ) вместо (a1 , a2 ,..., an ,0,...) для таких конфигураций. Ясно,Kt будет содержать конечное числе отличныхот нуля элементов, если этим свойством обладает конфигурация K0 .что для любого t конфигурацияТеперь условимся, что понимать под вычислением функций на МПД.f : N0n → N0 . Пусть P = I1I2 ...Is фиксированная программа. Пусть a1 ,..., a n ,b ∈ N0 . Будем говорить, чтовычисление дает результат b , если P( a1 , a 2 ,...) ↓ и в заключительнойконфигурации r1=b.Обозначение : P( a1 , a 2 ,...) ↓ b .Будем говорить, что программа Р вычисляет функцию f , если∀a1 ,..., an ,b ∈ N0 выполнимо P(a1 , a2 ,...) ↓ b ⇔ { f определена на( a1 , a 2 ,..., a n ) и f (a1 , a2 ,..., an ) = b .Назовем функцию f вычислимой (на МПД), если существует программа Р, которая вычисляет f . Класс вычислимых функций обозначим Е.Рассматриваем частичныеfтипа18Заметим, что любая программа Р для любого n ≥ 1 на начальныхконфигурациях вида K0 = ( a1 , a 2 ,..., a n ,0,...) определяет n -местную частичную функциюf pn ( x1 ,...., xn )такую, что∀a1 ,..., an ∈ N0b , если P( a1 ,..., a n ) ↓ и P( a1 ,..., a n ) ↓ bf pn ( a1 ,..., a n ) = , если P( a1 ,..., a n ) ↑ неопpеделенаЯсно, что разные программы могут вычислять одну и ту же функцию.2 0 ) Распространим понятие алгоритмической вычисли-мости наnпредикаты, заданные на множестве N0 .

Пусть π( x1 ,...., xn ) произвольныйтакой предикат. Определим характеристическую функцию χ π предиката πсоотношением:1 , если π( x1 ,...., xn ) = и (истина )χ π ( x1 ,...., xn ) = 0 , если π( x1 ,...., xn ) = л ( ложь)Будем называть предикат π разрешимым, если его характеристическаяфункция вычислима, и неразрешиным в противном случае.Это понятие соответствует вопросу о наличии алгоритма для проверкасвойства, определяемого предикатом.Теперь распространим понятие вычислимости на функции, отличные отрассматриваемого типа.nПусть D - некоторое множество, и f : D → D функция n переменных.Зафиксируем эффективное кодирование множества D натуральными числамиN0 , т.е. эада-дим инъективную функцию α:D → N0 .

Пусть α −1 - ееnобратная. Тогда для функции f : D → D можно однозначно определитьn∗функцию f : N0 → N0 , гдеf ∗ = αfα − 1 или f ∗ (a1 , a2 ,..., an ) = α ( f (α − 1 (a1 ),..., α − 1 (an ))∀a1 ,..., an ∈ N0Будем называть функцию f вычислимой тогда и только тогда, когда∗функция f вычислима.В качестве примера укажем кодирование множества целых чисел Ζ .Определим 2 z , если z ≥ 0α( z) = − (2 z + 1), если z < 0191m , если m ÷ етно2α( z) = 1− ( m + 1) , если m не ÷ етно 2Таким образом, можно считать определенным понятие вычислимостицелочисленных функций. Позднее будут рассмотрены эффективные кодированияи других областей.30 ) Рассмотрим примеры вычислимых функций (на МПД).а) функция f ( x + y) = x + y .

Эта функция может быть вычисленаследующей программойI1I2I3I4J (3,2,5)S(1)P:S( 3)J (111,,)Данная программа прибавляет 1 к x до тех пор пока r3 не станет равным y.Работу программн P можно представить блок-схемой:Начало=(x,y,0,0,...)k=0 в R3y=k?( r3 = r2 ? )Даостановr1=x+yнетr1:=r1+1k:=k+1(r3:=r3+1)б)Функцияf ( x) = {x,если x-четное и неопределена2если x-нечетноеЭта функция может быть представлена программой P:I1J (1,2,6)20I2I3S( 3)S( 2)S( 2)J (111,,)T( 31,)I4I1I6Данная программа прибавляет 1 к r3 и 2 к r2 до тех пор,пока r2 не станетравным x , тогда r3 даст результат.

Работу программы можно представить блоксхемой:Начало:=(x,0,0,...)k=0 в R3x=2k?(r1 = r2 ? )Даостановk → R1нетk:=k+1(r3:=r3+1)40 )2k:=2k+2r2:=r2+2Поскольку доказательства вычислимости конкретных функцийсвязаны с предъявлением конкретных программ, их вычисляющих, то следуетввести некоторые соглашения о составлении и записи про-грамм.

Аналогичнокомпозиции машин Тьюринга можно ввести компо- зицию программ МПД.Пусть P = I1I2 ...Is . Будем говорить , что Р имеет стандартный вид, еслидля всякой команды условного переходаJ ( m, n , q )выполнимоq ≤ s + 1.P и P′ назовем эквивалентными, если они определяютnnодни и те же n -местные функции, т.е. f P = f P ′ для всех n>0.Утверждение Для всякой программы P существует эквивалентная ейпрограмма стандартного вида P′ .Две программыДок-во.21P = I1I2 ...Is .Тогда определим P′ = I1′ I2′ ... I s′ , где ∀ k ∈1...s I k , если I k не есть пpогpамма условного пеpехода, если I k = J (m, n, q ) и q ≤ s + 1I k′ =  I k J ( m, n, q + 1), если I k = J (m, n, q и q > s + 1ПустьЯсно, чтоP′ удовлетворяет нужным требованиям.Утв док-но.P и Q стандартного вида. Образуемпрограмму PQ = I1 I2 ...

I s I s+1 .... I s+ t ,где P = I1I2 ...Is ,Q = I s+1 I s+2 ... I s+ t с учетом нумерации, т.е. команды J ( m, n , q ) замененына J ( m, n, s + q ) . Тогда результат действия программы P Q совпадает срезультатом вычисления по программе P , к которому применена программаQ.Заметим, что для всякой программы P существует минимальноенатуральное число r ( P) , такое, что для всех m, n ∈ N , входящих в командыиз P , т.е.

S( n ) , Z( n) , T( m, n) , J ( m, n , q ) выполнено m,n< r ( P) .Это число иногда называют ширина, ранг программы P .Смысл числа r ( P) состоит в том, что регистры Rt с t > r ( P) в ходевычисления по программе P не будут менять свое содержание и не будутвлиять на содержимое регистров R1 , R2 ,..., Rr , поэтому их можноПусть теперь даны две программыиспользовать для других вычислений.Заметим также, что можно организовывать вычисление, используяпрограмму P , в случае, когда входы программы находятся в регистрахRl , Rl ,..., Rl , а результат заносится в Rl .

Пусть P вычисляет f в12nстандартном понимании вычислимости. Тогда программаT( l1 ,1)...............P[ l1 ,..., ln → l] :T(ln , n)Z( n + 1)...............Z( r( P))PT(1, l )будет вычислять f ( xl , xl ,..., xl ) и результат запишет в Rl . (Далееn12считаем, что регистры Rl , Rl ,..., Rl отличны от R1 ,..., Rn .n1222Данную программу обозначимfP[ l1 ,..., ln → l] .Приведем еще пример вычислимой функции.в) Функция f ( x, y) = xy .Пусть Н - программа, вычисляющая функцию x+y (пример а) ).

Тогда( x, y) = xy вычисляется программойJ ( 2 ,3, p )S( 3)H[ 1,4 → 5]T(5,4 )J(1,1,1)I p : T(5,1)P:Программаx0 = 0P вычисляет xy по правилу :  xy = x( y − 1) + xРабота программы проходит в соответствии со следующей блок-схемой:Начало:=(x,y,0,0,...)k=0 в R3y=k?(r2 = r3 ? )k:=k+1Даостановr5 → R1нет+ r4 → R5R5 → R4по H: r1Как следует из изложенно, язык програм МПД содержит основныепроцедуры языков програмирования и позволяет устраивать ком-позицию(соединение ) программ и использовать програмны в качестве подпрограмдругих програм. Это является основаниен для пред-положения о том, чтовведенный класс вычислимых функций в точности отвечает классуалгоритмически вычислимых функций. Данное предположение называетсятезисом Черча (для МПД).

Также как и тезис Тьюринга данный тезис доказать23нельзя, однако принятие его позволяет истолковывать утверждения онесушествовании МПД для решения конкретных задач как утверждения онесушествовании алгоритмов вообще.24§ 4.Частично рекурсивные функции и их вычислимость10 ) Приведем еще один класс вычислимыхфукций, пред-ложенный в ЗОх годах (Гедель, Клини, Черч) в качестве уточнения понятия алгоритма - классчастично рекурсивных функций. Данный класс определяется путем указаниякон-кретных исходных функций и фиксированного множества операцийполучения новых функций из заданных.