неразрешимость
101ЖЕГАЛКИН — Иван Иванович (род. 1869 – ум. 1947) – рус. логик и математик, один из создателей школы математической логики. Построил логику высказываний в виде арифметики двух чисел – нуля («четное») и единицы («нечетное»), в которой в отличие от обычного… …
102НОВИКОВ — Пётр Сергеевич [15(28).8.1901, Москва, 9.1.1975, там же], сов. математик и логик, акад. ?? СССР (1960; чл. корр. 1953). Осн. труды по теории множеств, математич. логике, теории алгоритмов и теории групп. Создал метод доказательства… …
103МАРКОВ — Андрей Андреевич [р. 9(22).9.1903, Петербург, 11.10.1979, Москва], сов. математик и логик, чл. корр. АН СССР (1953). Чл. КПСС с 1953. Осн. тру ды по топологии, топологич. алгебре, теории динамич систем, теории алгорифмов и конструктивной… …
104НЕРАЗРЕШИМАЯ ФОРМУЛА — формула к. л. (логико математического) исчисления, одновре менно не доказуемая и не опровержимая средствами этого исчисления. (Соответственно формула, доказуемая или опровержимая в исчислении, наз. разрешимой в нем.) Термин Н. ф. прилагается, как …
105АЛГОРИТМОВ ЭКВИВАЛЕНТНОСТЬ — бинарное отношение, связывающее алгоритмы фиксированного типа и выражающее тот факт, что у всяких двух связанных этим отношением алгоритмов при совпадении определенного вида исходных данных совпадают и результаты работы (а также, быть может, и… …
106АССОЦИАТИВНОЕ ИСЧИСЛЕНИЕ — название, установившееся за исчислениями нек рого точно охарактеризованного типа, хорошо приспособленными для задания конечно определенных ассоциативных систем ( полугрупп). Термин А. и. введен А. А. Марковым. Им же было осуществлено построение… …
107ВЫЧИСЛИМЫЙ ИНВАРИАНТ — бинарного отношения между словами данного вида алгоритм (в к. л. точном смысле; напр. как это сделано в [1] нормальный алгорифм), применимый ко всякому слову рассматриваемого вида и перерабатывающий в одно и то же слово всякие два слова,… …
108ГРУППОВОЕ ИСЧИСЛЕНИЕ — ассоциативное исчисление, в к ром эффективным образом выполнено естественное групповое требование существования обратной операции. Именно, ассоциативное исчисление наз. Г. и. (см. [1], с. 341), если для него может быть построен инвертирующий… …
109ИЗОМОРФИЗМА ПРОБЛЕМА — задача отыскания алгоритма, позволяющего по любой паре эффективно заданных алгебраических систем из данного класса установить, изоморфны они или нет. Частная И. п. для фиксированной алгебраич. системы Асостоит в отыскании алгоритма, распознающего …
110КОНСТРУКТИВНЫЙ АНАЛИЗ — рекурсивный анализ, вычислимый анализ, название, объединяющее различные течения в основаниях математики и математич. анализе. При развитии К. а., как правило, преследуются обе или вторая из следующих двух принципиальных целей: (1) нетрадиционное… …
