Табличные аппроксимации рекурсивных предикатов

В заметке рассматривается сложность табличных аппроксимаций рекурсивных предикатов. В частности, показано, что любая табличная аппроксимация к заданному рекурсивному предикату может быть существенно улучшена в бесконечно многих точках.