Последние новости:

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

Не получить вовсе — не страшно, но лишиться полученного обидно (Клавдий Элиан).

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

FavoriteLoadingДобавить в избранное
01.01.2021
Алан Тьюринг

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

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

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

Алан Тьюринг

Алан Тьюринг

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

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

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

 

Читать  MSI активно продвигает игровые мониторы QD-OLED

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

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

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

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

Читать  Как ремонт компьютеров изменился в 2020 году?

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

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

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

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

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...
Поделиться в соц. сетях:

0 0 голоса
Рейтинг статьи
Подписаться
Уведомить о
guest

**ссылки nofollow

0 комментариев
Межтекстовые Отзывы
Посмотреть все комментарии

Это может быть вам интересно

Статьи партнеров:

Рекомендуемое
В сегодняшнем быстро меняющемся мире многозадачность стала нормой в повседневных…
0
Оставьте комментарий! Напишите, что думаете по поводу статьи.x

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

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

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

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

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

close

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

close