Длина вычисления программ Сергей Попов und Наталья Брошкова

Вводится обобщение пропозиционального языка, позволяющее представлять все вычислимые функции и арифметические программы. Этот язык полезен при анализе вычислительных характеристик арифметических программ. В частности, показывается, что функции арифметики Пресбургера вычислимы за линейное время, а длина вычисления арифметической программы определяется мощностью фактор-множества отношения эквивалентности частичных означиваний входа программы. Тем самым удается связать сложность вычисления программы с видом вычисляемой ею функции. Это и многое другое вы найдете в книге Длина вычисления программ (Сергей Попов und Наталья Брошкова)