Яндекс.Метрика

четверг, 3 марта 2011 г.

И еще немного про МТ

Цитата вот отсюда http://www.rsdn.ru/forum/education/2258963.flat.aspx

«Машина Тьюринга — это абстрактная математическая модель понятия алгоритма. Все вроде бы знают что такое алгоритм, но этого недостаточно для математика. Математику необходимо изучить границы применения этого понятия, какие процессы можно описать на языке алгоритмов, а какие нельзя. Чтобы это выяснить, приходится поступать как всегда, а именно: вводить математическую абстракцию, специальный математическо-строгий объект, который является абстракцией понятия алгоритма. Вот Тьюринг предложил такую абстракцию в виде машины, исполняющей простейшие команды. Такую же абстракцию, но еще более простую, предложил Пост. Наш математик Марков придумал другую модель — нормальный алгорифм Маркова. Есть и другие абстракции, например рекурсивные функции. Все эти абстракции описывают одно и тоже явление — алгоритм. Доказано, что они эквивалентны, т.е. одно определение влечет за собой другое и наоборот. Вопрос, который остается открытым: действительно ли эти модели описывают все из того, что мы считаем алгоритмом? В настоящее время примеров обратного не было найдено. Именно об этом и говорит тезис Черча, в смысле что описывают. В теории таким образом определенных алгоритмов четко выяснены границы применения данного понятия для описания явлений окружающей нас действительности, что собственно и было целью теории. Зачем это нужно программисту? В повседневной работе, конечно, вряд ли понадобится. Тем более, если программист и с алгоритмами то по особому счету не сталкивается, так формы программирует и все. В этом случае, наверное, и не нужно ничего такого изучать. Достаточно закончить техникум или профтехучилище и научится работе с командной строкой и клепанием формочек. Вон в Индии таки людей и образовывают, и ничего, живут же люди и деньги зарабатывают. Но для решения серьезных задач такое образование не подходит, необходим более широкий взгляд на проблему, знание методологии. Такое знание и понимание дается только одним: широким образованием. образование — это не тупое поглощение знаний, т.е. закончивший Университет тем только и отличается от закончившего Техникум, что "знает больше". Нет, образование — это прежде всего понимание взаимосвязей в казалось бы совсем не относящихся друг к другу явлениях, выработка умения видеть в казалось бы разных процессах одни и те же основания. Все это дается академическим образованием. И машина Тьюринга является частью такого образования. В общем, это из той же оперы зачем программисту иметь представление об истории философии или, например, о функциональном анализе.»

1 комментарий:

  1. > Наш математик Марков придумал другую модель — нормальный алгорифм Маркова. Есть и другие абстракции, например рекурсивные функции.

    На текущий момент полнота по Тьюрингу доказано для такого разнообразия не то чтобы моделей, а вообще мат. объектов, что диву даешься. Из совсем неожиданнх — это диофантовы уравнения! Матьясевич в 1970 г. доказав неразрешимость 10-й проблемы Гильберта получил это как побочный эффект.

    У Босса в его книжке «от Диофанта до Тьюринга» об этом написано.

    ОтветитьУдалить