RAM-машина : Структура, Див. також, Примітки, Література Вікіпедія

RAM-машина

Цю статтю потрібно повністю переписати відповідно до стандартів якості Вікіпедії. Ви можете допомогти, переробивши її. Можливо, сторінка обговорення містить зауваження щодо потрібних змін. (грудень 2019)

Ця стаття не містить посилань на джерела. Ви можете допомогти поліпшити цю статтю, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (грудень 2019)

Машина з довільним доступом до пам'яті (рівнодоступна адресна машина, скорочено РАМ-машина) — модель машини з одним суматором, команди програми не можуть змінювати самі себе. Служить теоретичною моделлю, зокрема, для аналізу алгоритмів.^[1]

Структура

РАМ-машина складається з вхідної стрічки, з якої вона може лише зчитувати, та вихідної стрічки, на яку вона може лише записувати, та пам'яті.

Вхідна стрічка складається з послідовності комірок, в яких записані цілі числа (можливо від'ємні). Щоразу, коли машина зчитує число з вхідної стрічки, зчитуюча голівка пересувається на наступну комірку вправо.

На вихідну стрічку машина може лише записувати; її розбито на комірки, які спочатку порожні. При виконанні команди запису в комірку, на яку вказує записуюча голівка, зберігається ціле число, а голівка пересувається на наступну комірку вправо. Записане вихідне число змінити вже неможливо.

Пам'ять складається з послідовності регістрів r₀, r₁, …, r_i, …, кожен з яких може зберігати довільне ціле число.

Програма для RAM-машини зберігається не в її пам'яті. Тому припускають, що програма не здатна змінювати сама себе. Програма складається з послідовності (можливо) помічених команд. Перелік команд залежить від постановки задачі, але схожий на типову мову асемблера.

Обчислення здійснюють в першому регістрі — r₀, який називають суматором. Кожна команда складається з двох частин: коду операції та адреси.