Content deleted Content added
→Universal recursively enumerable set: new section |
|||
Line 148:
Strangely, I do not see here a universal recursively enumerable set. [[User:Tsirel|Boris Tsirelson]] ([[User talk:Tsirel|talk]]) 17:52, 17 February 2018 (UTC)
:It is not defined here (and I have forgotten the definition), but I believe that these two examples listed in the section on examples would qualify:
:* Given a [[Gödel numbering]] <math>\phi</math> of the computable functions, the set <math>\{\langle i,x \rangle \mid \phi_i(x) \downarrow \}</math> (where <math>\langle i,x \rangle</math> is the [[Cantor pairing function]] and <math>\phi_i(x)\downarrow</math> indicates <math>\phi_i(x)</math> is defined) is recursively enumerable (cf. picture for a fixed ''x''). This set encodes the [[halting problem]] as it describes the input parameters for which each [[Turing machine]] halts.
:* Given a Gödel numbering <math>\phi</math> of the computable functions, the set <math>\lbrace \left \langle x, y, z \right \rangle \mid \phi_x(y)=z \rbrace</math> is recursively enumerable. This set encodes the problem of deciding a function value.
:[[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 12:39, 18 February 2018 (UTC)
| |||