Index set (computability theory)

An index set (of English. Index set ), and semantic quantity called, is in the computability theory an association of Godel numbers predictable features that all indices contain functions of a particular class.

definition

Be an effective numbering of all partially computable functions. A lot of hot semantics if: ${\displaystyle \lbrace \varphi _{n}\rbrace _{n\in \mathbb {N} }}$ ${\displaystyle A\subseteq \mathbb {N} }$

${\displaystyle \forall n;m\in \mathbb {N} \colon \varphi _{n}=\varphi _{m}\land n\in A\Rightarrow m\in A}$

So if two indices describe the same function, either both are in them or neither of them. ${\displaystyle A}$

Two partial functions are called the same if they are (un) defined in the same places and whenever they are defined, they always deliver the same result.

characterization

It denotes the totality of all partially computable functions; for each functional class there is exactly one index set that contains the numbers of functions . ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {S}}\subseteq {\mathcal {P}}}$ ${\displaystyle {\mathcal {S}}}$

Conversely, a corresponding, unique class of functions can also be found for each semantic set.

This means that an index set is completely determined by the semantic properties of the functions, from which the designation also results. ${\displaystyle {\mathcal {S}}}$

Examples

The following sets are index sets:

• the holding problem ${\displaystyle \varepsilon }$ ${\displaystyle H_{0}=\{n\mid \varphi _{n}(0)\downarrow \}}$
• the set of god numbers of all computable functions defined everywhere ${\displaystyle TOTAL=\{n\mid \forall k\colon \varphi _{n}(k)\downarrow \}}$

These sets are not index sets:

• the (general) holding problem with ${\displaystyle H=\{\langle n,k\rangle \mid \varphi _{n}(k)\downarrow \}}$ ${\displaystyle \langle \cdot ~,\cdot \rangle :\mathbb {N} ^{2}\rightarrow \mathbb {N} }$

The elements of this set do not define any functions. For example , it can apply. ${\displaystyle \varphi _{\langle n,k\rangle }\uparrow }$

• the special holding problem ${\displaystyle K=\{n\mid \varphi _{n}(n)\downarrow \}}$

${\displaystyle \varphi _{n}=\varphi _{n'}\nRightarrow n,n'\in K}$because in general . For example, for the function that is only defined at that point . ${\displaystyle \varphi _{n}(n)\downarrow \nLeftrightarrow \varphi _{n}(n')\downarrow }$ ${\displaystyle n}$

properties

• Every non-empty index set has an infinite recursively enumerable subset (and is therefore itself infinite), this follows from the padding lemma .
• Complements as well as any cuts and combinations of semantic sets are again semantic.
  • The system of the index sets thus constitutes both a σ-algebra and a topology on . ${\displaystyle \mathbb {N} }$
• Index sets are decidable if and only if they are trivial (i.e., or whole ), this is Rice's theorem . ${\displaystyle \emptyset }$ ${\displaystyle \mathbb {N} }$
• A set is many-one-reducible to an index set if and only if it can be one-one-reducible to this index set, so all semantic sets are cylinders .

literature

• H. Rogers Jr.: Theory of recursive functions and effective computability. 2nd ed., 3rd printing (1992), MIT Press, Cambridge MA, ISBN 0-262-68052-1

Individual evidence

1. ↑ Ref. E.g. in T. Kötzing: Computability theory . Lecture at the Friedrich Schiller University Jena in the summer semester 2013.