Post's Theorem

• For every $n\; \backslash geq\; 0$, $B\; \backslash in\; \backslash Sigma\_\{n+1\}$ if and only if $B$ is a recursively enumerable set with an oracle of some $\backslash Pi\_n$ set or, equivalently, some $\backslash Sigma\_n$ set.

• $\backslash emptyset^\{(n)\}$, i.e. the n-th Turing jump of the empty set is $\backslash Sigma\_n$ complete for every $n\; >\; 0$.

• $B\; \backslash in\; \backslash Delta\_\{n+1\}$ if and only if $B\; \backslash leq\_T\; \backslash emptyset^\{(n)\}$, i.e. $B$ is Turing reducible to $\backslash emptyset^\{(n)\}$.

• $B\; \backslash in\; \backslash Sigma\_\{n+1\}$ if and only if $B$ is a recursively enumerable set with an oracle of $\backslash emptyset^\{(n)\}$.

• $B\; \backslash in\; \backslash Delta\_\{n+1\}$ if and only if $B\; \backslash leq\_T\; \backslash emptyset^\{(n)\}$, i.e. $B$ is Turing reducible to $\backslash emptyset^\{(n)\}$.

<< Previous Word Browser Next >>
gapp michel chartrand uss normandy (cg 60) uss monterey (cg 61) turing degree uss chancellorsville (cg 62) aaron weiss jig (disambiguation) non statutory law gordon freeman bhat	lyusternik schnirelmann category nut (hardware) uss cowpens (cg 63) tungsten handheld uss gettysburg (cg 64) chad 'corntassel' smith sacoglossa kilfenora uss chosin (cg 65) list of mayors of bloomington, minnesota winter garden theatre	george murray tiger pistol shrimp defense meritorious service medal uss hue city (cg 66) uss vicksburg (cg 69) uss lake erie (cg 70) andromeda (comics) polynesian airlines jig (fishing) clatskanie river perdido street station	new crobuzon list of spanish television channels ben travers modacrylic royal tongan airlines maria von trapp hindenburg line galo plaza lasso fishing lure james pleasants lure