Cтраница 1
Номерное множество Z) Y этой нумерации отлично от D. [1]
Пусть номерное множество Da нумерации а является - множеством и а R - мулътисводима к нумерации р, имеющей R - бесконечные классы. [2]
Поэтому при рекурсивном номерном множестве Da частично рекурсивная мульти - или односводимость а к р равносильна рекурсивной мульти - или соответственно односводимости акр. Однако при произвольных Za, D р все введенные выше сводимости не равносильны друг другу. Приведем лишь пример, показывающий, что частично рекурсивная мультисводимость вообще отличается от общерекурсивной мультисводимости. [3]
В самом деле, номерное множество Da системы 31 по условию рекурсивно перечислимо. Согласно теореме 2.2.1 существует простая нумерация Р основного множества А системы 91, ор-униморфная нумерации а. Поскольку основные операции и предикаты системы 91 р, в том числе и отношение равенства, переходят при упомянутом униморфизме в op - операции и op - предикаты на 3 ( а, то такими же согласно теореме 2.1.4 эти операции и отношения будут и на Э ( р, что и требовалось доказать. [4]
Пусть алгебра 9t, имеющая рекурсивно перечислимое номерное множество, чр-гомоморфно отображена на алгебру 9Э с позитивной нумерацией. Тогда соответствующий канонический мономорфизм фактор-алгебры на Ж является частично рекурсивной эквивалентностью. [5]
Если множества А, В имеют рекурсивно перечислимые номерные множества, множество А позитивно или негативно и А - эквивалентно В, то В также позитивно или соответственно негативно. [6]
Напомним, что нумерации, имеющие в качестве номерного множества со вокупность всех натуральных чисел, называются простыми. Теперь, обобщая одну теорему Майхила [14], относящуюся к теории сводимости проблем, приходим к следующему предложению. [7]
Важнейшими характеристиками каждой нумерации а служат тип ее номерного множества Da и тип отношения эквивалентности 0а на Za, порождаемого нумерацией а. Номерные множества J9Y и D стандартных нумераций конечно порожденных алгебр имеют простое строение - они примитивно рекурсивны. Что же касается соответствующих эквивалентностей 0Y, Э §, то они могут быть рекурсивными всех трех типов пр, ор, чр, а также могут и не быть рекурсивно перечислимыми. Какой из этих случаев имеет место - зависит от внутреннего строения алгебры. [8]
Нумерованная алгебраическая система будет называться общерекурсивной, если ее номерное множество Z) a рекурсивно перечислимо, а эквивалентность 6а, основные операции и предикаты общерекурсивны. [9]
Нумерацию а множества А условимся называть позитивной, если ее номерное множество Z) a и соответствующая эквивалентность 0а рекурсивно перечислимы. Нумерацию а назовем разрешимой, если отношение 0а общерекурсивно. Указанные 3 типа нумераций: позитивные, негативные и разрешимые - обычно встречаются в наиболее важных конкретных случаях. [10]
Напомним, что нумерация а называется позитивной, если ее номерное множество Da и отношение эквивалентности 0а рекурсивно перечислимы. [11]
Каждая нумерация совокупности одноместных частично рекурсивных функций, имеющая рекурсивно перечислимое номерное множество и чр-эквивалентная геделевской нумерации чр-изоморфна геделевской нумерации. [12]
R - униморфизм нумерации а множества А, имеющей рекурсивно перечислимое номерное множество Z) a, на какую-либо другую нумерацию Р множества А влечет за собою R-изоморфизм этих нумераций. [13]
Теорема 3.3.3. Пусть алгебраическая система 9t имеет 1 -нумера-цию с рекурсивно перечислимым номерным множеством. [14]
Нумерованная алгебраическая система 91 имеет вполне определенную структуру, если заданы номерное множество jDa, эквивалентность 0а и функции, реализующие основные операции и предикаты системы в координатной форме. В зависимости от того, являются ли эти множество, эквивалентность, предикаты и операции частично обще - или примитивно рекурсивными, естественно выделить следующие классы нумерованных алгебраических систем. [15]