Цитата вот отсюда http://www.rsdn.ru/forum/education/2258963.flat.aspx
«Машина Тьюринга — это абстрактная математическая модель понятия алгоритма. Все вроде бы знают что такое алгоритм, но этого недостаточно для математика. Математику необходимо изучить границы применения этого понятия, какие процессы можно описать на языке алгоритмов, а какие нельзя. Чтобы это выяснить, приходится поступать как всегда, а именно: вводить математическую абстракцию, специальный математическо-строгий объект, который является абстракцией понятия алгоритма. Вот Тьюринг предложил такую абстракцию в виде машины, исполняющей простейшие команды. Такую же абстракцию, но еще более простую, предложил Пост. Наш математик Марков придумал другую модель — нормальный алгорифм Маркова. Есть и другие абстракции, например рекурсивные функции. Все эти абстракции описывают одно и тоже явление — алгоритм. Доказано, что они эквивалентны, т.е. одно определение влечет за собой другое и наоборот. Вопрос, который остается открытым: действительно ли эти модели описывают все из того, что мы считаем алгоритмом? В настоящее время примеров обратного не было найдено. Именно об этом и говорит тезис Черча, в смысле что описывают. В теории таким образом определенных алгоритмов четко выяснены границы применения данного понятия для описания явлений окружающей нас действительности, что собственно и было целью теории. Зачем это нужно программисту? В повседневной работе, конечно, вряд ли понадобится. Тем более, если программист и с алгоритмами то по особому счету не сталкивается, так формы программирует и все. В этом случае, наверное, и не нужно ничего такого изучать. Достаточно закончить техникум или профтехучилище и научится работе с командной строкой и клепанием формочек. Вон в Индии таки людей и образовывают, и ничего, живут же люди и деньги зарабатывают. Но для решения серьезных задач такое образование не подходит, необходим более широкий взгляд на проблему, знание методологии. Такое знание и понимание дается только одним: широким образованием. образование — это не тупое поглощение знаний, т.е. закончивший Университет тем только и отличается от закончившего Техникум, что "знает больше". Нет, образование — это прежде всего понимание взаимосвязей в казалось бы совсем не относящихся друг к другу явлениях, выработка умения видеть в казалось бы разных процессах одни и те же основания. Все это дается академическим образованием. И машина Тьюринга является частью такого образования. В общем, это из той же оперы зачем программисту иметь представление об истории философии или, например, о функциональном анализе.»
Показаны сообщения с ярлыком Turing. Показать все сообщения
Показаны сообщения с ярлыком Turing. Показать все сообщения
четверг, 3 марта 2011 г.
Зачем нужна машина Тьюринга
Щас я вам объясню, для чего нужно прочитать о том, что такое машина Тьюринга. Прочитать, что это такое, можно везде. А вот зачем она была создана, непонятно. Поэтому... ссылаюсь на слова Лешки, пересказываю, так сказать.
Скажем, давным-давно... А на самом деле до создания машины Тьюринга создавались машины для выполнения различных действий. Например, нужно взять логарифм, нука, а давайте-ка склепаем машинку, которая будет считывать число и брать логарифм. Или нужно, скажем, два числа сложить — вот вам и машина для сложения двух чисел. Да и сейчас существуют такие машины, например, калькуляторы. Что они могут делать? Складывать, вычитать, умножать, а инженерные — даже брать косинус или синус. Получается эти тупые машинки, кроме как записанные в них действия, исполнять ничего не могли и не могут.
Так вот было бы очень интересно создать такую машину, которая бы считывала не числа и не символы, а алгоритм, и выполняла бы его, то есть создать программируемую машину. Вот этим и занялся Тьюринг (скажу, что кроме тьюринговских таких абстракций много). И придумал модель такой машины. Оказалось, что для того, чтобы выполнять сложные алгоритмы всего-то нужна каретка, бесконечная лента, ну и возможность изменять значения, записанные на ленте и передвигаться по ней. Получается, что эта абстракция фактически может быть превращена в настоящую машину, единственное, с тем ограничением, что обеспечить машину бесконечной лентой мы не можем, но зато можно сделать очень длинную ленту ;)
Отступление. Собственно, как работает машина Тьюринга, рассказывать ни к чему, как я уже сказала, это можно найти очень легко. Поэтому будем полагать, что вы уже знаете, как она работает.
Ну какие-то просты алгоритмы машина Тьюринга выполняет, это бесспорно. Но как насчет сложненьких? А, например, как бы организовать цикл с помощью МТ? Или как сообразить ветвление? Оказывается, существуют теоремы, которые доказывают то, что МТ может выполнять циклы и ветвления, что говорит нам, что с помощью очень простого механизма можно составлять программы из простых блоков типа ветвления и циклов, а значит, можно запрограммировать все, что может быть запрограммировано. И тут по идее должен идти кусок объяснения того, что существуют и невычислимые функции, а следовательно, неразрешимые задачи, и эти задачи нельзя решить с помощью МТ. Вот как.
Но круче машины Тьюринга никто ничего не придумал, поэтому все языки программирования, которыми мы сейчас пользуемся могут запрограммировать не больше, чем машина Тьюринга. Отсюда появилось понятие полноты по Тьюрингу, что означает, что язык (или что-либо другое) полный по Тьюрингу в том случае, если на нем можно записать все алгоритмы, работающие на машине Тьюринга. И доказать, что язык — полный по Тьюрингу можно, написав на нем эмулятор машины Тьюринга. Вот такие пироги.
С точки зрения математики пост — фуфло, зато понятно, нафига нам оказалась нужна машина Тьюринга. Ну и вообще-то писать алгоритмы под эту машину — интересная головоломка. Верю тем, кто говорит, что после программирования exp(x) на машине Тьюринга, он действительно понял, что такое алгоритм. Пока не пробовала, но это интересная задачка.
Комментте.
Скажем, давным-давно... А на самом деле до создания машины Тьюринга создавались машины для выполнения различных действий. Например, нужно взять логарифм, нука, а давайте-ка склепаем машинку, которая будет считывать число и брать логарифм. Или нужно, скажем, два числа сложить — вот вам и машина для сложения двух чисел. Да и сейчас существуют такие машины, например, калькуляторы. Что они могут делать? Складывать, вычитать, умножать, а инженерные — даже брать косинус или синус. Получается эти тупые машинки, кроме как записанные в них действия, исполнять ничего не могли и не могут.
Так вот было бы очень интересно создать такую машину, которая бы считывала не числа и не символы, а алгоритм, и выполняла бы его, то есть создать программируемую машину. Вот этим и занялся Тьюринг (скажу, что кроме тьюринговских таких абстракций много). И придумал модель такой машины. Оказалось, что для того, чтобы выполнять сложные алгоритмы всего-то нужна каретка, бесконечная лента, ну и возможность изменять значения, записанные на ленте и передвигаться по ней. Получается, что эта абстракция фактически может быть превращена в настоящую машину, единственное, с тем ограничением, что обеспечить машину бесконечной лентой мы не можем, но зато можно сделать очень длинную ленту ;)
Отступление. Собственно, как работает машина Тьюринга, рассказывать ни к чему, как я уже сказала, это можно найти очень легко. Поэтому будем полагать, что вы уже знаете, как она работает.
Ну какие-то просты алгоритмы машина Тьюринга выполняет, это бесспорно. Но как насчет сложненьких? А, например, как бы организовать цикл с помощью МТ? Или как сообразить ветвление? Оказывается, существуют теоремы, которые доказывают то, что МТ может выполнять циклы и ветвления, что говорит нам, что с помощью очень простого механизма можно составлять программы из простых блоков типа ветвления и циклов, а значит, можно запрограммировать все, что может быть запрограммировано. И тут по идее должен идти кусок объяснения того, что существуют и невычислимые функции, а следовательно, неразрешимые задачи, и эти задачи нельзя решить с помощью МТ. Вот как.
Но круче машины Тьюринга никто ничего не придумал, поэтому все языки программирования, которыми мы сейчас пользуемся могут запрограммировать не больше, чем машина Тьюринга. Отсюда появилось понятие полноты по Тьюрингу, что означает, что язык (или что-либо другое) полный по Тьюрингу в том случае, если на нем можно записать все алгоритмы, работающие на машине Тьюринга. И доказать, что язык — полный по Тьюрингу можно, написав на нем эмулятор машины Тьюринга. Вот такие пироги.
С точки зрения математики пост — фуфло, зато понятно, нафига нам оказалась нужна машина Тьюринга. Ну и вообще-то писать алгоритмы под эту машину — интересная головоломка. Верю тем, кто говорит, что после программирования exp(x) на машине Тьюринга, он действительно понял, что такое алгоритм. Пока не пробовала, но это интересная задачка.
Комментте.
пятница, 28 января 2011 г.
Подписаться на:
Сообщения (Atom)