Поиск по сайту:

Поистине ловок тот, кто умеет скрывать свою ловкость (Ф. Ларошфуко).

Машины Тьюринга и теория вычислимости

4 мин для чтения
FavoriteLoadingДобавить в избранное
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...
1 января 2021
Алан Тьюринг
Машина Тьюринга – центральная теоретическая конструкция в информатике. Машина Тьюринга – это абстрактная математическая модель вычислений. Использование машин Тьюринга помогает объяснить, что такое вычисление, путем разграничения так называемых «вычислимых функций».

Раннее исследование логики Алана Тьюринга было сосредоточено на известной нерешенной проблеме, известной как Entscheidungsproblem. Entscheidungsproblem (примерно переводится с немецкого как «проблема решения») была предложена философом и математиком Дэвидом Гильбертом в 1928 году. Задача заключалась в том, существует ли алгоритм, который решал бы каждое утверждение на формальном языке.

Формальный язык – это система аксиом и правил вывода, например, в арифметике или логике первого порядка. Аксиомы могут быть любыми символами, а правила вывода могут быть любым списком правил манипулирования этими символами. «Принятие решения по каждому утверждению» означало либо вывод, было ли утверждение истинным/ложным, либо вывод, было ли утверждение выводимым/невыводимым. Теорема Курта Гёделя о полноте доказала, что алгоритм, определяющий применимость, эквивалентен эффективной процедуре, определяющей выводимость. В статье Алана Тьюринга 1936 года «О вычислимых числах в приложении к Entscheidungsproblem» был доказан отрицательный результат, заключающийся в невозможности алгоритмически решить каждое утверждение в формальной системе.

Алан Тьюринг

Алан Тьюринг

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

Машины Тьюринга и теория вычислимости

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

 

Читать  Почему вам стоит выбрать VPS хостинг

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

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

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

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

Читать  Топ-5 процессорных кулеров

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

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

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

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Поделиться в соц. сетях:
0 0 голоса
Рейтинг статьи
Подписаться
Уведомить о
guest
0 комментариев
Межтекстовые Отзывы
Посмотреть все комментарии

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

0
Оставьте комментарий! Напишите, что думаете по поводу статьи.x
()
x

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам:

Заполните форму и наш менеджер перезвонит Вам в самое ближайшее время!

badge
Обратный звонок 1
Отправить
galka

Спасибо! Ваша заявка принята

close
galka

Спасибо! Ваша заявка принята

close