Машина тьюринга реферат заключение

Обновлено: 05.07.2024

Введение
1. Описание машины Тьюринга
1.1 Свойства машины Тьюринга как алгоритма
2. Сложность алгоритмов
2.1 Сложность проблем
3. Машина Тьюринга и алгоритмически неразрешимые проблемы
4. Реализация машины Тьюринга
5. Практическая часть
Заключение
Список литературы

Вложенные файлы: 1 файл

курсач по мат логике Машина Тьуринга.doc

Министерство образования и науки Российской Федерации

Чебоксарский политехнический институт (филиал)

Кафедра высшей и прикладной математики

студент 2 курса (в/в)

Майоров Александр Геннадьевич

учебный шифр 612256

ст. преподаватель Павлова Н.А

1. Описание машины Тьюринга

1.1 Свойства машины Тьюринга как алгоритма

2. Сложность алгоритмов

2.1 Сложность проблем

3. Машина Тьюринга и алгоритмически неразрешимые проблемы

4. Реализация машины Тьюринга

5. Практическая часть

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

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

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

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

1. Описание машины Тьюринга

Алан Тьюринг (Turing) в 1936 году опубликовал в трудах Лондонского математического общества статью "О вычислимых числах в приложении к проблеме разрешения", которая наравне с работами Поста и Черча лежит в основе современной теории алгоритмов.

Предыстория создания этой работы связана с формулировкой Давидом Гильбертом на Международном математическом конгрессе в Париже в 1900 году неразрешенных математических проблем. Одной из них была задача доказательства непротиворечивости системы аксиом обычной арифметики, которую Гильберт в дальнейшем уточнил как "проблему разрешимости" – нахождение общего метода, для определения выполнимости данного высказывания на языке формальной логики.

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

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

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

Формально машина Тьюринга может быть описана следующим образом. Пусть заданы:

конечное множество состояний – Q, в которых может находиться машина Тьюринга;

конечное множество символов ленты – Г;

функция δ (функция переходов или программа), которая задается отображением пары из декартова произведения Q x Г (машина находится в состоянии qi и обозревает символ gi) в тройку декартова произведения Q х Г х (машина переходит в состояние qi, заменяет символ gi на символ gj и передвигается влево или вправо на один символ ленты) – Q x Г-->Q х Г х

один символ из Г-->е (пустой);

подмножество Σ є Г – -> определяется как подмножество входных символов ленты, причем е є (Г – Σ);

одно из состояний – q0 є Q является начальным состоянием машины.

Решаемая проблема задается путем записи конечного количества символов из множества Σ є Г – Si є Σ на ленту:

после чего машина переводится в начальное состояние и головка устанавливается у самого левого непустого символа (q0,w) –, после чего в соответствии с указанной функцией переходов (qi,Si) – ->(qj,Sk, L или R) машина начинает заменять обозреваемые символы, передвигать головку вправо или влево и переходить в другие состояния, предписанные функций переходов.

Остановка машины происходит в том случае, если для пары (qi,Si) функция перехода не определена.

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

1.1 Свойства машины Тьюринга как алгоритма

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

Дискретность. Машина Тьюринга может перейти к (к + 1) – му шагу только после выполнения каждого шага, т.к именно каждый шаг определяет, каким будет (к + 1) – й шаг.

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

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

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

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

2. Сложность алгоритмов

Сложность алгоритма определяется вычислительными мощностями, необходимыми для его выполнения. Вычислительная сложность алгоритма часто измеряется двумя параметрами: Т (временная сложность) и S (пространственная сложность, или требования к памяти). И Т, и S обычно представляются в виде функций от n, где n – это размер входных данных. (Существую и другие способы измерения сложности: количество случайных бит, ширина канала связи, объем данных и т.п.)

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

Эта нотация позволяет увидеть, как объем входных данных влияет на требования к времени и объему памяти. Например, если Т= О(n), то удвоение входных данных удвоит и время выполнения алгоритма. Если Т=О(2n), то добавление одного бита к входным данным удвоит время выполнения алгоритма.

Обычно алгоритмы классифицируются в соответствии с их временной или пространственной сложностью. Алгоритм называют постоянным, если его сложность не зависит от n: 0(1). Алгоритм является линейным, если его временная сложность О(n). Алгоритмы могут быть квадратичными, кубическими и т.д. Все эти алгоритмы – полиноминальны, их сложность – О(m), где m – константа. Алгоритмы с полиномиальной временной сложностью называются алгоритмами с полиномиальным временем

Алгоритмы, сложность которых равна О(tf(n)), где t – константа, большая, чем 1, a f(n) – некоторая полиномиальная функция от n, называются экспоненциальными. Подмножество экспоненциальных алгоритмов, сложность которых равна О(сf(n)), где с – константа, a f(n) возрастает быстрее, чем постоянная, но медленнее, чем линейная функция, называется суперполиноминальным.

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

С ростом n временная сложность алгоритмов может стать настолько огромной, что это повлияет на практическую реализуемость алгоритма.

При условии, что единицей времени для нашего компьютера является микросекунда, компьютер может выполнить постоянный алгоритм за микросекунду, линейный – за секунду, а квадратичный – за 11.6 дня. Выполнение кубического алгоритма потребует 32 тысяч лет, что в принципе реализуемо, компьютер, конструкция которого позволила бы ему противостоять следующему ледниковому периоду, в конце концов получил бы решение. Выполнение экспоненциального алгоритма тщетно, независимо от экстраполяции роста мощи компьютеров, параллельной обработки или контактов с инопланетным суперразумом.

Взглянем на проблему вскрытия алгоритма шифрования грубой силой. Временная сложность такого вскрытия пропорциональна количеству возможных ключей, которое экспоненциально зависит от длины ключа. Если n – длина ключа, то сложность вскрытия грубой силой равна 0(2n). Сложность вскрытия грубой силой при 56-битовом ключе составляет 256, а при 112-битовом ключе – 2112. В первом случае вскрытие возможно, а во втором – нет.

2.1 Сложность проблем

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

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

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

Задачи можно разбить на классы в соответствии со сложностью их решения. Вот важнейшие из них и предполагаемые соотношения между ними: P

Реферат на тему: МАШИНА ТЬЮРИНГА Выполнили Руководитель:Мистер Х | Москва 2013 ОГЛАВЛЕНИЕ ВВЕДЕНИЕ 3 ОПИСАНИЕ МАШИНЫ ТЬЮРИНГА 4 МАШИНА ТЬЮРИНГА КАК УНИВЕРСАЛЬНЫЙ ИСПОЛНИТЕЛЬ 7 ПРИМЕРЫ МАШИНЫ ТЬЮРИНГА 8 АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ 9 ПРИМЕРЫ СОСТАВЛЕНИЯ ПРОГРАММ ДЛЯ МТ 11 ЗАКЛЮЧЕНИЕ 14 СПИСОК ЛИТЕРАТУРЫ 15 ВВЕДЕНИЕ Развитие теории алгоритмов начинается с доказательства К. Геделем теорем о неполноте формальных систем, включающих арифметику, первая.

3134 Слова | 13 Стр.

машина

Реферат: Машина Тьюринга Содержание Введение. 2 1. Описание машины Тьюринга. 3 1.1 Свойства машины Тьюринга как алгоритма. 5 2. Сложность алгоритмов. 7 2.1 Сложность проблем… 9 3. Машина Тьюринга и алгоритмически неразрешимые проблемы… 12 Заключение. 16 Список литературы… 18 Введение Машина Тьюринга — это оченьпростое вычислительное устройство. Она состоит из ленты бесконечной длины,разделенной на ячейки, и головки, которая перемещается вдоль ленты и способначитать и записывать символы.

1515 Слова | 7 Стр.

Распознающие машины Тьюринга

5256 Слова | 22 Стр.

Алгоритмическая машина Тьюринга

3727 Слова | 15 Стр.

РЕФЕРАТ ИТПД

4619 Слова | 19 Стр.

Реферат по информатике

3080 Слова | 13 Стр.

Реферат искусственный интеллект

Министерство образования и науки РФ Государственное образовательное учреждение Высшего профессионального образования Кафедра философии Реферат Проблема толкования искусственного интелекта Выполнил(и) студенты Проверил: Дата_____________ Оценка___________ Подпись__________ 2010 Содержание: .

4491 Слова | 18 Стр.

Машина Поста

Технический лицей Шевченковского района Реферат на тему: “Теория алгоритмов. Машина Поста.” Работу подготовила: .

1933 Слова | 8 Стр.

РЕФЕРАТ иис

5443 Слова | 22 Стр.

Фон Неймановская машина

2078 Слова | 9 Стр.

Реферат ИКТ

на тему: История появления информационных технологий по предмету: Инфокоммуникационные технологии обучения РЕФЕРАТ фамилия имя отчество Ф.И.О.(руководителя) Содержание Введение 3 1. Развитие информационных технологий в период с XIV по XVIII век 5 2. История развития информационных технологий с XVIII по XX век 10 Заключение 23 Список использованной литературы 24 Введение В истории человечества можно выделить несколько этапов, которые человеческое общество последовательно.

5031 Слова | 21 Стр.

реферат информ

1232 Слова | 5 Стр.

Реферат

2211 Слова | 9 Стр.

Реферат ЗБСД 141

2274 Слова | 10 Стр.

Реферат

901 Слова | 4 Стр.

реферат по информатике

2885 Слова | 12 Стр.

Реферат по философии науки на тему "Человек и виртуальная реальность"

6554 Слова | 27 Стр.

Реферат

2749 Слова | 11 Стр.

Реферат База данных

3062 Слова | 13 Стр.

Реферат Дискретная математика

4015 Слова | 17 Стр.

Реферат

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ МАРИУПОЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ГРЕЧЕСКОЙ ФИЛОЛОГИИ Реферат на тему: История возникновения и перспективы развития прикладной лингвистики Студентки II курса Проверила: . Мариуполь 2015 План 1.Понятие прикладной лингвистики 2. Античные истоки прикладной лингвистики 3. Прикладная лингвистика в XIX веке 4. Современная наука 5. Перспективы современной прикладной лингвистики Вывод Список литературы 1. Понятие.

2340 Слова | 10 Стр.

История машинного перевода

История машинного перевода Впервые мысль о возможности машинного перевода высказал Чарльз Бэббидж (1791-1871), разработавший в 1836-1848 гг. проект цифровой аналитической машины - механического прототипа электронных цифровых вычислительных машин, появившихся через 100 лет. Идея Ч. Бэббиджа состояла в том, что память объемом 1000 50-разрядных десятичных чисел (по 50 зубчатых колес в каждом регистре) можно использовать для хранения словарей. Ч. Бэббидж привел эту идею в качестве обоснования для запроса.

2480 Слова | 10 Стр.

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

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

3676 Слова | 15 Стр.

Машины Тьюринга

Введение 1. Описание машины Тьюринга 1.1 Свойства машины Тьюринга как алгоритма 2. Сложность алгоритмов 2.1 Сложность проблем 3. Машина Тьюринга и алгоритмически неразрешимые проблемы Заключение Список литературы Введение Машина Тьюринга - это очень простое вычислительное устройство. Она состоит из ленты бесконечной длины, разделенной на ячейки, и головки, которая перемещается вдоль ленты и способна читать и записывать символы. Также у машины Тьюринга есть такая характеристика.

1655 Слова | 7 Стр.

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

Содержание 1. Введение 2. Алан Тьюринг. Краткая биография. 3. машины Тьюринга. Определение 4. Варианты машины Тьюринга 5. Заключение 6. Список литературы Введение Машина Тьюринга - это очень простое вычислительное устройство. Она состоит из ленты бесконечной длины, разделенной на ячейки, и головки, которая перемещается вдоль ленты и способна читать и записывать символы. Также у машины Тьюринга есть такая характеристика, как состояние, которое может выражаться целым числом от нуля до некоторой.

1524 Слова | 7 Стр.

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

848 Слова | 4 Стр.

Машина тьюринга

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

1287 Слова | 6 Стр.

машина Тьюринга

. 5 1. Биография Алана Тьюринга. 6 2. Описание машины Тьюринга. 7 3. Свойства машины Тьюринга как алгоритма. 9 4. Сложность алгоритмов. 10 5. Машина Тьюринга и алгоритмически неразрешимые проблемы.

3272 Слова | 14 Стр.

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

Введение 2 1. Описание машины Тьюринга 3 1.1 Свойства машины Тьюринга как алгоритма 5 2. Сложность алгоритмов 7 2.1 Сложность проблем 9 3. Машина Тьюринга и алгоритмически неразрешимые проблемы 12 Заключение 16 Список литературы 18 Введение Машина Тьюринга - это очень простое вычислительное устройство. Она состоит из ленты бесконечной длины, разделенной на ячейки, и головки, которая перемещается вдоль ленты и способна читать и записывать символы. Также у машины Тьюринга есть такая характеристика.

2930 Слова | 12 Стр.

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

СОДЕРЖАНИЕ 1. Описание машины Тьюринга 4 1.1 Алан Мэтисон Тьюринг 6 1.2 Понятие машины Тьюринга 6 1.3.Свойства машины Тьюринга как алгоритма 6 3. Работа машины Тьюринга 8 1. ОПИСАНИЕ МАШИНЫ ТЬЮРИНГА 1.1 Алан Мэтисон Тьюринг Алан Мэтисон Тьюринг (23 июня 1912 – 7 июня 1954) – английский математик, логик, криптограф, оказавший существенное влияние на развитие информатики. Кавалер Ордена Британской империи.

1127 Слова | 5 Стр.

Тест тьюринга

1200 Слова | 5 Стр.

ЭВОЛЮЦИЯ МАШИННОГО ПЕРЕВОДА

3569 Слова | 15 Стр.

Маш. Тьюринга

гаАлан Тьюринг (1912-1954)гг. британский математик, автор трудов по математической логике, вычислительной математике Сын колониального чиновника. Алан обучался в Шерборнской школе и в Кингс-колледже в Кембридже. Затем в Принстонском университете. В 1938 получил степень доктора философии. В конце 1943 при участии Тьюринга была построена первая вычислительная машина. В 1945 Тьюринг был принят в Национальную физическую лабораторию в Лондоне. В 1948 ученый был назначен заместителем директора.

1157 Слова | 5 Стр.

Тест Тьюринга

4987 Слова | 20 Стр.

Алан Тьюринг

1266 Слова | 6 Стр.

Реферат

Введение……………………………………………………………………….…2 1. Появление ЭВМ……………………………………………………………….5 2.Направления развития ЭВМ……………………………………….…….……6 2.1.Аналоговые вычислительные машины (АВМ)……………….……6 2.2.Электронные вычислительные машины (ЭВМ)………………..….7 2.3.Аналого-цифровые вычислительные машины (АЦВМ)….….……8 3. Поколения ЭВМ……………………………………………………….….…. 8 3.1. Первое поколение ЭВМ…………………………………….……….8 3.2. Второе поколение ЭВМ…………………………………….

4533 Слова | 19 Стр.

Реферат

3750 Слова | 15 Стр.

Алан Тьюринг – пионер кибернетики

1578 Слова | 7 Стр.

Моделирование машины Тьюринга

911 Слова | 4 Стр.

реферат

5144 Слова | 21 Стр.

Специальные алгоритмы (Машины Поста и Тьюринга)

………………………………………………………………………………. 3 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МАШИНЫ ПОСТА 1.1. Описание машины Поста. …………….………………………………………. 4 1.2. Программа машины Поста..………. ……………………………………………….. 1.3. Работа машины………………………………..……………………………….……. 5 8 Выводы ………………………….………………………………………………………. 11 2. ОТЛИЧИЯ МАШИНЫ ТЬЮРИНГА И ПОСТА 2.1. Машина Тьюринга……………..……………………………………………………. 12 2.2. Отличия работы машин…………….……………………………………………….. 14 Выводы ………………………………………………………………………………….

1607 Слова | 7 Стр.

Информатика в XIX и начале XX веков. Механические и электромеханические устройства и машины.

XIX и начале XX веков. Механические и электромеханические устройства и машины. 2014 г. Оглавление Введение2 Глава 1.Информатика в XIX веке. Механический этап развития вычислительной техники2 1.1.Предпосылки создания механических вычислительных устройств 2 1.2.Механические средства вычислений 4 1.3.Машина В.Шиккарда 4 1.4.Машина Б.Паскаля 5 1.5.Машина Г.Лейбница 7 1.6.Машина Ч.Бэббиджа 8 1.7.Другие механические машины 13 Глава 2.Информатика в конце XIX и начале XX веков. Электромеханический.

4907 Слова | 20 Стр.

Реферат Ногина 9И История ЭВМ

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

1244 Слова | 5 Стр.

Реферат: "Организация оперативной памяти"

6748 Слова | 27 Стр.

Математическая логика

6994 Слова | 28 Стр.

реферат по философии

5716 Слова | 23 Стр.

Реферат

1470 Слова | 6 Стр.

работа обучающегося (всего) 35 в том числе: решение задач; выполнение расчетно-графических заданий; работа по лекциям, со справочной и дополнительной литературой, Интернет источниками, составление конспектов, презентаций, докладов, рефератов. 6 6 23 Итоговая аттестация в форме ДИФФЕРЕНЦИРОВАННОГО ЗАЧЁТА 2.2. Тематический план и содержание учебной дисциплины Элементы математической логики Наименование разделов и тем Содержание учебного материала, практические занятия, самостоятельная.

2909 Слова | 12 Стр.

Nmnnnn

846 Слова | 4 Стр.

Искусственный интеллект

1116 Слова | 5 Стр.

Ооа уолтуа уклатоувло лцуотцул

2097 Слова | 9 Стр.

Информационные технологии

самостоятельно в графическом редакторе Paint и вставлены в текстовый документ. В контрольной работе необходимо описать порядок подготовки документов, формат отдельных фрагментов текста, способ добавления иллюстраций в основной документ. Реферат в обязательном порядке должен включать в себя: 1. Титульный лист. 2. Содержание. 3. Подготовленные документы. 4. Описание работы. 5. Список литературы. Поля страниц основного текста — 3 см слева, по 2 см — снизу, сверху и справа.

7078 Слова | 29 Стр.

[Bvbz d

2994 Слова | 12 Стр.

Ntjhbz fkujhbnvjd

2463 Слова | 10 Стр.

Реферат

электронных вычислительных машин (ЭВМ) начались в 40-х годах прошлого столетия почти одновременно в трех странах: Великобритании, США и СССР. Становление ВТ как науки началось с 1936 года, когда английский математик Алан Тьюринг (Alan Turing) предложил строгую математическую модель алгоритма решения задачи. Эта модель, получившая название абстрактной машины Тьюринга, могла быть использована для вычисления алгоритмов любой сложности. Физическую модель вычислительной машины предложил американец (венгр.

6350 Слова | 26 Стр.

Теория алгоритмов

Реферат Отчет по курсовой работе содержит: 38 страниц, 23 рисунка, 4 таблицы, 3 приложения, 2 источника. Объект исследования – рекурсивные функции, машины Тьюринга, нормальные алгоритмы Маркова. Цель – сформировать формальное определение алгоритма в виде трех аналитических моделей, написать программную реализацию машины Тьюринга, распознающей язык L = =1>, построить график временной сложности. Результат – формальное определение алгоритмов на.

3374 Слова | 14 Стр.

Донецк - 2014 РЕФЕРАТ Данный отчет о проделанной курсовой работе содержит 31 страниц, 3 рисунка, 17 таблиц, 1 приложение, 7 источников. Объект исследования – рекурсивные функции, машины Тьюринга, нормальные алгоритмы Маркова. Цель – сформировать формальное определение алгоритма в виде трех аналитических моделей. Результат – формальное определение алгоритмов на основе рекурсивных функций, машин Тьюринга и нормальных алгоритмов Маркова. МАШИНА, АЛГОРИТМ, АЛФАВИТ, ТЬЮРИНГА, ЛЕНТА, ЯЗЫК.

4204 Слова | 17 Стр.

Теория алгоритмов

1119 Слова | 5 Стр.

История появления алгоритмов

2156 Слова | 9 Стр.

Известные алгоритмы в истории математики

Лента предполагается потенциально бесконечной, разбитой на ячейки (равные клетки). При необходимости к первой или последней клетке, в которой находятся символы пристраивается пустая клетка. Машина работает во времени, которое считается дискретным, и его моменты занумерованы 1, 2, 3, … . В каждый момент лента содержит конечное число клеток. В клетки в дискретный момент времени может быть записан только один символ (буква) из внешнего алфавита A = , n ³ 2 . Пустая ячейка обозначается символом L, а сам символ L называется пустым, при этом остальные символы называются непустыми

Содержание работы

1. Математическая модель машины Тьюринга 3

2. Работа машины Тьюринга 6

3. Примеры машин Тьюринга, работающих в алфавите 7

4. Способы задания машин Тьюринга, операции над ними 11

5. Список используемой литературы 14

Файлы: 1 файл

махорин.docx

Московский Авиационный Институт

(Государственный Технический Университет)

Кафедра Прикладной Информатики

Реферат по курсу

Математическая логика и теория алгоритмов

студент группы 06-421

Преподаватель каф. 609

1. Математическая модель машины Тьюринга 3

2. Работа машины Тьюринга 6

3. Примеры машин Тьюринга, работающих в алфавите 7

4. Способы задания машин Тьюринга, операции над ними 11

5. Список используемой литературы 14

1. Математическая модель машины Тьюринга

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

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

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

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

2. Считывающая головка (некоторый считывающий элемент) пере-мещается вдоль ленты так, что в каждый момент времени она обозревает

ровно одну ячейку ленты. Головка может считывать содержимое ячейки и записывать в нее новый символ из алфавита А. В одном такте работы она может сдвигаться только на одну ячейку вправо (П), влево (Л) или оста-ваться на месте (Н). Обозначим множество перемещений (сдвига) головки D = . Если в данный момент времени t головка находится в крайней клетке и сдвигается в отсутствующую клетку, то пристраивается новая пустая клетка, над которой окажется головка в момент t + 1.

3. Внутренняя память машины представляет собой некоторое конеч-ное множество внутренних состояний Q = < q₀ , q₁, q₂ , . q_m >, m ³ 1. Будем считать, что мощность |Q | ³ 2. Два состояния машины имеют особое значение: q₁ – начальное внутреннее состояние (начальных внутренних состояний может быть несколько), q₀ – заключительное состояние или стоп-состояние (заключительное состояние всегда одно). В каждый момент времени МТ характеризуется положением головки и внутренним состоя-нием. Например, под ячейкой, над которой находится головка, указывается внутреннее состояние машины.

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

1. Описание машины Тьюринга

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

Формально машина Тьюринга может быть описана следующим образом. Пусть заданы:

конечное множество состояний – Q, в которых может находиться машина Тьюринга;

конечное множество символов ленты – Г;

один символ из Г-->е (пустой);

подмножество Σ є Г — -> определяется как подмножество входных символов ленты, причем е є (Г — Σ);

одно из состояний – q0 є Q является начальным состоянием машины.

Решаемая проблема задается путем записи конечного количества символов из множества Σ є Г – Si є Σ на ленту:

после чего машина переводится в начальное состояние и головка устанавливается у самого левого непустого символа (q0,w) –, после чего в соответствии с указанной функцией переходов (qi,Si) — ->(qj,Sk, L или R) машина начинает заменять обозреваемые символы, передвигать головку вправо или влево и переходить в другие состояния, предписанные функций переходов.

Остановка машины происходит в том случае, если для пары (qi,Si) функция перехода не определена.

1.1 Свойства машины Тьюринга как алгоритма

Дискретность. Машина Тьюринга может перейти к (к + 1) — му шагу только после выполнения каждого шага, т.к именно каждый шаг определяет, каким будет (к + 1) — й шаг.

2. Сложность алгоритмов

Сложность алгоритма определяется вычислительными мощностями, необходимыми для его выполнения. Вычислительная сложность алгоритма часто измеряется двумя параметрами: Т (временная сложность) и S (пространственная сложность, или требования к памяти). И Т, и S обычно представляются в виде функций от n, где n — это размер входных данных. (Существую и другие способы измерения сложности: количество случайных бит, ширина канала связи, объем данных и т.п.)

Обычно алгоритмы классифицируются в соответствии с их временной или пространственной сложностью. Алгоритм называют постоянным, если его сложность не зависит от n: 0(1). Алгоритм является линейным, если его временная сложность О(n). Алгоритмы могут быть квадратичными, кубическими и т.д. Все эти алгоритмы — полиномиальны, их сложность — О(m), где m — константа. Алгоритмы с полиномиальной временной сложностью называются алгоритмами с полиномиальным временем

Алгоритмы, сложность которых равна О(tf(n)), где t — константа, большая, чем 1, a f(n) — некоторая полиномиальная функция от n, называются экспоненциальными. Подмножество экспоненциальных алгоритмов, сложность которых равна О(сf(n)), где где с — константа, a f(n) возрастает быстрее, чем постоянная, но медленнее, чем линейная функция, называется суперполиномиальным.

При условии, что единицей времени для нашего компьютера является микросекунда, компьютер может выполнить постоянный алгоритм за микросекунду, линейный — за секунду, а квадратичный — за 11.6 дня. Выполнение кубического алгоритма потребует 32 тысяч лет, что в принципе реализуемо, компьютер, конструкция которого позволила бы ему противостоять следующему ледниковому периоду, в конце концов получил бы решение. Выполнение экспоненциального алгоритма тщетно, независимо от экстраполяции роста мощи компьютеров, параллельной обработки или контактов с инопланетным суперразумом.

Взглянем на проблему вскрытия алгоритма шифрования грубой силой. Временная сложность такого вскрытия пропорциональна количеству возможных ключей, которое экспоненциально зависит от длины ключа. Если n — длина ключа, то сложность вскрытия грубой силой равна 0(2n). Сложность вскрытия грубой силой при 56-битовом ключе составляет 256, а при 112-битовом ключе — 2112. В первом случае вскрытие возможно, а во втором — нет.

2.1 Сложность проблем

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

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

Как ни странно, можно доказать, что некоторые NP-задачи настолько же трудны, что и любая задача этого класса. Такие задачи называются NP-полными. То есть, если такая задача решается за полиномиальное время, то P=NP.

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

Наконец, существует класс задач EXPTIME. Эти задачи решаются за экспоненциальное время. В настоящее время можно доказать, что EXPTIME-полные задачи невозможно решить за детерминированное полиномиальное время. Кроме того, доказано, что P<>EXPTIME.

3. Машина Тьюринга и алгоритмически неразрешимые проблемы

За время своего существования человечество придумало множество алгоритмов для решения разнообразных практических и научных проблем. Зададимся вопросом – а существуют ли какие-нибудь проблемы, для которых невозможно придумать алгоритмы их решения?

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

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

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

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

а) Отсутствие общего метода решения задачи

Проблема 1: Распределение девяток в записи числа;

Определим функцию f(n) = i, где n – количество девяток подряд в десятичной записи числа, а i – номер самой левой девятки из n девяток подряд: =3,141592… f(1) = 5.

Задача состоит в вычислении функции f(n) для произвольно заданного n.

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

Проблема 2: Вычисление совершенных чисел;

Определим функцию S(n) = n-ое по счёту совершенное число и поставим задачу вычисления S(n) по произвольно заданному n. Нет общего метода вычисления совершенных чисел, мы даже не знаем, множество совершенных чисел конечно или счетно, поэтому наш алгоритм должен перебирать все числа подряд, проверяя их на совершенность. Отсутствие общего метода решения не позволяет ответить на вопрос о останове алгоритма. Если мы проверили М чисел при поиске n-ого совершенного числа – означает ли это, что его вообще не существует?

Проблема 3: Десятая проблема Гильберта;

Пусть задан многочлен n-ой степени с целыми коэффициентами – P, существует ли алгоритм, который определяет, имеет ли уравнение P=0 решение в целых числах?

Ю.В. Матиясевич показал, что такого алгоритма не существует, т.е. отсутствует общий метод определения целых корней уравнения P=0 по его целочисленным коэффициентам.

б) Информационная неопределенность задачи

Проблема 4: Позиционирование машины Поста на последний помеченный ящик;

Пусть на ленте машины Поста заданы наборы помеченных ящиков (кортежи) произвольной длины с произвольными расстояниями между кортежами и головка находится у самого левого помеченного ящика. Задача состоит установке головки на самый правый помеченный ящик последнего кортежа.

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

в) Логическая неразрешимость (в смысле теоремы Гёделя о неполноте)

Проблема 6: Проблема эквивалентности алгоритмов;

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

Проблема 7: Проблема тотальности;

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

Заключение

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

1. Рощин А.Г., Половов Р.М. Теория автоматов. Часть I. Тексты лекций — Москва: МГТУ ГА, 2001. — 76 с.

ГОСТ

Машина Тьюринга — это абстрактный исполнитель или абстрактная вычислительная машина.

Введение

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

Эта научная работа послужила стимулом к более углублённому изучению цифрового исчисления и компьютерных устройств, в том числе осознание мысли, что есть проблематика в сфере вычислений, которую нельзя решить на обычных электронных вычислительных машинах пользователей

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

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

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

Готовые работы на аналогичную тему

Машина осуществляет связь двух конечных рядов информационных данных, а именно алфавит знаков на входе $A = (a_0, a_1, …, a_m)$ и алфавит состояний $Q = (q_0, q_1, . q_p)$. Пассивным считается состояние $q_0$. Предполагается, что машина прекращает выполнение операций, когда считывает именно его. Исходным состоянием является состояние $q_1$, и устройство запускается в работу, когда считывает это стартовое состояние. Слово на ленте, которое является входной информацией, расположено последовательно по одной букве в позиции. При этом, впереди него и за ним расположены нулевые квадраты.

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

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

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

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

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

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

Рисунок 1. Функции машины Тьюринга. Автор24 — интернет-биржа студенческих работ

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

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

Читайте также: