Ris–Shapiros teorem

I beräkningsbarhetsteorin är Rice –Shapiro-satsen en generalisering av Rice-satsen och är uppkallad efter Henry Gordon Rice och Norman Shapiro .

Formellt uttalande

Låt A vara en uppsättning partiell-rekursiva unära funktioner på domänen av naturliga tal så att mängden $Ix(A):=\{n\mid \varphi _{n}\in A\}$ är rekursivt uppräknad , där $\varphi _{n}$ betecknar den $n$ -te partiellrekursiva funktionen i en Gödel-numrering .

har vi för varje unär partiell-rekursiv funktion ${\displaystyle \psi } :$

$\psi \in A\Leftrightarrow \exists$ en finit funktion $\theta \subseteq \psi$ så att $\theta \in A.$

I den givna satsen är en finit funktion en funktion med en finit domän $x_{1},x_{2},...,x_{m}$ och $\theta \subseteq \psi$ betyder att för varje $x\in \{x_{1},x_{2},...,x_{m}\}$ gäller att $\psi (x)$ är definierad och lika med $\theta (x)$ .

Perspektiv från effektiv topologi

För varje finit unär funktion $\theta$ på heltal, låt $C(\theta )$ beteckna 'frustum' för alla partiell-rekursiva funktioner som är definierade och överensstämmer med ${\ displaystyle \theta }$ , på $\theta$ s domän.

Utrusta uppsättningen av alla partiell-rekursiva funktioner med topologin som genereras av dessa frusta som bas . Observera att för varje frustum ${\displaystyle C} är$$Ix(C)$ rekursivt uppräknad. Mer generellt gäller det för varje uppsättning $A$ med partiell-rekursiva funktioner:

$Ix(A)$ är rekursivt uppräknad iff $A$ är en rekursivt uppräknad förening av frusta.

Anteckningar

• Cutland, Nigel (1980). Beräkningsbarhet: en introduktion till rekursiv funktionsteori . Cambridge University Press. ; Sats 7-2.16.
•   Rogers Jr., Hartley (1987). Teori om rekursiva funktioner och effektiv beräkningsbarhet . MIT Press. sid. 482. ISBN 0-262-68052-1 .
• Odifreddi, Piergiorgio (1989). Klassisk rekursionsteori . Norra Holland.