программирование и логика

[a_shen]

Полное помеченное двоичное дерево (то есть отображение множества 01-слов в 01, каждому слову, то есть вершине, соответствует метка) может быть задано по-разному:

(1) как программа, которая по слову указывает метку соответствующей вершины

(2) как программа, которая в применении к 0 даёт метку корня, а в применении к 1 и 2 выдаёт текст программ, задающих (в том же смысле) левое и правое поддеревья

От (2) к (1) переход очевиден, надо рекурсивно вызывать интерпретатор - а обратный переход не совсем очевиден (и может быть хорошей задачей по логике для программистов)