ВЫЧИСЛИМОСТЬ В ПРОИЗВОЛЬНЫХ ОБЛАСТЯХ И БАЗИСАХ

В этой описательной статье мы обсуждаем одно из главных понятий математики и вычисли-

тельной науки  понятие эффективной вычислимости. Демонстрируя разнообразие определений вычислимости, мы в то же время обнаруживаем, что эти определения не объясняют нам,

почему они оказываются эквивалентными друг другу. Размышляя над тем, как можно строго

поставить этот вопрос, мы приходим к понятию абстрактной вычислимости в произвольных

областях и базисах. Анализируя различные работы, посвященные абстрактной вычислимости,

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

попыткой синтеза взглядов на вычислимость, сложившихся как в математической логике, так

и в теоретическом программировании.