Файл: Машина Тьюринга.docx

ОБЛАСТНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

«ТОМСКИЙ ЭКОНОМИКО-ПРОМЫШЛЕННЫЙ КОЛЛЕДЖ»

Реферат

По элементам высшей математике

На тему:

«Машина Тьюринга»

Выполнил:

Студент группы 1992с

__________/ Куница Д.В.

«____» ___________ 2022г.
Проверил:

Преподаватель

_________/ Максимова Е.В.

«____» __________2022г.


Томск 2022

Оглавление

Введение

Алан Матисон Тьюринг (23 июня 1912 - 7 июня 1954) - английский математик, логик, криптограф, оказавший существенное влияние на развитие информатики. Кавалер Ордена Британской империи (1945). Предложенная им в 1936 году абстрактная вычислительная «Машина Тьюринга» позволила формализовать понятие алгоритма и до сих пор используется во множестве теоретических и практических исследований.

В своей работе Тьюринг предложил проект простого устройства, имеющего все основные свойства современной информационной системы: программное управление, память, и пошаговый способ действий. Эта воображаемая машина, получившая название «машины Тьюринга», используется в теории автоматов или компьютеров. Когда Тьюринг из США возвратился в Англию, началась вторая мировая война. Одним из важнейших вооружений этой войны была ЭВМ «Колосс» по проекту «Ультра», начавшая в 1943 году взламывать сверхсложные шифры немцев. Работа этой системы значительно помогла в борьбе с Германией и её союзниками.

Создание машины Тьюринга

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

---

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

Состав Машины Тьюринга

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

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

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

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

Принцип работы машины Тьюринга

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

---

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

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

• 
  Свойство дискретности. Цифровое устройство выполняет переход к очередному этапу n+1 лишь после полного завершения предыдущего. Каждый завершенный шаг определяет, каким будет следующий.
  
• 
  Свойство понятности. Машина осуществляет лишь одну операцию для выбранной ячейки. Она записывает алфавитный символ и выполняет одно перемещение в указанную сторону.
  
• 
  Свойство детерминированности. Всем позициям в машине сопоставляется только один вариант осуществления задаваемой схемы, и на всех шагах операции и их очерёдность осуществления строго определены.
  
• 
  Свойство результативности. Окончательный итог на каждом шаге вычисляет машина Тьюринга. Программа работает согласно заданному алгоритму и за не бесконечное количество выполненных этапов доходит до состояния.
  
• 
  Свойство массовости. Каждой машине сопоставлен набор допустимых слов, которые входят в алфавит.
  

Функции Машины Тьюринга

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

Множеством рациональных или натуральных чисел и слов в не бесконечном алфавитном наборе N для устройства Тьюринга может быть рассмотрен набор множеств B, а именно слова в границах бинарного кодового алфавита B = (0, 1). Кроме того, в итоге расчётов необходимо учесть «неопределённую» величину, возникающую при повисании выполнения алгоритма. Для осуществления функции требуется присутствие формализованного языка в не бесконечном алфавите и условие, что задача определения корректности описаний в принципе может быть решена.

Программа для Машины Тьюринга

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

---

Интересный факт

Когда настали трудные времена Тьюринг занимался не только теорией, но и практически участвовал в разных важных проектах. Он с коллегами расшифровал коды немецкой армии – это известная история. Там использовались шифровальные машины «Энигма», которые пытались расшифровать сначала польские криптографы, а потом английские – при активном участии Тьюринга, им это удалось. А после войны Тьюринг уже строил реальную электронную вычислительную машину. Хотя прямой связи с его теоретическими работами не было, но явно это было продолжением той же самой деятельности. Так что хорошая теория — вещь очень практичная, и не надо бояться того, что теоретические работы окажутся бесполезными.

Список литературы

1. 
   Гэри, М. Вычислительные машины и трудно решаемые задачи / М. Гэри, Д. Джонсон. - М.: [не указано], 1982. - 537 c.
   
2. 
   Зубков. Из чего все машины сделаны? / Зубков, Васильевич Борис. - М.: Малыш, 1986. - 712 c.
   
3. 
   Павлидис, Т. Алгоритмы машинной графики и обработки изображений / Т. Павлидис. - М.: [не указано], 1986. - 286 c.
   
4. 
   Роджерс, Д. Алгоритмические основы машинной графики / Д. Роджерс. - М.: [не указано], 1989. - 503 c.
   
5. 
   Эпштейн, Г.Г. Динамо-машина / Г.Г. Эпштейн, П.В. Албычев, А.А. Чикин. - М.: Научное книгоиздательство, 1983. - 176 c.
   

---