Дискретная математика без формул

      При использовании логики для проектирования логических схем, например отдельных фрагментов процессора, первоначально эксплуатировали аналогию с релейными схемами. Операция диз'юнкции(" или") соответствует параллельному подключению контактов реле, кон'юнкции(" и") – последовательному. Операция отрицания(" не") моделируется нормально замкнутым контактом реле. То есть контакт размыкается при срабатывании реле. Разумеется, все это реализовывалось в полупроводниковом «модульном» варианте. Тогда достаточно было выпустить, например, модули типа «и-не», чтобы на них реализовать любую схему. (А сам процессор был размером со шкаф, но не по вине логики).

Лекция 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.
 
      Базовые функции и функции, которые могут быть построены из них с помощью операторов суперпозиции, примитивной рекурсии и наименьшего корня, образуют множество ЧАСТИЧНО-РЕКУРСИВНЫХ ФУНКЦИЙ. А множество частично-рекурсивных функций совпадает с множеством всех алгоритмически разрешимых задач (множеством всех вычислимых функций). Кстати, за слово «частичные» надо благодарить оператор наименьшего корня, из-за которого в множество построенных функций входят и не всюду определенные (частичные) функции.
 
      Тьюринг не был автостроителем. Машина Тьюринга не предполагает двигателя внутреннего сгорания, поскольку все там перемещается исключительно силой мысли. Это математическая модель. Она чем-то может и напоминающая автомашину, но не более чем машину напоминает магнитофон, в котором лента (разделенная на ячейки) неподвижна, а считывающе-записывающая головка вдоль нее ездит. Хуже того, ездит головка рывками, от ячейки к ячейке. А в ячейках записаны символы. (Чтобы не было пустых ячеек, в пустые ячейки записывают специальный пустой символ).
 
      В машине Тьюринга есть устройство управления, имеющее память «состояний» и работающее по задаваемой программе (алгоритму). Программа состоит из команд. Каждая «команда» состоит в следующем: Машина читает символ из ячейки, против которой стоит головка (находясь в каком-то состоянии [вначале – в начальном]), записывает в эту ячейку символ (может и тот же самый), меняет свое состояние (может сохранить прежнее) и делает шаг влево или вправо (может остаться на месте).
      Так Машина ходит вдоль ленты до тех пор, пока не перейдет в специальное состояние, называемое заключительным. Это говорит об окончании работы Машины (алгоритма). А на ленте остается результат (решения).
 
      Пример. Построим Машину, которая в сплошной последовательности единичек стирает последнюю.
      Поскольку количество единичек в сплошной последовательности произвольное и неизвестное, последнюю определим как ту, которая стоит ПЕРЕДпустым символом. Это главная идея данного решения. Остальное – дело техники. Напишем программу – четыре команды.
      Машина читает пустой символ, находясь в начальном состоянии пишет пустой символ и делает шаг вправо. (Значит машина находится ДОначала последовательности единичек)
      Машина читает единичку, находясь в начальном состоянии, пишет единичку и делает шаг вправо, оставаясь в этом состоянии. (Значит машина «идет» по последовательности единичек)
      Машина читает пустой символ, находясь в начальном состоянии, пишет пустой символ, делает шаг влево и переходит во второе состояние. (Значит найдена последняя единичка)
      Машина читает единичку, находясь во втором состоянии, пишет пустой символ (стирает единичку), стоит на месте и переходит в заключительное состояние. (Задача решена)
      Несмотря на внешнюю примитивность такой конструкции, для любой алгоритмически разрешимой задачи можно построить Машину Тьюринга! А поскольку машина строится в собственной голове, вопросы «технической эффективности» такой машины никакой роли не играют. Единственный вопрос. Доберется ли машина до заключительного состояния? Пусть и через (воображаемый) миллион лет. Тогда задача разрешима!
 
      Не будет преувеличением сказать, что нормальные алгорифмы Маркова создал А.А.Марков, член-корреспондент Академии Наук СССР из Москвы. Для восстановления единообразия, по праву автора, он назвал алгориТмы алгориФмами, поскольку слово это арабо-греческое, как и слово ариФметика…
      Смысл нормальных алгорифмов – принудительный обмен, порядок которого жестко задан.
      Собственно алгоритм в нормальных алгорифмах задается НОРМАЛЬНОЙ СХЕМОЙ ПОДСТАНОВОК– очередностью правил «что на что менять». Лучше всего это показать на примере замены слов, тем более, что и сам Марков любую последовательность букв, какую ни в одном словаре не сыщешь, называл «словами». Так при наличии двух подстановок: меняющей «ха» на «ссон» и «мусс» на «сл» из «муха» можно сделать «слон».