Теорема (про оберненість асимптотичних відношень)

1. Відношення виконується тоді і тільки тоді, коли виконується відношення .

2. Відношення виконується тоді і тільки тоді, коли виконується .

Лекція 2

§2.1. Машини з довільним доступом до пам’яті

Машини з довільним доступом до пам’яті (або, інакше, рівно доступна адресна машина – скорочено РАМ) моделює обчислювальну машину з одним суматором, в якій команди програми не можуть змінювати самі себе.

РАМ складаються із вхідної стрічки, з якої вона може лише зчитувати, вихідної стрічки, на яку вона може лише записувати, і пам’яті (малюнок 1).

…

Вхідна стрічка

…

Вихідна стрічка

Малюнок 1

Вхідна стрічка є послідовністю клітинок, кожна з яких може містити ціле число (можливо від’ємне). Кожного разу, коли символ зчитується із стрічки, іі голівка зміщується на одну клітинку вправо. Вихід є стрічкою на яку машина може лише записувати; вона розбита на клітинки, які спочатку всі пусті. При виконанні команди запису в тій клітинці вихідної стрічки, яку в цей час оглядає її голівка записується ціле число і голівка потім зміщується на одну клітинку вправо. Як тільки вихідний символ записаний, його уже неможна змінити.

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

1) розмір задачі достатньо малий, щоб вона помістилася в основну пам’ять обчислювальної машини,

2) цілі числа, які приймають участь в обчисленні, достатньо малі, щоб їх можна було помістити в одну комірку.

Програма для РАМ (РАМ-програма) не записується в пам’ять. Тому передбачається, що програма не змінює сама себе. Програма є, по суті, послідовністю (можливо) помічених команд. Точний тип команд, допустимих у програмі, недуже важливий, поки вони нагадують ті, які зазвичай зустрічаються в реальних обчислювальних машинах. Передбачається, що є арифметичні команди, команди вводу-виводу, непряма адресація (наприклад, для індексації масивів) і команда розгалуження. Всі обчислення відбуваються в першому регістрі , який називається суматором, і який, як і всякий інший регістр пам’яті, може зберігати довільне ціле число. Приклад набору команд для РАМ подано в таблиці 2.1. Кожна команда складається з двох части – коду операції

й адресу.

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

Операнд може бути одного із типів:

1. =і означає само ціле число і й називається літералом,

2. і вміст регістру і (і повинно бути невід’ємним),

3. і означає непряму пере адресацію, тобто, значенням операнда є вміст регістру j де j – ціле число, яке знаходиться в регістрі і; якщо j <0 машина спиняється.

Таблиця 2.1

Код операції	Адрес
LOAD STORE ADD SUB MULT DIV READ WRITE JUMP JGTZ JZERO HALT	Операнд Операнд Операнд Операнд Операнд Операнд Операнд Операнд Мітка 10 -12

Можна визначити значення програми Р за допомогою двох об’єктів: відображення с з множини невід’ємних цілих чисел в множину цілих чисел і “лічильника команд“, який визначає наступну виконувану команду. Функція с є відображенням пам’яті, а саме с(і) – ціле число, яке міститься в регістрі і (вміст регістру і).

Спочатку с(і)=0 для всіх , лічильник команд установлений на першу команду в Р, а вихідна стрічка пуста. Після виконання k-тої команди із Р лічильник команд автоматично переходить на k+1 (тобто на наступну команду), якщо k-та команда не була командою вигляду JUMP, HALT, JGTZ або JZERO.

Щоб описати дію команди задамо значення v(a) операнда а:

v ( =i ) = i, v ( i ) = c (i), v ( i ) = c(c (i)).

Таблиця 2.2 визначає дію кожної команди з таблиці 2.1.

Таблиця 2.2

Команда

Дія

1.LOAD а 2..STORE і STORE 3. ADD а 4. SUB а 5. MULT а 6. DIV а 7. READ і READ 8. WRITE a 9. JUMP b 10. JGTZ b 11. JZERO b 12. HALT

1. c(0) v(a) 2. c(i) c(0) c (c(i)) c(0) 3. c(0) c(0) + v( a) 4. c(0) c(0) - v( a) 5. c(0) c(0) v( a) 6. c(0) ëc(0) / v( a)û 7. c(i) наступний вхідний символ. (c(i)) наступний вхідний символ. У обох випадках головка вхідної стрічки зміщується на одну клітинку вправо. 8. v( a) записується у тій клітинці вихідної стрічки, яку в даний момент оглядає її голівка. Потім ця головка зміщується на одну клітинку вправо. 9. Лічильник команд установлюється на команду з міткою b. 10. Якщо c(0) > 0, то лічильник команд установлюється на команду з міткою b, у іншому випадку на наступну команду. 11. Якщо c(0) = 0, то лічильник команд установлюється на команду з міткою b, у іншому випадку на наступну команду. 12. Робота завершується.

Команди, діям яких не наведено визначення (такі як STORE = i) можна вважати еквівалентними команді HALT. Аналогічно ділення на нуль спиняє машину. При виконанні будь-якої з перших восьми команд лічильник команд збільшується на одиницю. Тому команди в даній програмі виконуються послідовно, до тих пір поки не зустрінеться команда JUMP чи HALT або JGTZ при вмісті суматора, більшого нуля, або JZERO при в вмісті суматора, рівного нулю.

РАМ-програма визначає відображення із множини вхідних стрічок в множину вихідних стрічок. Оскільки на деяких вхідних стрічках програма може не спинятися, це відображення є частковим (тобто для деяких входів воно може бути не визначеним). Це відображення можна інтерпретувати різними способами. Дві важливі інтерпретації – інтерпретація інтерпретація у вигляді функції й інтерпретація у вигляді мови.

Припустимо, що програма Р завжди зчитує з вхідної стрічки n цілих чисел і записує на вихідну стрічку не більше одного цілого числа. Нехай – цілі числа, які знаходяться в перших n клітинках вхідної стрічки, і нехай програма Р записує y в першу клітинку вихідної стрічки а потіч через деякий час спиняється. Тоді говорять, що Р обчислює функцію . Можна показати, що для довільної частково рекурсивної функції можна написати РАМ-програму, яка її обчислює, і для довільної РАМ-програми можна указати еквівалентну їй часткова рекурсивну функцію.

Інший спосіб інтерпретувати програму для РАМ – це подивитися на неї з точки зору сприйняття нею мови. Алфавіт – це скінченна множина символів, мова – множина ланцюгів (слів) алфавіту, Символи алфавіту можна подати цілими числами 1, 2, …, k при деякому k. Дана РАМ сприймає мову в такому розумінні. Нехай на вхідній стрічці знаходиться ланцюг , причому символ розташований в першій клітинці, – в другій і т.д., а в (n+1)-й клітинці розташований 0 – символ, який використовується в значенні кінцевого маркера, тобто маркера кінця вхідного ланцюга. Вхідний ланцюг сприймається РАМ-програмою Р, якщо Р прочитає всі її символи й кінець маркера, пише 1 в першу клітинку вихідної стрічки й спиняється.

Мовою, яка сприймається програмою Р, називається множина всіх ланцюгів (слів), які нею сприймаються. Для вхідних ланцюгів, які не належать мові, котра сприймається програмою Р, вона може написати на вихідній стрічці символ, відмінний від 1, й спинитися, а може навіть і не спинитися взагалі. Можна показати, що мова сприймається деякою РАМ тоді й тільки тоді, коли вона рекурсивно перераховна. Мова сприймається РАМ, котра спиняється на всіх входах, тоді й тільки тоді, коли вона рекурсивна.