Лекция 8. Алгебра высказываний

 

В этой алгебре об'ектами служат высказывания, о которых мы

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

Осталось поговорить об их свойствах или законах, чтобы определится

наконец с алгеброй.

Если использовать только три первых логических операции:

диз'юнкцию, кон'юнкцию и отрицание, то алгебра высказываний

аналогична алгебре множеств. Аналог диз'юнкции - об'единение,

кон'юнкции - пересечение, а отрицания - дополнение. Эти аналогии

можно использовать для одного из возможных об'яснений смысла

логических операций (это, так называемая, теоретико-множественная

интерпретация - и она достаточно "естественна"). Но мы

ограничимся формальным подходом. А в связи с этим напомним, что

нами были названы еще импликация, эквивалентность и штрих

Шеффера, аналогов которым в теории множеств мы не стали искать.

Однако эти операции можно выразить через первые три.

 

Импликацию можно представить иначе, если взять диз'юнкцию

отрицания первого высказывания со вторым. То есть с точки зрения

формальной логики равносильны высказывания:

"ЕСЛИ стоит хорошая погода, ТО мы купаемся" и

"НЕВЕРНО, что стоит хорошая погода, ИЛИ мы купаемся".

Единственный случай, когда оба сложных высказывания ложны,

это когда первое высказывание истинно, а второе ложно, то есть

когда погода стоит хорошая, а мы не купаемся.

 

Для эквивалентности замена более длинная, но, фактически,

совпадающая с определением. Например, высказывание (пусть и

несколько диковатое):

"Хорошая погода стоит ТОГДА И ТОЛЬКО ТОГДА, КОГДА мы

купаемся" эквивалентно высказыванию "Хорошая погода И мы купаемся

ИЛИ НЕхорошая погода И мы НЕ купаемся".

Кстати, эквивалентность можно было выразить и через

кон'юнкцию двух импликаций:

"ЕСЛИ стоит хорошая погода, ТО мы купаемся И ЕСЛИ мы

купаемся, ТО стоит хорошая погода".

 

Штрих Шеффера для этих же исходных высказываний мог бы

выглядеть следующим образом:

"НЕ ВЕРНО, что стоит хорошая погода И мы купаемся" или (по

так называемому закону Де Моргана) это равносильно высказыванию:

"НЕхорошая погода ИЛИ мы НЕ купаемся".

 

В алгебре высказываний есть законы: коммутативный,

ассоциативный и дистрибутивный, которые аналогичны законам для

множеств.

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

закона воспользуемся примером из книги Клини "Математическая

логика": "Мэри вышла замуж И родила ребенка" равносильно с точки

зрения логики тому что "Мэри родила ребенка И вышла замуж".

Первый "заяц" связан c синтаксисом коммутативного закона - то

есть можно переставлять местами высказывания, а второй "заяц" - с

семантикой, при которой перестановка не соответствует

общепринятой морали - для приличного общества существенно, какое

событие стоит первым. (Это в очередной раз говорит о том, что

математическая логика не учитывает [и не в состоянии это

сделать!] многих нюансов, имеющих место в практике жизни).

 

Ассоциативный закон утверждает, что безразлично, в каком

порядке мы рассматриваем (истинность) попарных кон'юнкций и

диз'юнкций:

"Стоит хорошая погода И мы купаемся И заработали ангину".

"Стоит хорошая погода ИЛИ мы купаемся ИЛИ заработали ангину".

Поскольку очередность выполнения операций в математике часто

задают скобками, то ассоциативный закон еще называют законом

снятия скобок.

 

Дистрибутивный закон. Приведем пример только для

"экзотического" случая.

"Стоит хорошая погода ИЛИ мы купаемся И заработали ангину"

равносильно высказыванию

"Стоит хорошая погода И мы купаемся ИЛИ

стоит хорошая погода И заработали ангину"

 

Не будем перечислять все возможные законы логики

высказываний. Как уже было сказано, они аналогичны законам

алгебры множеств. Но важно заметить, что здесь мы вместо слова

"равенство" употребляли слово "равносильность". Два сложных

высказывания являются равносильными, если они имеют одинаковые

ТАБЛИЦЫ ИСТИННОСТИ. В этих таблицах начальные столбцы

соответствуют исходным (элементарным) высказываниям, а последний

результирующему (сложному) высказыванию. В начальных столбцах

проставляются все возможные комбинации истинности элементарных

высказываний, а в последнем истинность сложного высказывания.

Для каждой комбинации отдельная строка.

Для последнего примера таблицы будут одинаковыми для левой и

правой части дистрибутивного закона:

 

хорошая погода | мы купаемся | заработали ангину | РЕЗУЛЬТАТ

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 1

1 0 1 1

1 1 0 1

1 1 1 1

 

 

Касательно математической логики, как и множеств, есть люди,

несогласные с рядом ее законов. Прежде всего это опять законы

исключенного третьего и противоречия. То есть заполнение

очевидных таблиц истинности для конструктивистов (интуиционистов)

неочевидно!

 

Конструктивисты относительно сложного высказывания "Теорема

Ферма верна ИЛИ теорема Ферма НЕверна" говорят, что это сложное

высказывание не может быть истинным хотя бы потому, что признав

его истинность мы окончательно делаем неразрешимым вопрос "Так

верна она или нет?!". Более человеколюбивые логики в качестве

аргумента приводят сложные высказывания типа: "Человек почти

лысый ИЛИ НЕ ВЕРНО, что человек почти лысый". Утверждают, что

определить истинность этого сложного высказывания не только

невозможно, но и просто бестактно.

 

Логика высказываний, и алгебра высказываний в частности, как

уже ранее говорилось, бурно расцветали на заре вычислительной

техники. Одно из важнейших алгебраических преобразований - это

минимизация сложных высказываний. То есть было создано множество

методик получения из исходного высказывания равносильного, но

имеющего наименьшее возможное число логических операций. А в

соответствии с таким высказыванием можно построить и максимально

простое техническое устройство. И всем заинтересованным лицам

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

 

Лекция 9. ЛОГИКА ПРЕДИКАТОВ "Предикат" с английского переводится как сказуемое. Ноговорить "логика сказуемых" - себя не уважать. Формальнопредикатом называется функция, аргументами которой могут бытьПРОИЗВОЛЬНЫЕ ОБ'ЕКТЫ из некоторого множества, а значения функции"истина" или "ложь". Предикат можно рассматривать как расширениепонятия высказывания. Пример. Вместо трех высказываний "Маша любит кашу" "Даша любит кашу" "Саша любит кашу"можно написать один предикат "Икс любит кашу"и договориться, что вместо неизвестного Икс могут быть либо Маша,либо Даша, либо Саша. Подстановка вместо Икс имени конкретного ребенка превращаетпредикат в обычное высказывание. Для предикатов справедливы, и имеют тот же смысл, ранеерассмотренные логические операции. Например, "ЕСЛИ Маша любит кашу, ТО Саша любит кашу". Но есть и две новые операции, специфические. Они называютсянесколько вызывающе - операциями НАВЕШИВАНИЯ КВАНТОРОВ. Этиоперации соответствуют фразам "для всех" - квантор общности и"некоторые" - квантор существования. Мы договорились не писатьформул, но все-таки следует сказать о значках, которые здесьиспользуются, в силу их экзотичности. Квантор общности произошелот английского All и обозначается буквой A, перевернутой вверхногами. Квантор существования произошел от английского Exist иобозначается буквой E, которую вверх ногами переворачиватьбесполезно, поэтому ее повернули кругом. Наш предикат, после навешивания каждого из кванторов, такжепревращается в высказывание, которое может быть истинно или ложно! "ВСЕ любят кашу" "НЕКОТОРЫЕ любят кашу" Это, кстати, был (до навешивания кванторов) одноместныйпредикат (одноместная функция). Но предикаты могут быть не толькоодноместные. Это просто проиллюстрировать, если представить, чтодети могут любить не только кашу... "Икс любит Игрека" -двухместный предикат. "ВСЕ любят Игрека" - одноместный предикат."ВСЕ любят КОЙ-КОГО [некоторого]" - нульместный предикат, тоесть высказывание. Интересно посмотреть, как ведут себя кванторы в присутствииоперации отрицания. Возьмем отрицание предиката "ВСЕ любят кашу":"НЕ ВЕРНО, что ВСЕ любят кашу". Это равносильно (по закону ДеМоргана!) заявлению: "НЕКОТОРЫЕ НЕ любят кашу. То есть отрицание"задвинули" за квантор, в результате чего квантор сменился напротивоположный. А теперь сделаем одно из самых важных заявлений: ИЗ ФОРМАЛИЗОВАННЫХ ЯЗЫКОВ МАТЕМАТИКИ ЯЗЫК ПРЕДИКАТОВ - САМЫЙБЛИЗКИЙ К ЕСТЕСТВЕННОМУ. Поэтому работы по искусственномуинтеллекту тяготеют к использованию этого языка. В сравнении сестественным, это очень во многих смыслах ограниченный язык. Нолучшего за 100 лет не придумано, если не считать так называемого"синтаксического сахара", когда вместо соответствующей символикииспользуются, например, слова естественного языка. (Вроде того,как мы пытаемся это делать). В хорошо формализованных системах даже наоборот,дополнительно ограничивают этот язык для удобной реализации накомпьютерах. Примером тому язык (логического) программированияПРОЛОГ - ПРОграммирование на ЛОГике. Так вот, язык предикатов наследует пороки языка логикивысказываний, которые обуславливают изначальное несоответствиеестественного и логического языков. На языке предикатов можно описать далеко не все, хотя имногое. Но даже в этом ограниченном пространстве подчасприходится применять хитрости и уловки, которые бы большепристали ремеслу или искусству. Хотя об'яснения, в конце концов,обычно бывают строго формальные. Вот некоторые "классические примеры".Если мы желаем сказать на языке предикатов "Все студенты отличники",то рекомендуется конструкция "ДЛЯ ВСЕХ иксов справедливо: ЕСЛИ икс студент, ТО икс отличник" Но если хотим сказать "Некоторые студенты отличники", то этоследует записать "ДЛЯ НЕКОТОРЫХ иксов справедливо: икс студент И иксотличник" Конструкция ЕСЛИ..., ТО в даном случае не подходит. Ивот почему: стоит затесаться в компанию одному иксу-нестуденту ион сделает этот предикат истинным, даже если там нет ни одногоотличника! И еще высказывание "Собакам и кошкам вход воспрещен".Конструкция "ДЛЯ ВСЕХ иксов справедливо: ЕСЛИ икс - собака И икс -кошка, ТО иксу вход запрещен" Ясно что таких иксов, которые бы были одновременно собакой икошкой не существует! Как, впрочем, и таких игреков. Поэтому "ДЛЯ ВСЕХ иксов справедливо: ЕСЛИ икс - собака ИЛИ икс -кошка, ТО иксу вход запрещен" И список таких фокусов-выкрутасов можно продолжать долго. Добесконечности. Но, главное, во-время остановиться и понять, чтоесли бы даже придумать другую логику, в которой не было бы этихпроблем, то получится логика, в которой будут другие проблемы,скорее всего существенно большие. А мы даже не трогали такихзаморочек, присущих естественным языкам, как синонимы, омонимы,метафоры, гиперболы и т.д и т.п. Одни идиомы, кто знает, чегостоят!.. Так что "братания" языка логики с естественным языкомне предвидится и в самой отдаленной перспективе, даже когдапланета Земля начнет остывать...

 

Лекция 10. АКСИОМАТИЧЕСКИЕ ТЕОРИИ Если алгебра логики и дает образец логического мышления, тоуж очень специфический. Строгие логические рассуждения и близкоот такого образца не лежали. Создавать (абсолютно) строгиелогические (то есть абсолютно логичные) системы позволяетдедуктивный подход. Не путать с "дедуктивным методом" ШерлокаХолмса. У Холмса, или скорее у Конан-Дойля, явно были проблемы слогикой, коль скоро он путал дедукцию с индукцией... ДЕДУКТИВНЫЙ подход, называемый еще АКСИОМАТИЧЕСКИМ, этоподход от общего к частному. От аксиом (постулатов) к теоремам(следствиям). Аксиоматическая теория строго задана, если строгосформулирован (задан) язык теории, ее аксиомы и правила вывода.Стоит хотя бы в одной из этих трех составляющих "дать слабину" истрогой теории как не бывало! Знаменитая (одна из первых) аксиоматическая теория -геометрия Эвклида худо-бедно обеспечила строгость только в одномкомпоненте - в постулатах. Но язык, на котором проводятсядоказательства в геометрии даже через тысячелетия, как истрогость самих доказательств не выдерживают критики. Это неболее, чем неоднозначный метафорическо-аллегорический язык иправдоподобные рассуждения. Потому-то нередки случаи, когдаопровергаются "доказанные" теоремы. Собственно, почти всяматематика, за исключением сравнительно малюсенького раздела излогики аксиоматических систем, покоится (лучше звучит - зиждется)на правдоподобных рассуждениях и порядочности доказывающих. Так что образцовая безупречно строгая теория задается наязыке предикатных формул. (Мы здесь зареклись использоватьформулы, поэтому остается полагаться на собственную честность). Аксиомами об'являются некоторые из формул. В жизни мы такжеоб'являем законами (аксиомами) не все фразы, которые можноввернуть в той или иной ситуации, а лишь некоторые, которые мырешили считать таковыми... Законы (Аксиомы) это вопрос веры, аиногда целесообразности. Они недоказуемы! Если доказуемы, то этоуже теоремы! Существование Бога недоказуемо! Иначе это была бы теорема.А из каких, простите, более первичных понятий такую "теорему"выводить прикажете?!.. Закон всемирного тяготения недоказуем. Мы просто емуповерили, посколько надоело проводить эксперименты по падениютел, в ожидании, когда с ними произойдет что-нибудь оригинальное. Выводы в теории тоже следует формализовать, посколькукаждому в жизни встречались люди, которые "убедительно" доказываликакую-нибудь чушь. Кстати, самое знаменитое правило вывода в математическойлогике (modus ponens) удручает своей очевидностью и дажепримитивностью. Проиллюстрировать его можно так: Пусть в системеесть утверждения "ЕСЛИ хорошая погода, ТО мы гуляем"и "Хорошая погода"тогда в соответствии с modus ponens выводимо утверждение "Мы гуляем" При всей своей примитивности это правило вывода имеетрешающее достоинство. Оно очевидно для всех. Очевиднее небывает! А если в системе есть еще и утверждение: "ЕСЛИ мы гуляем, ТО обязательно заблудимся"то с учетом ранее выведенного "Мы гуляем"получим "Обязательно заблудимся" Видите, как далеко можно зайти маленькими очевиднымишажками! Существует много и других правил вывода, но все имеютобязательное свойство - очевидность. Эта очевидность позволяетдалее использовать эти правила абсолютно формально. То естьрезультат вычисляется. Такие символьные вычисления называютсяИСЧИСЛЕНИЯМИ. Есть еще один подход к аксиоматике, когда основной упорделается именно на правила вывода. Такие системы (почему-то)называются системами естественного вывода, намекая на то, что вних собраны базовые естественные правила логических рассуждений. Логики резвились меж собой до тех пор, пока не былсформулирован подход к созданию аксиоматических систем подназванием ПРИНЦИП (МЕТОД) РЕЗОЛЮЦИ. Он очень способствовалпродвижению логики в широкие народные массы. С одной стороны, активизировались работы по использованиюкомпьютеров для реализации логического вывода и работы поискусственному интеллекту в частности. А с другой стороны, наэтой основе был создан язык ПРОЛОГ. Это совсем другое программирование, нежели традиционноепроцедурное. Это даже не программирование в обычном смысле слова,коль скоро здесь программист не пишет алгоритм решения задачи. Онописывает логические зависимости "мира", в котором существуетзадача. На основе описанной логики "мира" система (машина) самасоздает алгоритм в процессе поиска решения! Это только кажется, что аксиоматические системы - этосложно. Любой может напридумывать их сколько угодно. Болеепростым делом вам вряд ли приходилось заниматься. Например, в качестве языка можно об'явить любые "слова" изпоследовательности буквы Я. Букву Я об'явим аксиомой. Правило вывода будет удваивать букву Я. То есть сходу придумана теория, в которой выводимы любыепоследовательности (слова), состоящие из буквы Я. Я ЯЯ ЯЯЯ... ЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯ... И все бы хорошо, только такая строго заданная теория малочто дает создателю, кроме радости созидания. Поэтому встаетвопрос целесообразности, смысла. Той самой семантики... Здесьлогики заняли очень(!) интересную позицию. Коль скоро логика не интересуется смыслом высказываний, алишь их истинностью, то ее (истинность) и об'явили смысломвысказываний. Вдумайтесь, смысл высказывания, например, "Газ принагревании расширяется" не в том, что это отражение физическогозакона, а в том что оно истинно. Следовательно, точно такой жесмысл(!) имеет высказывание "Никита Михалков - кинорежиссер". Тоесть его смысл в том, что оно тоже истинное. Дальше - больше. Язык предикатов - это существенноерасширение языка высказываний и обычным образом перебрать всеслучаи даже в простейшей ситуации, вроде "Икс любит кашу", невсегда возможно. Тем более, что речь может идти и обесконечностях. Для решения проблем семантики в этом случаеприбегают к теории моделей. Но это теория также, в конечномитоге, упирается в "смысл" типа истинно-ложно. Возвращаясь к аксиоматическим теориям следует сказать, что вматематике "практический смысл" имеют лишь такие теории, вкоторых можно выводить только истинные формулы. И нельзя ложные.Одна ложная формула "уничтожает без остатка" любуюаксиоматическую теорию. Наша теория, созданная из буквы Я, не привязана к понятиюистинности. Поэтому она бессмысленна, как бессистемнаяперестановка детских кубиков. С кубиками все ясно. Но проблемы аксиоматических теорий наэтом не исчерпываются. Пожалуй самым фундаментальным открытием вэтой сфере следует считать доказанную Геделем ТЕОРЕМУ ОНЕПОЛНОТЕ. Оказывается, в сколько-нибудь сложной аксиоматическойсистеме (посложнее, чем кубики, но достаточно даже арифметики)существуют формулы, которые нельзя ни доказать, ни опровергнуть.Может в этом причина, что не все школьные задачки имеют решения?!Так что, создавая свои аксиоматические теории помните, что онидолжны обладать какими-то полезными свойствами. А такие теориисоздавать уже не так-то просто. Хотя создать свою собственнуюматематику может каждый! Известно высказывание одного крупного математика:"Преимущество аксиоматизации - это преимущество воровства передчестным трудом".

 

Лекция 11. ТЕОРИЯ АЛГОРИТМОВ Теория алгоритмов не учит "составлять" алгоритмы. Оназанимается более важным вопросом. Основная задача классическойтеории алгоритмов - это ответ на вопрос: " Можно ли (вообще) длязадач данного типа построить алгоритм?". Говоря болеенаукообразно: "Являются ли задачи данного типа алгоритмическиразрешимыми"? Это связано с тем, что, во-первых, не для всех задачвозможно создать алгоритмы их решения. А, во-вторых, чтобысделать математически строгий вывод о невозможности построитьалгоритм, надо иметь строгое (формальное) определение самогоалгоритма. Но понятие АЛГОРИТМА относится к фундаментальнымнеопределяемым понятиям. В вопросе об алгоритме у нас собачьяпозиция. Понимать понимаем, а сказать не можем. Если где-товстречаете "определение" алгоритма, то там, что ни слово - тоаллегория... Из этого тупика был найден нетривиальный выход. Понятиеалгоритма заменили строго формализованными математическимимоделями. Среди самых известных рекурсивные функции, машиныТьюринга и нормальные алгорифмы Маркова. Эти математические модели выступают в роли "конкретизацийпонятия алгоритма". То есть длительная практика подтверждает такназываемый тезис Черча, который можно пересказать так: Для любой алгоритмически разрешимой задачи можно построить рекурсивную функцию (машину Тьюринга, нормальный алгорифм Маркова). И наоборот, для задач, для которых нельзя построить перечисленные конкретизации, не существует алгоритма решения. РЕКУРСИВНЫЕ ФУНКЦИИ основаны на той идее, что исходные даныеи возможные результаты решения любой задачи можно пронумеровать.Для чего, естественно, достаточно множества натуральных чисел(целых положительных чисел, начиная с нуля). А далее базовымиоб'являются функции, возможность выполнить (вычислить) которые невызывает сомнений. НУЛЬ-ФУНКЦИЯ - это функция, которая дает значение ноль длялюбого значения аргумента. Реализовать эту функцию может нетолько ребенок. Можно посадить попугая и подучить его на любойвопрос о значении функции кричать "Ноль!". ФУНКЦИЯ СЛЕДОВАНИЯ дает следующее, по сравнению саргументом, значение. Для пяти это шесть, для миллиона - миллионодин. Можно бы было сказать, что здесь надо просто прибавлять 1.Но операции сложения у нас пока нет! ФУНКЦИЯ ВЫБОРА АРГУМЕНТА. Это вообще забавная даже дляпервоклассника функция, содержащая в своем имени номер аргумента.Если у вас есть несколько аргументов, то эта функция в качествезначения возьмет значение указанного в ней аргумента. Например,функция выбора третьего из Иванова, Петрова и Сидорова, которыхмы ранее пронумеровали, например, как 22, 13 и 49, даст значение49. Эти три базовых функции могут использоваться далее вкачестве исходного материала для создания более сложных функций спомощью трех операторов: суперпозиции, примитивной рекурсии инаименьшего корня. Известный хорошо еще со школы ОПЕРАТОР СУПЕРПОЗИЦИИпозволяет вместо аргумента подставлять функцию... "Игла в яйце, аяйцо в ларце"... Дольше словами описывать ОПЕРАТОР ПРИМИТИВНОЙ РЕКУРСИИ. Ноесли поднатужиться, то можно понять. Этот оператор позволяетпостроить новую функцию из двух функций, одна из которых имеет наодин аргумент меньше, а другая на один аргумент больше. Значение создаваемой функции для нулевого значениявыбранного аргумента приравнивается к функции, не имеющей как разэтого аргумента. Значение же создаваемой функции для всех прочих(ненулевых) значений выбранного аргумента приравнивается другойфункции, зависящей (напрягитесь!) от тех же аргументов, кромевыбранного; от ПРЕДЫДУЩЕГО значения выбранного аргумента и отсоздаваемой функции от предыдущего значения выбранного аргумента. Ну как тут не пожалеть о формулах. Хотя, на самом-то деле мы со школы сталкиваемся с такогорода функциями, но, как тот герой, только на старости лет узнаем,что говорим прозой. Приведем построение с помощью рекурсии всемизвестной двухместной функции умножения икс на игрек (считаявыбранной переменной игрек). Функцию умножения икс на ноль можно выразить черезнуль-функцию от икс, которая обеспечит нам желанное значение -ноль. Функцию умножения икс на игрек (отличный от нуля) можновыразить через функцию сложения икса со значением функцииумножения икса на предыдущее значение игрека... То есть мывыразили умножение через сложение. Здесь следует сделать два замечания. Считаем, что к этомумоменту доказана рекурсивность используемой здесь функциясложения. И второе, при умножении икс на игрек в нашемраспоряжении функция от трех аргументов. Но, применивпроектирующую функцию мы избавимся от среднего аргумента, кольскоро он нам здесь не нужен. Нам ведь дозволено заниматьсяподбором из возможного! Последний оператор - ОПЕРАТОР НАИМЕНЬШЕГО КОРНЯ. Егонеобходимость просто об'яснить хотя бы тем, что рекурсивныефункции, призванные решать любые алгоритмически разрешимые задачи,сами используют лишь целые положительные числа. А это непозволяет решить даже детскую задачку: 5 - 8 =? (Нет длярекурсивных функций отрицательных чисел). На самом-то деле этидетские задачки можно решить по-детски. Договориться, что 1000это (сдвинутый) ноль, а вычитание - есть сложение с"отрицательным" числом! Тогда 1005 + 992 = 1997 (приведение к шкале: 1997 - 1000 = 997) Поскольку мы при этом сдвиг нуля учли дважды, тоокончательный результат (в системе с один раз сдвинутым на 1000нулем) будет 997. Но это детское решение лишь говорит о том, чтобез отрицательных чисел и в школе можно обойтись. Как и в древнемРиме обходились. Правда там и без нуля обходились, а здесь он намнужен позарез. Именно оператор наименьшего корня и следит, при какомзначении выбранного аргумента наблюдаемая им функция впервыеопустится до нуля. Это значение выбранного аргумента и будетзначением оператора наименьшего корня. Например, для функции иксминус игрек при иксе равном 5, значение оператора наименьшегокорня также будет равно 5, поскольку двигаясь в значениях игрекаот нуля получим нулевое значение функции именно при игрек равном5. Базовые функции и функции, которые могут быть построены изних с помощью операторов суперпозиции, примитивной рекурсии инаименьшего корня, образуют множество ЧАСТИЧНО-РЕКУРСИВНЫХФУНКЦИЙ. А множество частично-рекурсивных функций совпадает смножеством всех алгоритмически разрешимых задач (множеством всехвычислимых функций). Кстати, за слово "частичные" надоблагодарить оператор наименьшего корня, из-за которого вмножество построенных функций входят и не всюду определенные(частичные) функции. Тьюринг не был автостроителем. Машина Тьюринга непредполагает двигателя внутреннего сгорания, поскольку все тамперемещается исключительно силой мысли. Это математическаямодель. Она чем-то может и напоминающая автомашину, но не болеечем машину напоминает магнитофон, в котором лента (разделенная наячейки) неподвижна, а считывающе-записывающая головка вдоль нееездит. Хуже того, ездит головка рывками, от ячейки к ячейке. А вячейках записаны символы. (Чтобы не было пустых ячеек, в пустыеячейки записывают специальный пустой символ) В машине Тьюринга есть устройство управления, имеющее память"состояний" и работающее по задаваемой программе (алгоритму).Программа состоит из команд. Каждая "команда" состоит вследующем: Машина читает символ из ячейки, против которой стоитголовка (находясь в каком-то состоянии [вначале - в начальном]),записывает в эту ячейку символ (может и тот же самый), меняетсвое состояние (может сохранить прежнее) и делает шаг влево иливправо (может остаться на месте). Так Машина ходит вдоль ленты до тех пор, пока не перейдет вспециальное состояние, называемое заключительным. Это говорит обокончании работы Машины (алгоритма). А на ленте остаетсярезультат (решения). Пример. Построим Машину, которая в сплошнойпоследовательности единичек стирает последнюю. Поскольку количество единичек в сплошной последовательностипроизвольное и неизвестное, последнюю определим как ту, котораястоит ПЕРЕД пустым символом. Это главная идея данного решения.Остальное - дело техники. Напишем программу - четыре команды. Машина читает пустой символ, находясь в начальном состояниипишет пустой символ и делает шаг вправо. (Значит машина находитсяДО начала последовательности единичек) Машина читает единичку, находясь в начальном состоянии,пишет единичку и делает шаг вправо, оставаясь в этом состоянии.(Значит машина "идет" по последовательности единичек) Машина читает пустой символ, находясь в начальном состоянии,пишет пустой символ, делает шаг влево и переходит во второесостояние. (Значит найдена последняя единичка) Машина читает единичку, находясь во втором состоянии, пишетпустой символ (стирает единичку), стоит на месте и переходит взаключительное состояние. (Задача решена) Несмотря на внешнюю примитивность такой конструкции, длялюбой алгоритмически разрешимой задачи можно построить МашинуТьюринга! А поскольку машина строится в собственной голове,вопросы "технической эффективности" такой машины никакой роли неиграют. Единственный вопрос. Доберется ли машина дозаключительного состояния? Пусть и через (воображаемый) миллионлет. Тогда задача разрешима! Не будет преувеличением сказать, что нормальные алгорифмыМаркова создал А.А.Марков, член-корреспондент Академии Наук СССРиз Москвы. Для восстановления единообразия, по праву автора, онназвал алгориТмы алгориФмами, поскольку слово это арабо-греческое,как и слово ариФметика... Смысл нормальных алгорифмов - принудительный обмен, порядоккоторого жестко задан. Собственно алгоритм в нормальных алгорифмах задаетсяНОРМАЛЬНОЙ СХЕМОЙ ПОДСТАНОВОК - очередностью правил "что на чтоменять". Лучше всего это показать на примере замены слов, темболее, что и сам Марков любую последовательность букв, какую ни водном словаре не сыщешь, называл "словами". Так при наличии двухподстановок: меняющей "ха" на "ссон" и "мусс" на "сл" из "муха"можно сделать "слон". Механизм нормальных алгоритмов настолько прост, чтонапоминает скорее детскую игру, чем математику. Но на самом делеэто очень мощный механизм, поскольку через него можно выразитьрешение любой алгоритмически разрешимой задачи. И опять напомним,что это не следует воспринимать, как предложение решать любуюзадачу через подстановки (хотя на этих принципах работаетзамечательный язык программирования РЕФАЛ). Это лишь означает,что любую алгоритмически разрешимую задачу МОЖНО представить ввиде такой системы подстановок. А если нельзя (и вы это смоглидоказать), то такая задача вообще не имеет алгоритма решения.