3.Найпростіша мова програмування – імперативні оператори.

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

clear <ім'я>;

Параметр <ім'я> може бути будь-яким припустимим ім'ям змінної.

incr < ім'я >;

decr <ім'я>;

І в цьому випадку параметр <ім'я> являє собою будь яке припустиме ім'я змінної.

Найпростіша мова містить всього одну керуючу структуру, наданих парою операторів while-end, що має наступний синтаксис:

while <ім'я> not 0 do;

.....end;

Тут параметр <ім'я> являє собою будь припустиме ім'я змінної.

Зазначена вище синтаксична конструкція буде викликати повторення будь-якої по-послідовності операторів, розміщених між операторами while і end, поки значення змінної <ім'я> не стане рівним нулю.

4.Можливості програм, написаних на найпростішому мові

.Що можливо, а не то, що зручно.Використовувати найпростішу мову програмування для прикладних цілей, дуже важко.

Мови, подібні найпростішій мові програмування, хоч і непрактичні щодо створення прикладного програмного забезпечення, але, тим не менш, знаходять застосування в теорії обчислювальних машин.move <ім'я 1> to <ім'я 2>;

Тут параметри <ім'я 1> і <ім'я 2> представляють імена відповідних змінних.

Таким чином, хоча найпростіша мова сам по собі і не має явної команди присвоєння, ми часто будемо писати програми, вважаючи, що він допускає подібні дії.

5.Поняття Машини Тюрінга

Найпростіша мова програмування є універсальною у тому сенсі, що з її допомогою можна висловити рішення будь-якої проблеми, яку здатна вирішити машина.

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

Зазначимо, що Тьюринг "винайшов" дані машини ще до того, як розвиток технологій дозволив реалізувати їх на практиці.Машина Тьюрінга складається з блоку управління, який зчитує і записує символи на стрічці за допомогою головки зчитування / запису.Стрічка поділена на комірки, кожна з яких може містити один довільний символ з кінцевого набору.

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

6.Поняття обчислюваних функцій

Розглянемо дії комп'ютера на самому фундаментальному рівні. Якщо можна було б зробити знімки стану пам'яті комп'ютера до і після виконання програми, то ми б побачили один набір двійкових розрядів, відповідний станом пам'яті до її виконання, а другий - після її виконання. Програма виконує єдину дію: управляє перетворенням деякого початкового набору двійкових розрядів, який будемо називати вхідним, в інший набір двійкових розрядів, іменований вихідним. Зв'язок, що існує між цими наборами, називається функцією. Процес визначення вихідної величини функції на основі значення її вхідний величини називається обчисленням функції. Отже, дії комп'ютера при виконанні програми можуть розглядатися як обчислення функції. Таке розуміння процесу обчислень надає нам засіб для вимірювання обчислювальної потужності машини. Якщо деяка машина або алгоритмічна система здатна обчислювати більше функцій, ніж інша, то ми будемо вважати її більш потужною.