Введение в машину Тьюринга, алгоритмы

ВВЕДЕНИЕ В МАШИНУ ТЬЮРИНГА, АЛГОРИТМЫ

И ДЕЙСТВУЮЩИЙ ИМИТАТОР МТ

На исходе 30-х годов ХХ века вычислительная техника, основанная на принципах механики и дополненная электрическими двигателями и электромагнитами (для увеличения быстродействия), приблизилась к пределу своего совершенства.

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

В этот же период значительного развития  в передовых странах мира достигли новые отрасли знания, техники и технологии: электротехника связи (телеграфии и телефонии) и радиотехника, что привело к появлению новых элементов и схемных решений, которые позднее легли в основу первых релейных вычислительных машин - Марк-I (1944, США), Марк-II (1947, США) и первой электронной вычислительной машины – ЭНИАК (1946, США).

Перевод вычислительной техники на электронную основу мог дать возрастание скорости вычислений в сотни и тысячи раз и расширить объём и круг решаемых задач.

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

Накопленный человечеством за тысячелетия опыт в области счета - от загибания пальцев на руках и зарубок на дощечках и палочках, плетения вампумов, выдавливания символов на глиняных табличках, перекладывания камешков на абаке и перемещения косточек на счётах, взаимодействия стержней, пружин, колес, валиков, зубчатых планок и рычагов в конструкциях Паскаля, Лейбница, Беббиджа, Чебышева, Однера (1874), логарифмические шкалы и линейки – всё это напрямую не переводилось на язык электронных схем.

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

Родоначальником этой теории стал талантливый английский учёный – математик, логик, криптограф Алан Метисон Тьюринг.

28 мая 1936 года он передал свою работу «О вычислимых числах» в редакцию издания «Труды Лондонского математического общества», которая была опубликована в конце 1936 года.

Тьюрингом было дано абстрактное понятие вычислительной машины при анализе понятия эффективно вычислимой (т.е. вычислимой при помощи некоторого алгоритма) функции.

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

 

 

I. УСТРОЙСТВО И ПРИНЦИП РАБОТЫ МАШИНЫ ТЬЮРИНГА

II. НЕКОТОРЫЕ ПРАКТИЧЕСКИЕ ПРИМЕРЫ ПРОГРАММ (АЛГОРИТМОВ) ДЛЯ МАШИНЫ ТЬЮРИНГА

ЗАКЛЮЧЕНИЕ

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

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

    Машина Тьюринга была и остаётся до нашего времени самым универсальным и доступным средством алгоритмирования за более чем 80-летнюю историю своего существования.

    За кажущейся её простотой скрыты далеко не исчерпанные возможности.

 

М.В. Селицкая

2012 год

 

СПИСОК ЛИТЕРАТУРЫ

 

 

1. Данильченко И. А. Цифровая вычислительная машина // Энциклопедия современной техники. Автоматизация производства и промышленная электроника. Москва: Советская энциклопедия, 1965, т. 4, С. 293-306.

2. Гастев Ю. А. Тьюринга машина // Энциклопедия современной техники. Автоматизация производства и промышленная электроника. Москва: Советская энциклопедия, 1965, т. 4, С. 109-111.

3. Гофман В. Э., Хоменко А. Д. Delphi. Быстрый старт.  СПб.: БХВ-Петербург, 2003.

4. Трахтенброт Б. А. Алгоритмы и вычислительные автоматы. М.: Сов. радио, 1974.

5. http://ru.wikipedia.org

 

 

ВВЕДЕНИЕ В МАШИНУ ТЬЮРИНГА, АЛГОРИТМЫ

И ДЕЙСТВУЮЩИЙ ИМИТАТОР МТ

На исходе 30-х годов ХХ века вычислительная техника, основанная на принципах механики и дополненная электрическими двигателями и электромагнитами (для увеличения быстродействия), приблизилась к пределу своего совершенства.

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

В этот же период значительного развития  в передовых странах мира достигли новые отрасли знания, техники и технологии: электротехника связи (телеграфии и телефонии) и радиотехника, что привело к появлению новых элементов и схемных решений, которые позднее легли в основу первых релейных вычислительных машин - Марк-I (1944, США), Марк-II (1947, США) и первой электронной вычислительной машины – ЭНИАК (1946, США).

Перевод вычислительной техники на электронную основу мог дать возрастание скорости вычислений в сотни и тысячи раз и расширить объём и круг решаемых задач.

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

Накопленный человечеством за тысячелетия опыт в области счета - от загибания пальцев на руках и зарубок на дощечках и палочках, плетения вампумов, выдавливания символов на глиняных табличках, перекладывания камешков на абаке и перемещения косточек на счётах, взаимодействия стержней, пружин, колес, валиков, зубчатых планок и рычагов в конструкциях Паскаля, Лейбница, Беббиджа, Чебышева, Однера (1874), логарифмические шкалы и линейки – всё это напрямую не переводилось на язык электронных схем.

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

Родоначальником этой теории стал талантливый английский учёный – математик, логик, криптограф Алан Метисон Тьюринг.

28 мая 1936 года он передал свою работу «О вычислимых числах» в редакцию издания «Труды Лондонского математического общества», которая была опубликована в конце 1936 года.

Тьюрингом было дано абстрактное понятие вычислительной машины при анализе понятия эффективно вычислимой (т.е. вычислимой при помощи некоторого алгоритма) функции.

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