Н О В О С Т И

IEEE  COMPUTER  SOCIETY

The world's leading membership organization for computing professionals

English facebook twitter Новости IEEE События Программы Архив The Day Вопросы

ПОЧЕМУ НАДО «ЗНАТЬ» МАШИНУ ТЮРИНГА***

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

Из рецензии читателя на литературное творчество
 в Интернете. Ст.-Петербург. 1997 г.

Беда в том, что в отличие от высокообразованных критиков, разбирающих литературное творчество графоманов творящих в Интернете, большинство нынешних программистов не изучало ни машину Тюринга, ни машину Поста, ни нормальные алгорифмы Маркова.

Однажды, давным-давно, еще в прошлом столетии, а точнее 4 апреля 1978 года мне довелось присутствовать на заседании Ученого совета Вычислительного центра АН СССР. Шла защита диссертации на соискание ученой степени кандидата физико-математических наук.
Не помню точно тему, что-то связанное с искусственным интеллектом.
В процессе обсуждения диссертации возник вопрос, а может ли представленная диссертация претендовать на соискание степени кандидата физико-математических наук. Теорем нет, а есть какие-то эвристические оценки действий, совершаемых «искусственным интеллектом» и есть программа, написанная на языке ЛИСП, которая позволяет определять действия «искусственного интеллекта».

Надо сказать, что Вычислительный центр Академии наук, несмотря на свое прикладное название, был отнюдь не счетной фабрикой, обслуживающих другие институты академии. Это был  (и есть) первоклассный научно-исследовательский институт, в котором в те годы работали такие выдающиеся математики как академики А.Дородницын, Ю.Журавлев, П.Краснощеков, А.Марков, Н.Моисеев, А.Петров, Г.Поспелов, В.Румянцев. Это далеко не полный список имен, которыми может гордиться российская наука и которые работали в то время в ВЦ АН.

Так вот, между членами ученого совета возникла оживленная дискуссия о правомерности защиты диссертации на степень кандидата физико-математических наук, а не на степень кандидата технических наук. Степень кандидата технических наук присуждается за работы, в которой основой диссертации является решения прикладных задач.
Мнение разделились и защита диссертации оказалась под вопросом. Решающим оказалось мнение, высказанное директором института академиком А.Дородницыным. Он высказал тезис, что каждую программу можно рассматривать как теорему о возможности решения некоторой задачи. И если программа работает, то можно утверждать, что теорема доказана
.
Этот тезис был поддержан А.Марковым, который предложил только уточнить тезис. В большинстве случаев невозможно определить, всегда ли программа дает правильный ответ. Поэтому предлагалось принять следующее утверждение: каждая программа является теоремой, справедливость которой доказана для тех случаев, в которых программа дает правильный ответ.

А.Марков – великий русский математик. Для нас он был живой классик. Именно он дал одно из наиболее распространенных определений понятия алгоритм, которое получило его имя - нормальные алгорифмы Маркова.
Тезис Дородницына - Маркова единогласно был принят Ученым советом как аксиома, постулат. Диссертация была успешно защищена, а соискатель получил искомую степень кандидата физико-математических наук.

Это один из примеров, почему надо знать определение понятия алгоритм.

Почему надо знать, что такое машина Тюринга, что такое нормальный алгорифм Маркова. Алгорифм – так писал автор - Андрей Андреевич Марков, который считал, что правила чтения иностранных слов должны быть единообразны. Если мы пишем арифметика, а не аритметика, то правильное написание – алгорифм.

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


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

Почему надо «знать» машину Тюринга?
Потому, что это - Начала математики, в нем вводится понятие алгоритм. Помните знаменитый тезис Тюринга: всякий алгоритм может быть реализован соответствующей машиной. Этот тезис является формальным определением алгоритма. Он позволяет доказывать существование или несуществование алгоритмов, описывая соответствующие машины Тюринга или доказывая невозможность их построения.
Не знать машину Тюринга – значит не знать математики.

Потому, что это - Начала программирования, в нем вводятся понятия алгоритм. К сожалению, у многих программистов тюринговское определение алгоритма заменяется на своё, более близкое: алгоритм – эта программа, которую пишу Я.
Но если вы не знаете, что такое алгоритм, то как вы можете говорить, что вы запрограммировали алгоритм решения какой-либо задачи.

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

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

 

 587

+

 

 104

 

________

 791

7 + 4 – мы ведь реально не производим вычисления, не прибавляем как школьники первого класса к 7 палочкам еще 4 палочки. Нет, мы знаем что 7+4 = 1 и 1 «в памяти».

Т.е. ее надо перенести влево как это и делается в машине Тюринга. Точно также мы складывая 8 и 0 получаем 8, но так как мы находимся в особом состоянии, которое называется «перенос единицы» мы знаем, что в нижней строке надо записать 9.
Вместо реальных вычислений производится формальная замена одних символов другими. Но интерпретировать записанную последовательность символов «791» как число или как текст или другим образом зависит целиком от нас. 
Семантическая интерпретация последовательности символов целиком зависит от контекста, от наших соглашений с другими людьми. Например, FF  можно интерпретировать как пару букв латинского алфавита, а можно как число 255, записанное в шестнадцатиричной системе. Так что считать ли FF частью номера автомобиля или числом зависит только от нас.

Еще один пример. Вспомним, что А.Марков дал другое определение алгоритма. Со школьной скамьи мы знаем, что 7х8 = 56. Если кто забыл об этом, то можно освежить свою память, посмотрев на обложку школьной тетради. Здесь имеет место употребления нормальных алгоритмов Маркова. Цепочка символов 7х8 заменяется на цепочку 56. Никаких действий не происходит.


Почему надо «знать» машину Тюринга? Потому, что Тюринг показал, что существуют задачи, которые алгоритмически неразрешимы. Первоначально это вызвало шок и непринятия такого «скверного» определения понятия алгоритм. Были предприняты многочисленные, но безуспешные попытки его «улучшить». Однако еще до Тюринга Геделем была сформулирована теорема о неполноте формальных исчислений.
Тюринг показал на примерах, что существуют задачи, для которых применение формальных методов требует бесконечно много времени для решения, т.е. решения практически нет. В то время как человек решает эти задачи очень просто. Это имеет важное практическое значение  для разработчиков систем искусственного интеллекта. Так как определение алгоритма по Тюрингу (или Маркову) говорит, фактически, о невозможности создания систем искусственного интеллекта, которые были бы способны заменить человека. По крайней мере, пока не возникнет новая математика или не появятся биороботы, в которых мозг человека или другого существа будет объединен с возможностями большой вычислительной машины. (а работы в этом направлении уже ведутся).

К сожалению, во время вступительных экзаменов в аспирантуру и кандидатских экзаменах по специальности часто приходится слышать невразумительные ответы о машине Тюринга и нормальных алгоритмах. Экзаменуемые студенты и аспиранты ссылаются обычно на то, что по жизни они им не нужны. Это не так. Машина Тюринга играет в понимании математики, в умении квалифицированно решать задачу такую же фундаментальную роль, как и постулаты Евклида. Естественно, что прораб на стройке может не знать аксиом Евклида, они ему не нужны. Но я уверен, что архитектор всегда помнит о них (не использует в работе, но знает, чувствует их), т.к. должен учитывать геометрию (по крайней мере, начертательную) при проектировании и строительстве. Чтобы безопасно нам было жить и ходить на развлечения.
Точно также и абитуриенты гуманитарных вузов могут не помнить постулаты Евклида, но я уверен, что, не зная и не понимая их сущности, невозможно поступить ни на мехмат МГУ, ни на физтех, ни в любой другой приличный университет или институт.

Для тех, кого не убедило, что «знать» машину Тюринга очень полезно и практично – это называется общая грамотность – тест. Вот задача, которую действующий программист должен решить за 5 минут. Любой специалист, связанный с программированием, за 15 минут. Любой культурный человек за 1 час.

Наверняка каждый сталкивался с ситуацией, когда в письме, полученном по электронной почте, русский текст «не читается». Используешь какую-либо из готовых программ перекодировки – безуспешно.

Как написать программу, которая будет способна декодировать текст, записанный в произвольной кодировке, и приводить его к «читабельному» виду.

5 минут. Время пошло! Дать подсказку?
Она проста. В составе Российской академии наук есть Институт русского языка. Подумайте, что исследует институт с таким ёмким названием.
Проверить решение можете
здесь.

*** Должен признать, что чаще всего в русской литературе применяется другое написание фамилии Turing - Тьюринг. Но оно как-то режет глаз. Никто ведь не пишет о династии Тьюдоров, но пишут о династии Тюдоров

Вернуться...