Ш.И._Галиев_МЛ_и_ТА_2004

Если ate машина Т не изменяет буквы Sd, а читающая головка движется, например, вправо по команде q&iRqn то по подстановке

qtSt\Si~*StitiA(SieA) алгоретмавиз(6.2) получки

Яено, ч'Ги н любоуу другому 'гъкту машины Т будет соотвсгст-

исключеиием того, что при преобразовании с помощью В в олове

Однако а конце преобразования алгоритм В своей подстановкой уберетзгу лишнюю букву. Итак,

VPвЛ :ЛгЖР)«В(Г%

Следствие 6,1 Всякая частично вычислимая (вычислн«аа)| по Тьюрингу функция является частично вычислимой (вычиыгкмой)|

ко Маркову функцией	j
Доким •е;1ьство Пу: ь функция Цх ,¾..1	л,) вычи.лима сю

Тьюрингу и •е вычисляет м нииа Тьюринга Т с алфавите» А, содержащнм 1 и *. Это знача г, чгп цля любых на1уралы ых чисел K h - X найдутся такиг елова R\ и R- (возможно, пустые) в алфавите

{S|}, НТО At	(in*:- X ) = i?i/(i|,*2.-,k„)Ri. В		г.илу д казанной
теореык 6.5 сушестауег и рмальиый алгоритм в			над ,	вполне
эквивалентна й откосталы о		А алгоритму А ц,	т.е. для	любил
нмуральны* чисел ii, .....к, имеем:
А гЖ \Л з ~ ) | а В « Г V A ) ) * Я,				(S3)
Для то п, чтобы функдня была частично вычислимо				по Мар-
Rosy, нужт	чтобы сущктаоаал нормальный алгоритм			котнрый
преобразует	(¾.¾... X )	/(t|,*j,...,A:„). Наш	же нормальный

алгоритм В прообразует (^Д 2,...Д„) в R* Надо как-

то изменить алгоритм, чтобы он убкрал слова R] и Кг. Пусть Bj - нормальный алгоритм над {I,*,.?}}, стирающий осе вхождении S( перед первым вхождением 1 или * во всяком слове в алфавите {I ,*Д}. Такой алгоритмможно задатьсхемой:

В = <«*->**

Пусть В2- нормальный алгоритм над {1ЛЗД, который стирает все -вхождения5™после последнего вхождении 1или * во всяком слове

в алфавите	Например, 5: можно задать схемок:
Построим композицию алгоритмов В. В, и Bt:		По

доказанной теореме 6.1 алгоритм Сваляется нормальным алгоритмом, как композиция нормальных алгоритмов. Для любых натуральных

£ f e , V , y ) = ЛТл( М г.--Л))s Я,J l k ^ Z x h .

гдей| и Ri -	некоторые слом в {Soj.Далее
в,	!{k„kv ,.,k„ % ;

Отсюда видно, что/есть вычислимая по Маркову функция, ее вычисляет нормальный алгоритм С.

Аналогичным образом проводится доказательства для частично вычислимых функций.

Теорема 6.6 (обратная теореме 6.5), Пусть В - нормальный алгоритм з алфавита А, не содержащем S,, к 3. Тогда существует такая

машина	Гьюпинга Т, что алгоритм Тьюриигп А т<v(So 8]				в алфавите
^u{Sj.6}	обладает следующий свойспюм: дли			всякого слова		Р
в А алгоригч А?		.^применил к Р тогда и только тогдо, когда
к 1‘ применим алгоритм В и при этом A r				jj (Р)	имеет вид
S{,B(P )$Q , гдег иmидныеиеотривтотьньв числа, a .¾1 = .¾¾.. ¾ •
Согласно сформулированной			еорече значения алгоритмов В и
А 5- Ли[ув5]формально различны, так			акдля машины Тыоринга S0есть
символ пустого квадрата, а в нор* альноч олгорише 8					4 - буква,
равноправная с любой другой букво			. Но с точностью до символов So,
которое	могут стоять	справа и ci ева от результирующего слова.
алгоритмы В и A		j вполне	„ и . ™ , Т	„	ч —	«
Следствие 6.2 ■		Всякая час ично вычислимая (вычислимая)!

по Маркову функция частично оычис лима (вычислима) по Тьюриигу.

Доказательство следствия сразу получается из теоремы 6.6 и определения вычислимой по Тьюрингу функции.

Из теорем 6.5 и 6.6 видим, что различные подходы к понятию алгоритмов Тьюринга и Маркова (нормальные алгоритмы] по сущест­ ву эквивалентны, т.е. то, что можно осуществить с помощью нормаль­ ного алгоритма, можно осуществить с помощью машины Тьюринга, и наоборот.

Есть еще многоленточные машины Тьюринга и другие модифи­ кации (варианты) подхода к понятию алгоритма, такие как машины Поста, машины Минского и др. Однако детальный анали? показывает, что все зги понятия равносильны в том смысле, что то, что можно осуществить (вычислил) с помощью одной HI чтих машин, молко сделать (вычислить) с помощью машннь! Тьюринга, а следовательно, и с помощью нормального алгоригха, и наоборот

243

§ 11. Осиоввая гипотеза теории алгоритмов (принцип нормализацив шш ныне Чёрча)

С целью дать строгое (с некоторых позиций) определение алгоритм? были введены понятия нормального алгоригьш и алго­ ритма (машын) Тьюринга. Было выяснено, что оба эти подхода приводят к равносильным понятиям алгоритма, т.е. то, что можно осуществить с помощью одного и этих алгоритмов, можно осу­ ществить с помощью другого, и наоборот. Естественно задаться вопросом: насколько общими являются эти схемы вычислений с помощью нормального алгоритма или Алгоритма Тьюринга и насколько эти понятии близки к интуитивному понятию любого алгоритма? На эти вопросы современная теория алгоритмов предлагаетответи виде следующей гипотезы:

Для всякого алгоритма В е алфавите А существует вполне эквивалентный ему нормальный алгоритм Снад^4,т.е.

V? в А'. В{Р) = С{Р).

Иначе эта гипотеза формулируется так:

Всякий алгоритм может быть задан посредством некоюрой машины Тьюринга и реализован в этой машине.

Эту гипотезу называют осноеноИ гипотезах или основным тсзисом теории алгоритмов, или пршщином нормелиюцт, или

тезисом Черча.

Ясно, что эта гипотеза не носит xipaicrcpa тгореми и не мижет быть, следовательно, доказана, ибо в нее аходит нестрогое (неопре­ деленное) понятие алгоритма Уверенность п истинности гипотезы основана, главным обрагюм, на опыте. Известие алгоритмы, которые

были придуманы в течение многих тысячелетий, могут быть заданы посредством нормального алгоритма (машины Тьюриига). Имеются я другие соображения, подтверждающие правильность основкпД гипотезы. В § 6данной главы были рассмотрены различные операции над нормальными алгоритмами (аналогичные операции можно рас­ смотреть и для алгоритмов (.машин) Тьюринга), причем каждый раз оказывалось, что результирующий алгоритм снова является нормаль-

Эаметим, что внутри самой теории алгоригаов основная гипо­ теза не применяется. В теоряи алгоритмов исследуется нормальный алгоритм, машина Тьюринга, машины ГТост и т.п., устанавливается criif, между ними ит.д. Основная гипотеза только утверждает (посту­ лирует) универсальность понятии нормального алгоритма. Иначе мокко сказать, что основной тезис применяет»! в теории алгоритмов ТОЛ1.КО в рекламных целях: "Любой алгоритм можно представить как нормальныйалгоритм".

Основную гипотезу можно рассматривать как уточнение поня­ тия любого алгоритма через более специальное, но строгое понятие нормального алгоритма (машиныТьюринга),

Никогда rte бывает большихдел без больших трудностей.

§ 12. Проблема алгоритмической неразрешимости

Пид массовой проблемны будем понимать бесконечное мно­ жество однотипных задач. Массовую проблему можно обозначать, например, через {я,}, где«г - некотораяединичная чадяча.

Переход от расплывчатого понятая алгоритма к строгому опре­ делению специальных алгоритмов (нормальный алгоритм, или алго­ ритм Тьюринга) позволяет уточнить вопрос об алгоритмической разрешимоститого илииного круга задач.

24'

Массовая проблема {о;\ называется алгоритмически разре­ шимой. если существует алторит (нормальный алгоритм или алго­ ритм Тьюринга), позволяющий решить каждую задачу этой массовой проблемы, и алгоритмически неразрешимой, &сли такого алгоритма не существует.

Проблема алгоритмической (не)разремш1ссти формулируется

мически разрешимой?»

и философ Лейбниц (1646-1716) мечтал о создании всеобщего метода, позволяющего решать любую задачу. Хотя всеобщего алгоритма ему

алгоритм будет найдем. Несыогря на долгие и упорные усилия многих крупных специалистов, чруякоо и остались непреодолимыми. Более того, были обнаружены большие трудности даже при попытке создание алгоритмов для нексюрых массовых проблем частного вида (не говоря уже о любой задаче). В результате многочисленных, но безрезультатных попыток создания таких алгоритмов стало вено, что налицо имеются трудности принципиального характера, и воз-

решаю-дего алгоритма. Оказалось, что для целого ряда массиры* проблем невозможно построил разрешающего алшритка, т.е. алгоритма, который позволил ба решить все задачи данной массовой проблемы. Первые результаты такого рода были обнаружены в математической логике о работах Геделя, Чёрча, Тьюринга. Ими были указаны (найдены) примеры алгоритмически неразрешимых массовых проблем.

Таким образом, существуют как алгоритмически разрешимые проблемы, так и алгоритмически неразрешимые массивые проблемы.

К алгоритмически разрешимым массовым проблемам относятся, например, следующие:

-сложение двух иболее заданных чисел; - решение в радикалах уравнений от одной переменной не выше

четвертой степени; -решение систем линейных уравнений си неилкстными1

Обнаружение алгоритмически неразрешимых проблем создало в нлукетакую ситуацию, когда математик, стремящийся к построению желаемого алгоритма, должен считаться с тем, что такого алгоритма может и не существовать. Поэтому параллельно с поиском желаемого алгоритма приходится прилагать усилия для доказательства сущест­ вования такого алгоритма.

Рассмотрим, например, полиномы, зависящие от произвольного числа переменных 11Д1, -.л, с целыми коэффициентами. Такие полиномы называют днофантовыми в память греческого математика Диофанта, рассмотревшего некоторые да таки* полиномов. Будем интересоваться, есть ли у такого полинома целочисленные корни (диофантовы корни). Целочисленными решениями полиномов интересовались еще античные математики, например, в связи с теоремой Пифагора они рассматривали уравнение 1!+У=гг. Евклид приводит формулы, позволяющие найти псе целочисленные решения этого уравнения. Сам Диофант (Ш в. н.э) среди многих других уравнений рассмотрел уравнение ап +Ьх+с=у и решил его для неко­ торых частных случаев.

В эпоху развития анализа диифзитпвы уравнении привлекали внимание таких выдающиеся ученых как Ферма, Эйлер, Лаграюк, Гаусс. В частности. Ферма выдвинул гнамснигую гипотезу о том, что уравнение ^ -1/ = 11 при п>2 не имеет целочисленных решений (большая теорема Ферма).

На рубеже Х1Х-ХХ вв. Гильберт включил проблему диофантоаыч уравнений в число наиболее аяжнмх проблем, которые XIX век оставил XX веку. Эта проблема была сформулирована им так [27]: "Пусть задано произвольное диофактовое уравнение с произвольными неизвестными н целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах" Эта проблема называется / £?-ы проблемой Гильберта.

247

В 70-е голы XX в. советскими математиками Ю. В. Матиясеаичсм и Г. В. Чудновским было доказано, что эта проблема алгоритмически неразрешима, т.е. алгоритм, который искали, не существует.

Заметим, что на существует алгоритма, позволяющего выяснить наличие целых (дисфантовых) корней дм произвольного полинома от щюизвольного числа переменньв. Для полиномов частного вида разрешающий ялгориш может существовать.

§ 13. Примеры алгоритмически неразрешимых массовых проблем

В предыдущем параграфе уже рассматривалась одни из алгорит­ мически неразрешимых массовых проблем - 10-я проблема Гиль­ берта. Рассмотрим еще несколько таких примеров.

1. Проблема распознавания применимости. Путь задан н мальный алгоритмА н слово Р. Возможны два случая:

1)алгоритм А применим а слову Р, т.е. процесс переработки

2)алгоритм А бесконечно перерабатывает слово Р. т.е. не при­ меним к этому слову.

Следовательно, возникает задача а/, применим т А к Р или нет. Учитывая, что нормальных алюритнов А и слов Р иожет быть бесчисленное множества, получаем массовую проблему {а,} - проблему рьопомавания применимости произвольного нормального алгоритма к произвольному слову.

Далее ставим вопрос: существует ли общий метол для репгенил всех задач этой проблемы, т.е. есть ли общий метод, который

позволил бы выяснить применимость произвольного нормального алгоритма А к произвольному слову Р. Под общим методом будем понимал, либо нормальный алгоритм, либо машину (алгоритм) Тьюринга.

248

Теорема 6.7. Не существует нормального алгоритма В,

позволяющего решить вег задачи массовая проблемы {г,}. Иначе:
не существует нормального алгоритма В, который позволяй Си
выяснить, применим или нет произвольный нормальный алгоритм А |
iкпроизвольному олову Р.	_____
Теорему примем бездоказательства.
2, Проблема зкаталеитности слов. ПустьА - некоторый алфа­
вит; Р и Q слова в этом алфавите; P-*Q -	ориентированная подста­

новка, т.е. когда вместо слова р подставляется слово Q; P-Q - неориентированная подстановка, т.е. можно подсчавтъ либо вместо Р слово Q, либо наоборот, вместо Q слово Р. Из бесчисленного множества возможны* подстановок в алфавите А задают некоторое конечное множество подстановок указанных видов и называют ни допустимыми подстановками.

Два слова Л и S' в алфавитеА называются эквивалентнымиесли существует конечная последовательность слов Ri,Ri,...,R, (Ri=R, такал, что Я,, получается из Л, в результате одной допустимой

Возникает следующая массовая проблема: для любых двух слов в данном алфавите требуется указать, эквивалентны они или нет - проблема эхвивалснтиостн слов. Марков и Пост доказали, пто данная проблематоже алгоритмическинеразрешима.

3.Проблема предстатмисти матриц. Пусть £/].[/»..,£/, - матрицы порядка пуп. Булем говорить о матрице U того же порядка, что с«а предсчавныа через С/|,Ь\ У„ если для некоторого целого положительного I и целых чисел n.r^.-.ri из ряда 1,2, ..,q имеет место равенство

и - ц ,•%*... *ия.

Общая проблема преостаеимости матриц. Дакс целое положительное число к, требуется выяснить, существует ли алгоритм, посредством которого можно было бы узнавать для тобой

249

системы нитрид 4¾ ££,...,¾ порядка «»л, представима ли матрица J через матрицы U\, ¢/1,.-.¾.

Чистнпд проблема предетмшюстн матриц. Даны матрицы У|,Vi... U, порядка пхп. Требуется выяснять, существует ли алгоритм, посредством которого можво было бы узнавать днилюбой матрицы U

того же порглка. представимали она через U],Uj,...,C',r

А. А. Маркое построил снстеиу из 102 матриц 6-го порядка, для которойдоказал алгоритмическую неразрешимость чистиой проблемы представимости, откуда сразу следует алгоритмическая неразреши­ мость и общей проблемыпредставимостиматриц для май (позже было доказано для я>4).

4. Проблема неразрешимости логики гфкйикатав. Черч доказано, что не существует алгоритма, который для любой формулы логикипредикатовустанавливает,логическиобщезначима онакли нет.

j .Проблема остановки. Тьюрингом доказано, что не сущест­ вует алгоритма, позволяющего выяснить, остановится или нет произвольная программа дпа произвольного заданного входа. Смысл этого утверждения для теоретического программирования состоит 8 следующем: не существует ебщаго метода проверки программ us наличие в них бесконечных циклов.

6. Не существует алгоритма, позволяющего устаном вычисляет ли некоторая конкретная программа (на любом языке программирования) постоянную нулевую функцию Z(x)=0. Как следствие, можно утверждать, что проблема о том, вычисляют ли две произвольные программы одну и ту же одяоаргументкую функцию, тоже алгоритмически неразрешима. Тем самым получаем, ито в об­ ласти тестирования компьютерных программ имеются принциниаль-

Сделаем несколько замечаний.

1. Теоремы об алгоритмической неразрешимости утвержд лишь то, что класс рассмвтрниаемьпезадач достаточно обширен и для них нет одного разрешающего алгоритма, ни не утверждается вообще

250