Section outline
-
Заняття 6. Абстрактна машина Поста. Машина Тюрінга. Нормальні алгоритми Маркова.
Мета: метою заняття є формування у студентів теоретичних знань та практичних навичок щодо абстрактних обчислювальних машин, які є основою для вивчення теорії алгоритмів та обчислювальності. Студенти ознайомляться з необхідністю створення таких машин та їх роллю у визначенні класу обчислювальних функцій. На занятті будуть вивчені сутність і принципи роботи абстрактних машин, таких як машина Е. Поста та машина А. Тюрінга, а також нормальні алгоритми Маркова. У результаті студенти отримають розуміння того, як ці алгоритмічні схеми дозволяють описувати будь-які алгоритми, та навчаться порівнювати їх за основними принципами та особливостями.