Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Универсальная абстрактная машина



Читайте также:
  1. II. Машина
  2. Алгоритм та інструкція до програми PPSMW розрахунку перехідних процесів у синхронних машинах
  3. Вышивальная машина Barudan BEVT-Z1501CBII (ЯПОНИЯ)
  4. Государство — универсальная организация
  5. ДА-НЕТНАЯ МАШИНА
  6. Кто имеет право управлять гусеничными самоходными машинами с двигателем мощностью свыше 25,7 кВт?
  7. Машина PCOR-давление

 

Алгоритмы строятся из команд, а из алгоритмов можно строить более сложные алгоритмы [7].

1) Композиция C алгоритмов А, В:

C=А◦В

С=В(А(Х)), Х – исходные данные.

Таким образом, приписывается программа к программе (программа за программой).

2) Ветвление:

А, В, С, D.

Запускается алгоритм А.

Если результат применения А(Х) соответствует заданному условию, то D(Х)=B(Х).

Иначе, D(Х)=С(Х).

3) Итерация (повторение):

Повторение алгоритма А, пока алгоритм В не укажет, что пора заканчивать.

Более удобна, чем примитивные вышерассмотренные, так называемая универсальная машина U, которая выполняет, как и современная ЭВМ любую программу.

Такая машина читает произвольную запись программы Р и применяет ее к заданному слову. Таким образом, исходные данные – это запись программы Р и исходные данные Х.

(Р) – запись программы;

Х – исходные данные (на ленте);

(Р)*Х, где * – разделитель, символ не используемый в Р.

Тогда результат записывается как U((P)*X)=P(X).

Один из способов построения универсальной машины – использование геделевской нумерации алгоритмов [19].

Программу машины Тьюринга можно закодировать следующим образом. Представим в общем, виде команду:

, a=1...k,

где k – число программ (машин), S1=L – налево, S2=R – направо, S3=E – на месте.

Пусть р1, р2, р3, ... последовательность всех простых чисел, расположенных в порядке возрастания (т.е. последовательность 2,3,5,7,11,...). Номером машины Тьюринга М с программой n называется число:

Закодируем, например, машину Тьюринга М1 с программой:

Здесь алфавит X0={1,l}, Y0={y1,yk}, кроме того t={1,2,3} соответствует L, R, E.

Таким образом:

Естественно, не все натуральные числа являются номерами машин Тьюринга. Если n – номер некоторой машины, то ее программу можно однозначно установить по этому номеру.

 


Дата добавления: 2015-07-11; просмотров: 191 | Нарушение авторских прав






mybiblioteka.su - 2015-2024 год. (0.005 сек.)