Turing the Universe — истоки информатики

Дата: 12.01.14
Автор:
14 комментариев
Цена: Free
Скачать


turingНачало двадцатого века ознаменовалось грандиозным кризисом математики. Собственно, предпосылки его назревали ещё с предыдущего, девятнадцатого века, когда многие частные результаты были обобщены и стали целыми отраслями математической науки.

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

Школа формалистов утверждала, что математика должна быть абсолютно строгой, и в основе её должен лежать абсолютный минимум аксиом — пусть даже вывод чего-то из этого минимума будет громоздким и неудобопонимаемым. Школа интуиционистов утверждала, что вовсе нет необходимости в мозголомных построениях там, где можно положиться на нормальную человеческую соображаловку — и избавиться от противоречий таки да, нужно, но коль скоро без неопределяемых понятий обойтись нельзя, то нет смысла и стремиться к минимализму аксиоматики. Были у них и фирменные заморочки вроде отказа признавать неконструктивные доказательства теорем существования.

Обе эти точки зрения сами по себе выглядели вполне логично, но… когда дело доходило до конкретных моментов и примеров, представители обеих школ быстро находили в доводах оппонентов парадоксы и несообразности. (: Всё это длилось чуть больше двадцати лет, пока в 1930 году Курт Гёдель не доказал со всей строгостью Абсолютно Ужасную Вещь.

Если излагать немного упрощённо, то две гёделевские теоремы утверждали, что формально-логическая система, основанная на натуральных числах и их арифметике (читай — вся математика целиком!) либо неполна, либо внутренне противоречива. Неполноту здесь следует понимать вот как: существуют вполне осмысленные математические утверждения, которые нельзя ни доказать, ни опровергнуть — и в частности, нельзя доказать утверждение о том, что математика непротиворечива (если, конечно, это действительно так).

Это одинаково не устроило обе школы. Формалисты обломились со своей идеей минимизации аксиоматики — ведь недоказуемые и неопровергаемые утверждения придётся постоянно принимать (или не принимать) как новые и новые аксиомы. Интуиционисты быстро уразумели, что такие утверждения просто не поддаются обычной соображаловке и интуиции — а значит, после их принятия или отвержения неизбежно придётся строить дальнейшие рассуждения чисто формально, на одной голой логике. На том обе школы и примирились. (:

Благо к тому моменту уже были исторические прецеденты. Достаточно вспомнить пресловутый пятый постулат Эвклида о параллельных прямых. Он упорно не выводился и не опровергался из остальных постулатов, хотя интуитивно вроде бы выглядел справедливым. Когда Гаусс, Лобачевский и Бойяи попробовали от него отказаться, то получили неэвклидову геометрию — вполне логичную изнутри, но абсолютно бредовую снаружи. Благодарные соотечественники тут же радостно оценили её в духе „КГ/АМ“ и столь же радостно закидали авторов фекалиями. (Лобачевскому это стоило карьеры и репутации, а Бойяи сошёл с ума. Гаусс оказался хитрее, тот сразу предвидел такую реакцию и ничего не опубликовал на эту тему при жизни.) Зато потом, после работ товарища Эйнштейна, бредовая неэвклидова геометрия ВНЕЗАПНО встала на службу теории относительности — которая, на минуточку, является фундаментальной основой современных знаний о рождении и свойствах Вселенной…

Я, конечно, рассказываю популярно, но в целом всё так и было. А это длинное вступление понадобилось мне для того, чтобы подвести рассказ к истокам информатики и программирования.

Идеи гёделевских теорем основывались на том, что математическим формулам и утверждениям можно однозначно ставить в соответствие натуральные числа. Это позволило свести вопросы доказуемости к вопросам о вычислимости функций. Чем сообщество и занялось.

Для изучения вопросов вычислимости были придуманы простенькие интерпретации — этакие модели сферических вычислителей в вакууме. Простота позволяла изучать их свойства и делать выводы, а потом весь этот накопленный материал ВНЕЗАПНО оказался фундаментом новой науки — теории алгоритмов и формальных языков. Да ещё и теории искусственного интеллекта достался немаленький кусок. И математической лингвистике. Тьюринг, Пост, Марков, Хомский… наверное, они тогда и думать не могли, к чему приведут их работы…

Да-да, тот самый Алан Тьюринг, который во время Второй Мировой занимался взломом шифра „Энигмы“. В 1936 году он предложил самую знаменитую алгоритмическую абстракцию, которая так и называется — машина Тьюринга.

Это именно абстракция, хотя существует немало её юмористических изображений. (: Мне больше всего нравится вот эта:

Turing the Universe

Машина Тьюринга по сути представляет собой считывающе-записывающую головку, ездящую по бесконечной ленте и перерабатывающую содержащуюся на той информацию. Она хороша тем, что её можно легко объяснить даже десятилетним школьникам… чего автор этих строк неоднократно и делал.

Чтобы объяснения не остались абстракцией, нужен какой-то эмулятор машины. Для iPad существует очень хорошее бесплатное приложение под названием Turing the Universe — по-русски что-то вроде „Тьюрингуем Вселенную“. Оно ориентировано именно на обучение, так как позволяет создавать внутри себя нескольких пользователей, и каждому из них создавать собственные машины с различными программами.

Turing the Universe

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

Хотите верьте, хотите нет, но этого вполне достаточно, чтобы можно было выполнить любой алгоритм — лишь бы он в принципе был выполнимым. Хотя реализация может получиться весьма и весьма громоздкой. (:

Позвольте показать на примере простой задачки, традиционно рассматриваемой в этой связи. Это так называемый поиск на прямой.

Где-то на пустой ленте записана одна-единственная буква „А“. Головка машины находится в произвольном месте ленты (неизвестно по какую сторону и на каком расстоянии от этой буквы). Требуется найти букву и совместить с ней позицию головки.

Как бы вы действовали в этой ситуации? Бессмысленно идти в какую-то одну сторону — вдруг это окажется не та сторона, и поход никогда не закончится. Но можно сделать шаг вправо, затем два шага влево, потом три шага вправо и так далее, постепенно расширяя обследованную территорию в обе стороны. Рано или поздно буква найдётся.

Способ вроде бы и хорош, да не очень. У машины Тьюринга нет памяти, и она не может помнить, сколько шагов уже было сделано в какую сторону! Хм… но ведь обследованную территорию можно помечать. Наткнувшись на отмеченную границу, надо сделать за неё один шаг в прежнем направлении и, если там нет искомого, отметить этот сделанный шаг — после чего развернуться и идти в противоположную сторону, пока граница не найдётся там.

Это уже работает, и вот как выглядит соответствующая программа:

Turing the Universe

Каждая пронумерованная блямба — это и есть состояние машины, а стрелочки указывают условия перехода между ними. У каждой стрелочки отмечена пара символов в скобках. Первый объясняет, когда нужно идти по данной стрелке („-“ означает пробел, а „…“ альтернативу всем остальным случаям), второй предписывает, что сделать с лентой (записать это на неё или указанным образом подвинуться).

Если вы разберётесь в картинке (поверьте, это просто!), то быстро поймёте: программа отмечает обследованную территорию звёздочкой, а за прохождение этой территории вправо-влево отвечают петли на состояниях „2“ и „3“. Серое состояние „1“ — это конец работы.

А вот видео, иллюстрирующее работу программы:

Скорость работы можно менять, дабы наглядно видеть все переходы. Можно также делать типичные отладочные операции: паузить выполнение, выполнять программу пошагово и т.п.

Если вы разобрались и вас заинтересовало, то можете усовершенствовать программу. Пусть она „прибирает за собой“, чтобы никаких меток-звёздочек не оставалось. (:

А вот пример посложнее:

На пустой ленте записано слово, составленное из любого количества букв „А“ и „В“ в любом порядке. Головка машины указывает на произвольную букву слова. Требуется записать рядом с этим словом его копию через пробел.

Не нужно быть программистом, чтобы понять очевидное: машина должна будет находить очередную букву, подлежащую копированию, запоминать её, тащить головку в другое место и там записывать запомненное. Но… памяти опять же нету! Это значит, действия между „запомнить“ и „записать“ придётся дублировать: отдельно для „А“ и отдельно для „В“. А если букв больше двух — то и для других тоже. Вот как это выглядит:

Turing the Universe

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

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

Если вам всё ещё интересно, то вот ещё пара довольно типичных задач. (:

  • На ленте записано слово, составленное из букв „А“, „В“. Оно окружено пробелами, начальная позиция головки может быть в любой букве слова. Записать на ленту слово-перевёртыш, буквы которого идут в обратном порядке по сравнению с исходным. Сохранять исходное слово не обязательно.
  • На ленте записано через пробел два слова, каждое из которых образовано несколькими буквами „А“. Слева и справа от них лента пуста, второе слово короче первого. Записать на ленту слово из букв „А“, количество которых равно разности длин исходных слов. Сохранять исходные слова не обязательно.

Михаил Баландин специально для ipadstory.ru

Цена: Free
Скачать

Тип программы: , , (все программы по категориям для iPad)
Размер приложения в App Store: 4.7 Мб
Язык приложения: Английский
Разработчик/Издатель: OTSL Inc.
Минимальная версия iOS: 6.0

1 звезда2 звезды3 звезды4 звезды5 звёзд (Ещё никто не присваивал рейтинг статье. Будьте первым!)
Загрузка...


14 комментариев к записи: “Turing the Universe — истоки информатики”

  1. Maksim"LaFkraFt":

    Спасибо огромное за статью!!! :)

  2. Дмитрий:

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

  3. niks26:

    Спасибо, Михаил, как всегда познавательно и полезно!

  4. Alex S:

    Интересно. Но чувствуешь себя… не очень умным человеком.
    С другой стороны, “кто на что учился” :)

  5. A:

    Игра из разряда развивающих. Вакладывайте еще задачки ))

    • Michael:

      Легко. Пусть рассматриваются целые положительные числа в десятичной системе. Все они должны быть записаны без незначащих нулей.
      РАЗ. На пустой ленте записано число, начальное положение головки — в любой его цифре. Заменить исходное число таким, которое на единицу больше.
      ДВА. Всё то же самое, только результат должен быть на единицу меньше.
      ТРИ. На пустой ленте записаны через пробел два числа, начальное положение головки — в любой цифре первого числа. Заменить эти числа их суммой.

  6. Алексей:

    Давайте делиться файлами своих программ, их можно будет увидеть в разделе imported files. По крайней мере, можно отправлять по почте. willzvul@mail.ru напишите сюда, если у кого то что нибудь интересное получилось!

    • Michael:

      А что именно интересует? У меня, естественно, есть решения всех предложенных мною выше задач, есть и ещё задачи. Машина Тьюринга — вообще одна из самых популярных тем в хорошо продуманных учебных курсах. Правда, у меня многое сделано не конкретно в этом эмуляторе, а в разных программах на PC.

  7. Вступительная часть статьи очень интересная! Сама машина Тьюринга похожа на некий инструмент решения узкоспециальных математико-технических задач, возможно связанных с шифровкой/дешифровкой.

Оставить комментарий к Michael