No label defined (Q3335771)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3867312
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3867312 |
Statements
1984
0 references
domains
0 references
computability
0 references
recursively enumerable inseparability
0 references
index sets
0 references
effective complete partial order
0 references
cpo
0 references
0.7589482069015503
0 references
0.7491430044174194
0 references
0.7419598698616028
0 references
[For the entire collection see Zbl 0538.00005.] A lot of important undecidability results are based on the fact that certain sets are recursively inseparable. An obvious generalization of recursive inseparability is inseparability by a recursively enumerable (r.e.) set, i.e., r.e. inseparability. We consider index sets of certain disjoint sets S and T of computable elements of an effective complete partial order (cpo) under certain numberings of these elements and study the r.e. and the effective r.e. inseparability of such index sets. The main result about effective r.e. inseparability is that the index set of S is effectively r.e. inseparable from the index set of T, if there is an r.e. subset T' of T such that S has a nonempty intersection with the closure of T' in the Scott topology of the cpo. As a consequence from this result one obtains the cpo generalizations of some well-known theorems, the theorem by Rice/Shapiro on completely r.e. sets of computable cpo elements and the theorem by Myhill/Shepherdson on effective operators. Moreover, it follows that the index set of a non Scott-open class of computable cpo elements is productive. This generalizes a result by Myhill/Dekker.
0 references