ксти на деякій мовою, що цілком відповідає нашому інтуїтивному уявленню про алгоритм.
Виникає питання, чи є алгоритмом робота будь-якої машини Тьюрінга? У їх поведінці є багато спільного: все, що вони В«вміютьВ», зводиться до досить простих операцій пошуку поточної команди, перетворення, вхідного символу в вихідний, зміни внутрішнього стану і знаходження наступного вхідного символу. Ці операції носять настільки регулярний, В«механічнийВ» характер, що їх цілком можна описати у вигляді єдиної програми для підходящої машини - універсальної машини Тьюринга.
Ідея універсальної машини полягає в імітації роботи будь-якої конкретної машини Тьюринга. З цією метою в пам'яті універсальної машини повинні зберігатися програма роботи і образ імітованої машини, що включає інформацію як про вмісті її пам'яті з вказівкою на поточний вхідний символ, так і про поточний стані.
На перший погляд, це здається неможливим, адже безліч всіх імітованих машин нескінченно. Але тексти на будь-яких мовах можна зашифрувати (Закодувати) за допомогою єдиного, наприклад цифрового алфавіту. Зробити це, очевидно, потрібно так, щоб можна було досить просто розрізняти образ машини від її програми, символи від станів і т.п. У цьому випадку програма роботи універсальної машини Тьюринга зводиться до виконання системи нескладних дій.
В образі конкретної машини шукаються коди першого символу та початкової стану. За ним у зашифрованому тексті програми знаходиться потрібна команда, несуча інформацію про ті зміни, які потрібно провести в образі машини. Після їх вчинення коди нового стану і наступного символу дозволяють відшукати таку команду і т.д. Цей процес, званий інтерпретацією, продовжується до тих пір, поки не буде досягнуто кінцевий стан. У цьому випадку в пам'яті універсальної машини виявиться код вихідного слова імітованої машини Тьюринга.
У уявному пристрої універсальної машини використані важливі ідеї, що знайшли пізніше втілення в особливостях конструкції і роботи справжніх ЕОМ. У першу чергу, це робота за програмою, що представляє собою символічну запис алгоритму мовою, В«зрозумілоюВ» для виконання не дуже складним пристроєм. По-друге, це наявність пристрою, що запам'ятовує для зберігання як вихідної, проміжної і кінцевої інформації, так і самої програми. Пам'ять реальних ЕОМ завжди кінцева, але це обмеження стає несуттєвим у сучасних ЕОМ, що володіють вельми великою пам'яттю. Нарешті, це можливість імітації роботи будь-яких спеціалізованих пристроїв обробки інформації на однієї універсальної конструкції.
В
6. Нормальні алгоритми Маркова
Коротко зупинимося на третьому підході до уточнення (конкретизації) поняття алгоритму. За змістом воно близьке до ідей Тьюринга, однак, у ньому не використовуються уявлення про будь машинах. Алгоритм задається системою підстановок, які вказують, які заміни символів необхідно виробляти і в якому порядку ці підстановки повинні слідувати. Такий підхід було запропоновано А.А. Марковим. На початку 50-х років минулого сторіччя було введено поняття нормального алгоритму (сам Марков називав їх алгорифма).
Знову розглянемо деякий алфавіт A, що містить кінцеве число знаків (літер). Введемо ряд визначень:
Слово - це будь-яка кінцева послідовність знаків алфавіту.
Кількість символів у слові називається його довжиною. p> Слово, довжина якого дорівнює нулю, називається порожнім. p> Слово s називається подсловом слова q, якщо q можна представити у вигляді q = rst, де r і t - будь-які слова в тому ж алфавіті (у тому числі і порожні). p> Тепер можна визначити поняття алгоритму (що не є суворим):
Алгоритмом в алфавіті A називається ефективно обчислювана функція, областю визначення якої служить-яке підмножина множини всіх слів в алфавіті A і значеннями якої також є слова в алфавіті A.
В алгоритмах Маркова в якості елементарного кроку алгоритму приймається підстановка одного слова замість іншого. Нехай в алфавіті A побудовано вихідне слово P, яке містить подсловом P r (у загальному разі таких Підшар у вихідному слові може бути декілька), а також є деяке слово P k в тому ж алфавіті.
Підстановкою називається заміна першого по порядку подслова P r вихідного слова P на слово P k . Позначається підстановка P r в†’ P k .
Алгоритм у даній формі подання задається системою підстановок, яка являє собою послідовність (список) підстановок. Якщо в цьому списку є підстановки з лівими частинами, які входять в P, то перша з них застосовується до P, в результаті чого воно переходить у інше слово P 1 . До нього знову застосовується схема підстановок і т.д. Процес припиняється у двох випадках: або в списку не знайшлося підстановки з лівою частиною, що входить до P n , або при отриманні P n була застосована остання підстановка.
В
Біблі...
