мета-данные страницы
  •  
Загрузка не удалась. Возможно, проблемы с правами доступа?

Различия

Показаны различия между двумя версиями страницы.

Ссылка на это сравнение

Следующая версия		Предыдущая версия
Последняя версияСледующая версия справа и слева
asm:base [13/02/2012 00:18] – создано arabusovasm:base [13/02/2012 00:22] – arabusov
Строка 1: Строка 1:
 ===== Архитектура IBM PC ===== ===== Архитектура IBM PC =====
 +==== Машина Тьюринга ====
 +{{:asm:220px-maquina.png|}}
 +
 +
 Согласно теоретическим исследованиям в области теории алгоритмов [[http://ru.wikipedia.org/wiki/Машина_Тьюринга|машина Тьюринга]] способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен. Согласно теоретическим исследованиям в области теории алгоритмов [[http://ru.wikipedia.org/wiki/Машина_Тьюринга|машина Тьюринга]] способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
-{{:asm:maquina.png|}}+ 
 + 
 +В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано. 
 + 
 +Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные. 
 + 
 +Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.