Определение. Доказательство окончено

ФУНКЦИИ, ВЫЧИСЛЯЕМЫЕ СИСТЕМАМИ ПОСТА

Доказательство окончено.

Ранее уже отмечалось, что множество классов слов, выводимых в системах Поста, не является замкнутым относительно операции взятия дополнения до множества всех слов в заданном основном алфавите. Такое свойство множеств выводимых слов связано существованием неразрешимых множеств слов, выводимых в системах Поста.

Пусть P = (A, B, V, P) - система Поста, основной алфавит, который вместе с другими символами содержит символы f,), (и символ запятой -,. Здесь f - функциональный символ, обозначающий некоторую функцию.

Словарная функция f: (A*) ⁿ ® A* вычисляется системой P, если: " ₁,..., _n Î A* (f ( ₁,..., _n) = _{n+ 1} в системе P выводится слово ″ f ( ₁,..., _n) = _{n+ 1}″),

То есть функция f, вычисляемая системой Поста P, отображает набор ( ₁,..., _n), составленный из - слов в алфавите A, в слово _{n+ 1} в том же алфавите тогда и только тогда, когда в P выводима запись: ″ f ( ₁,..., _n) = _{n+ 1}″.

Иначе говоря, в системе P выводятся записи таких слов, которые представляют график отображения f.

Аналогично определяется понятие числовой функции, вычисляемой в некоторой системе Поста P.

Пусть обозначает двоичную запись числа m.

Дата добавления: 2015-03-31