Читайте также:
|
Машина Тьюринга это абстрактная вычислительная машина. Была предложена Аланом Тьюрингом для формализации понятия алгоритма.
Компоненты
В состав машины Тьюринга входит бесконечная лента, разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы. Имеется и другая трактовка
В теории вычислимости исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
Есть программы для обычных компьютеров, имитирующие работу машины Тьюринга. Но следует отметить, что данная имитация неполная, так как в машине Тьюринга присутствует абстрактная бесконечная лента. Бесконечную ленту с данными невозможно в полной мере имитировать на компьютере с конечной памятью (суммарная память компьютера — оперативная память, жёсткие диски, различные внешние носители данных, регистры и кэш процессора и др. — может быть очень большой, но, тем не менее, всегда конечна).
Дата добавления: 2015-07-19; просмотров: 67 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Генератор в программировании, понятие вычислительного контекста | | | Сопоставление в логическом программировании |