Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

для каждого такого входа дает через конечное число действий (шагов) соответствующий символьный выход. Существенными чертами неформального понятия алгоритма оказываются следующие: 1 - алгоритм задается как набор инструкций конечных размеров, т. е. его можно описать конечным набором слов и специальных символов; 2 - имеется вычислитель, например человек, который умеет обращаться с инструкциями и производить вычисления; 3 - алгоритм имеет некоторое множество входных данных; 4 - имеется возможность для выделения, запоминания и повторения шагов вычисления; 5 - для каждого данного входа вычисление (преобразование входа) производится только по данным инструкциям; 6 - с помощью алгоритма получается одно или несколько выходных данных. Легко заметить аналогию с цифровыми вычислительными машинами. Отметим, что алгоритм обладает также свойством массовости, т.е. он применяется для решения множества однотипных задач, а не одной задачи. Также алгоритм обладает свойством общедоступности. Задание алгоритма предполагает, что процесс применения алгоритма к входам является механическим, т.е. процедура преобразования входов не требует для своего осуществления никакой изобретательности. Эти рассуждения выявляют некоторые свойства алгоритма, но не дают достаточно точного его определения. § 2. Алфавит. Слова. Алгоритм в алфавите. Вполне эквивалентные алгоритмы Алфавитом называется всякое непустое конечное множество символов, а сами символы алфавита называются буквами. Примером алфавита может служить конечное множество символов {a,+,l,v] или, например, русский алфавит. Словом в данном алфавите А называется всякая конечная последовательность букв алфавита^. Пустая последовательность букв называется пустым словом и обозначается через Л. Если Р обозначает слово abb и Q обозначает слово bb, то пусть PQ обозначает слово abbbb, аналогично для любых слов Р я Q запись PQ обозначает слово, полученное из слов Р м Q, если сразу за Р записать слово Q. Ясно, что для любого слова имеем РЛ=ЛР=Р. 147