Отчет по курсовой работе содержит: 55 страниц, 21 рисунков, 4 таблиц. Опишем работу машины Тьюринга тремя способами. Курсовая работа, добавлен 16.11.2013. Машина Тьюринга. Парадигма программирования. Тьюринг как английский математик, логик, криптограф, .

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

Курсовая работа посвящена обобщениям алгоритма деления для. Машина Тьюринга представляет из себя простейшую абстрактную модель .

Есть программы для обычных компьютеров, имитирующие работу машины Тьюринга. Но следует отметить, что данная имитация неполная, так . Характеристика машины Тьюринга в каталоге лучших рефератов сети, всего более 500 000 работ.

1. Машина Тьюринга. Парадигма программирования. Машина Тьюринга. Алан Матисон Тьюринг (23 июня 1912 - 7 июня 1954) - английский .
2. Машина Поста, Тьюринга и алгоритмы Маркова.

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

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

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

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

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

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

Например, если Т= О(n), то удвоение входных данных удвоит и время выполнения алгоритма. Если Т=О(2n), то добавление одного бита к входным данным удвоит время выполнения алгоритма. Алгоритм называют постоянным, если его сложность не зависит от n: 0(1).

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

Развитие теории вычислительной сложности возможно когда- нибудь позволит создать алгоритмы, для которых существование алгоритмов с полиномиальным временем вскрытия может быть исключено с математической точностью. Выполнение кубического алгоритма потребует 3. Выполнение экспоненциального алгоритма тщетно, независимо от экстраполяции роста мощи компьютеров, параллельной обработки или контактов с инопланетным суперразумом. Временная сложность такого вскрытия пропорциональна количеству возможных ключей, которое экспоненциально зависит от длины ключа. Если n - длина ключа, то сложность вскрытия грубой силой равна 0(2n).

Сложность вскрытия грубой силой при 5. В первом случае вскрытие возможно, а во втором - нет.

Сложность проблем Теория сложности также классифицирует и сложность самих проблем, а не только сложность конкретных алгоритмов решения проблемы. Теория рассматривает минимальное время и объем памяти, необходимые для решения самого трудного варианта проблемы на теоретическом компьютере, известном как машина Тьюринга. Машина Тьюринга представляет собой конечный автомат с бесконечной лентой памяти для чтения записи и является реалистичной моделью вычислений. Нерешаемые проблемы иногда называют трудными. Проблемы, которые могут быть решены только с помощью суперполиномиальных алгоритмов, вычислительно нерешаемы, даже при относительно малых значениях n. Даже отвлекаясь от временной сложности алгоритма, невозможно создать алгоритм решения этих проблем. Вот важнейшие из них и предполагаемые соотношения между ними: P< =NP< =EXPTIME Находящийся слева класс P включает все задачи, которые можно решить за полиномиальное время.

В класс NP входят все задачи, которые можно решить за полиномиальное время только на недетерминированной машине Тьюринга (это вариант обычной машины Тьюринга, которая может делать предположения). Такая машина предполагает решение задачи – либо “удачно угадывая”, либо перебирая все предположения параллельно – и проверяет свое предположение за полиномиальное время. Тем не менее, никем не доказано, что P< > NP (или P=NP).