AAA
Обычный Черный



Кто не делится найденным, подобен свету в дупле секвойи (древняя индейская пословица)

версия для печатиВерсия для печати



Библиографическая запись: Машина с неограниченными регистрами. — Текст : электронный // Myfilology.ru – информационный филологический ресурс : [сайт]. – URL: https://myfilology.ru//165/informaczionnye-texnologii/mashina-s-neogranichennymi-registrami/ (дата обращения: 19.08.2022)

Машина с неограниченными регистрами

Машина с неограниченными регистрами

Содержание

    Машина с неограниченными регистрами

    Машина с неограниченными регистрами имеет бесконечно много регистров памяти R1, R2, ..., а в каждом регистре может храниться сколь угодно большое целое неотрицательное число.

    Машина с неограниченными регистрами (МНР) — это своего рода идеализированный компьютер. МНР имеет бесконечно много регистров R1, R2, в каждом из которых в любой момент времени записано некоторое натуральное число. Число, находящееся в регистре Rn, будем обозначать rn. Содержимое регистров может меняться при выполнении некоторой команды, Конечный упорядоченный список команд образует программу, Будем предполагать, что команды занумерованы числами 1,2,3,...

    Команды бывают четырех типов:

    1. 1) команда обнуления имеет вид Z(n), n ∈ {1,2,3, ...}. Выполнение такой команды заменяет содержимое регистра Rn на 0, не затрагивая другие регистры. Используя оператор присваивания, команду Z(n) можно записать так: rn:= 0;
    2. 2) команда прибавления единицы имеет вид S(n), n ∈ {1,2,3, ...}. Выполнение такой команды увеличивает содержимое регистра Rn на 1, не затрагивая другие регистры. С помощью оператора присваивания команда S(n) записывается так: rn := rn + 1;
    3. 3) команда переадресации имеет вид Т(m, n), m, n ∈ {1,2,3, ...}. Выполнение такой команды заменяет содержимое регистра Rn числом rm находящимся в регистре Rm, не затрагивая другие регистры (в том числе регистр Rm). Команду Т(m, n) можно записать так: rn := rm ;
    4. 4) команда условного перехода имеет вид  J (m,n,q), m, n, q ∈ {1,2,3, ...}. Выполнение такой команды состоит в следующем. Сравнивается содержимое регистров Rm и Rn. При rm = rn машина переходит к выполнению q-й команды программы; при rm ≠ rn — к выполнению следующей команды. Если в результате исполнения команды требуется выполнить команды с номером, превосходящим число команд в программе, машина прекращает работу. Команду J(m,n, д) можно записать так: IF rm == rn GOTO q.

    Команды обнуления, прибавления единицы и переадресации называются арифметическими. 

    Структура и функционирование

    Составные части.

    1) Регистры R1, R2, R3,..., в которых содержатся соответственно натуральные числа r1, r2, r3,...

    Число регистров бесконечно, но только конечное множество регистров R1, R2,...,Rk содержит числа, отличные от нуля. Все остальные регистры Rk+1, Rk+2,... заполнены нулями.

    .
    Машина с неограниченными регистрами, как и произвольный алгоритм, работает по тактам: такт 1, такт 2, ... Первый такт работы МНР с программой I1, I2,...,I8 — выполнение первой команды I1. Затем выполняются команды I2, I3,... Этот последовательный порядок выполнения команд продолжается до тех пор, пока не встретится команда J (m, n, q), которая может изменить естественный порядок выполнения команд.

    Условие остановки. Машина останавливается тогда и только тогда, когда невозможно выполнить очередную предписанную команду. Это означает, что МНР только что совершила i-вый такт работы и следующим  i + 1 тактом должна выполнить несуществующую команду. Эта ситуация при выполнении программы I1, I2,...,I8 возникает ровно в одном из трех следующих случаев:

    1. 1) Если в i-вом такте выполнена I8 — последняя команда программы и эта команда не является командой условного перехода, тогда следующим i +1 тактом должна выполняться несуществующая команда I8+1.
    2. 2) Если в i-вом такте выполнена команда условного перехода J (m, n, q), где rm = rn  и q > s тогда следующим i + 1тактом должна выполняться несуществующая команда Iq.
    3. 3) Если в i-вом такте выполнена I8 — последняя команда программы и эта команда является командой условного перехода J (m, n, q) при rm ≠ rn,тогда следующим i + 1 тактом должна выполняться несуществующая команда I8+1.

    Крупский В.Н. Теория алгоритмов : учеб, пособие для студ. вузов / В. Н. Крупский, В. Е. Плиско. — М.: Издательский центр «Академия», 2009. — 208 с.

    12.07.2022, 28 просмотров.


    Уважаемые посетители! С болью в сердце сообщаем вам, что этот сайт собирает метаданные пользователя (cookie, данные об IP-адресе и местоположении), что жизненно необходимо для функционирования сайта и поддержания его жизнедеятельности.

    Если вы ни под каким предлогом не хотите предоставлять эти данные для обработки, - пожалуйста, срочно покиньте сайт и мы никому не скажем что вы тут были. С неизменной заботой, администрация сайта.

    Dear visitors! It is a pain in our heart to inform you that this site collects user metadata (cookies, IP address and location data), which is vital for the operation of the site and the maintenance of its life.

    If you do not want to provide this data for processing under any pretext, please leave the site immediately and we will not tell anyone that you were here. With the same care, the site administration.