Более строгое описание алгоритма, чем общее или формализация понятия алгоритма. Три подхода к формализации: теория конечных и бесконечных автоматов, теория вычислимых (рекурсивных) функций и л-исчисление Черча. Воображаемые машины Поста и Тьюринга.
Аннотация к работе
Абстрактная машина Поста представляет собой бесконечную ленту, разделенную на одинаковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой «V», и головки, которая может перемещаться вдоль ленты на одну клетку вправо или влево, наносить в клетку ленты метку, если этой метки там ранее не было, стирать метку, если она была, или проверять наличие в клетке метки. С точки зрения свойств алгоритмов, изучаемых с помощью машины Поста, наибольший интерес представляют причины останова машины при выполнении программы: 1) останов по команде «стоп»; такой останов называется результативным и указывает на корректность алгоритма (программы); Предположим, что на ленте записано только одно число и головка находится над одной из клеток, в которой находится метка, принадлежащая этому числу: Для решения задачи можно переместить головку влево (или вправо) до первой пустой клетки, а затем нанести метку. Программа, добавляющая к числу метку слева, имеет вид: Программа, добавляющая к числу метку справа, имеет вид: (отличие только в направлении движения головки в первой команде. В случае более сложных начальных условий, когда неизвестно, справа или слева от головки (и на какое число клеток) находится число, можно применить такой принцип поиска числа: двигая головку вправо и влево и отмечая метками степень удаления головки от исходного положения, найти число, а потом уже применить известную программу сложения.