Автоматична обробка інформації

Як приклад автомата, що виконує обробку інформації, розглянемо машину Е. Посту. Алгоритм, за яким працює машина Посту, будемо називати програмою.
Домовимося про термінологію: під словом «програма» ми завжди будемо розуміти алгоритм, записаний за суворими правилами мови команд виконавця – на мові програмування для даного виконавця.
Модель машини Посту
Опишемо архітектуру машини Посту (рис. 2.6). Мається нескінченна інформаційна стрічка, розділена на позиції – клітини. У кожній клітині може або стояти позначка (деякий знак), або відсутніми (пусто).
Уздовж стрічки рухається каретка – зчитує. На малюнку вона позначена стрілкою. Каретка може пересуватися кроками: один крок – зміщення на одну клітку вправо або вліво. Клітку, під якою встановлена ​​каретка, називатимемо поточної.
Каретка є ще і процесором машини. З її допомогою машина може:
– Розпізнати, порожня клітка або позначена знаком;
– Стерти знак в поточній клітці;
– Записати знак в порожню поточну клітку.
Якщо зробити заміну міток на одиниці, а порожніх клітин – на нулі, то інформацію на стрічці можна буде розглядати як аналог двійкового коду телеграфного повідомлення або даних в пам’яті комп’ютера. Істотна відмінність каретки-процесора машини Посту від процесора комп’ютера полягає в тому, що в комп’ютері можливий доступ процесора до комірок пам’яті в довільному порядку, а в машині Посту – тільки послідовно.
Призначення машини Посту – виробляти перетворення на інформаційній стрічці. Початковий стан стрічки можна розглядати як вихідні дані завдання, кінцевий стан стрічки – результат рішення задачі. Крім того, у вихідні дані входить інформація про початковий положенні каретки.

У процесі виконання наведеної програми багаторазово повторюється виконання команд з номерами 2 і 3. Така ситуація називається циклом. Нагадаємо, що цикл відноситься до числа основних алгоритмічних структур разом з проходженням і розгалуженням.
А тепер навчимо машину Посту грати в інтелектуальну гру, яка називається «Гра Баше». Опишемо правила гри.
Грають двоє. Перед ними 21 (або 16, або 11 і т. Д.) Фішка. Гравці беруть фішки по черзі. За один хід можна взяти від 1 до 4 фішок. Програє той, хто забирає останню фішку.
Мається виграшна тактика для гравця, що бере фішки другого. Вона полягає в тому, щоб брати таку кількість фішок, яку доповнює число фішок, взятих суперником на попередньому ході, до п’яти.
Роль фішок на інформаційній стрічці машини Посту виконуватимуть мітки (знаки). Машина грає з людиною. Людині надається можливість прати мітки (брати фішки) першого. Машина буде вступати в гру другою. Вихідна обстановка: на стрічці масив з 21 клітини містить мітки. Каретка встановлена ​​на крайней зліва клітці цього масиву. Прати мітки можна тільки поспіль. Виграшним результатом повинна бути одна залишилася мітка перед черговим ходом людини.
Ще раз нагадаємо принцип виграшною тактики: прати стільки міток, щоб в сумі з мітками, стертими противником за попередній хід, їх було п’ять.
Програма управління машиною Посту в грі Баше проти людини наведена в табл. 2.3.
Діючи за цією програмою і починаючи прати мітки другий після людини, машина завжди буде вигравати, якщо правильно поставлено початкова число міток, яке має дорівнювати 5n + 1, де n – будь-яке натуральне число. В іншому випадку машина може програти.

Посилання на основну публікацію