Дагестанського державного ІНСТИТУТ НАРОДНОГО ГОСПОДАРСТВА
Факультет: ПвКС
Реферат
З дисципліни: Теорія Алгоритмів
На тему: Машина Поста
Абдурашидов Арсен
Махачкала 2013
ЗМІСТ
ВСТУП
ОПИС РОБОТИ МАШИНИ ПОСТУ
опис алгоритмів
ОПИС ПРОГРАМИ
ВИСНОВОК
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
ВСТУП
Абстрактна обчислювальна машина - теоретична побудова, за допомогою якого вводиться суворе, математичне визначення алгоритму. Абстрактні машини є окремим випадком керуючих систем. Виникнення їх пов'язане з аналізом поняття алгоритму, що почалося в середині 30-х рр.. 20 в., З розвитком ЕОМ і з побудовою математичних моделей біологічних систем. Найбільшого поширення набули машини, переробні дискретну інформацію, типовими представниками яких є кінцевий автомат і машина Посту. Абстрактні машини володіють великою наочністю, можливістю легко здійснювати різні композиції, елементарністю кроків роботи. Вивчення машин проводиться в рамках теорії алгоритмів, математичної кібернетики і переслідує мети аналізу та формалізації поняття алгоритму, математичного моделювання реальних пристроїв і процесів. Існує плідна зв'язок між абстрактними машинами і реально існуючими ЕОМ.
Автомат - різновид абстрактної обчислювальної машини, яка визначається:
безліччю вхідних і вихідних сигналів;
безліччю станів;
функцією, яка задає переходи з одних станів в інші;
функцією, визначальною вихідні сигнали в залежності від вхідного сигналу і поточного стану.
Автомат призначений для формальної переробки послідовностей символів.
Кінцевий автомат - математична модель пристрою з кінцевою пам'яттю. Кінцевий автомат переробляє безліч вхідних дискретних сигналів в безліч вихідних сигналів. Розрізняють синхронні і асинхронні кінцеві автомати. Еміль Пост запропонував абстрактну обчислювальну машину - машину Посту. Вона проста і «еквівалентна» і була створена для уточнення поняття «алгоритм». Машина Поста складається з каретки (або зчитує і записуючої головки) і розбитою на секції стрічки, що вважається умовно нескінченної в обидві сторони. У кожній клітині може бути записаний символ з фіксованого алфавіту. У будь-який конкретний момент головка оглядає одну клітку і здатна працювати тільки з нею. Робота машини Посту визначається програмою з кінцевим числом рядків. Програма складається з команд, що мають по 3 поля, в яких записуються: № команди, операція і відсилання.
Для машини Посту визначені операції 6 видів:
1. Рух головки на 1 клітку вправо.
. Рух головки на 1 клітку вліво.
. Запис мітки.
. Видалення ...
