НОУ ІНТУІТ, Лекція, Структура однопрограмної ЕОМ

Класичні засади побудови ЕОМ

Основи побудови електронних обчислювальних машин у їхньому сучасному розумінні були закладені у 30-ті – 40-ті роки минулого століття відомими вченими: англійським математиком Аланом Т'юрінгом та американцем угорського походження Джоном (Яношем) Нейманом.

Машина Тьюринга

У 1936 році А. Т'юрінг сформулював поняття абстрактної обчислювальної машини. Поруч із ним, хоча й у настільки явної формі, це зробив Э. Пост (США). Хоча машина Тьюринга (МТ) не стала реально діючим пристроєм, вона до теперішнього часу постійно використовується як основна модель для з'ясування сутності таких понять, як "обчислювальний процес", "алгоритм", а також для з'ясування зв'язку між алгоритмом та обчислювальними машинами [11] ].

Основні положення машини Тюрінга

Машина Тьюринга (рис.10.1) має кінцеве число знаків si , що утворюють зовнішній алфавіт , в якому кодуються відомості, що подаються в МТ, а також вироблюються в ній. Серед знаків єпорожній знак(s1), посилка якого в будь-яку комірку стирає знак, що знаходився в ній, і залишає її порожньою.

структура

Залежно від поданої початкової інформації (значків, що містяться на стрічці зовнішньої пам'яті) можливі два випадки:

  • після кінцевого числа тактів машина зупиняється (маючи інформацію), подаючи сигнал про зупинку. У цьому випадку МТзастосовнадо інформації та переробляє її в інформацію;
  • зупинка ніколи не настає. В цьому випадку МТне застосовуєтьсядо початкової інформації

У кожен момент оглядається лише один осередок стрічки (пам'яті). Перехід може здійснюватися лише до сусіднього осередку (R – праворуч, L – ліворуч, N – ніпереходу (залишитися)). Перехід до довільного осередку проводиться шляхом послідовного перебору всіх осередків, що розділяють поточну та необхідну осередки. На кожному окремому такті t команда наказує тільки заміну єдиного знака si, що зберігається в осередку, що розглядається, яким-небудь іншим знаком sj.

Логічний блок МТ має кінцеву кількість станів i> i=1..m.

Знаки R, L, N, q1. qm утворюють внутрішній алфавіт машини.

Перероблений знак sj , записуваний у комірку, що переглядається, стан, який прийме машина Тьюринга в наступному такті q(t+1) і виконувана в даному такті операція переходу до наступної комірки P(t+1) є функцією аналізованого в даному такті символу і поточного стану машини si і q(t):

Програма для МТ визначається трійкою i, P, q&tt.

Приклад запису програми обчислення логічної функції "нерівнозначність" машини Тьюринга представлений нижче.