Content deleted Content added
Futonchild (talk | contribs) No edit summary |
|||
Line 62:
::What exactly do you believe is the formal definition of "the set ''A'' is recursively enumerable"? [[User:CMummert|CMummert]] · <small>[[User talk:CMummert|talk]]</small> 18:43, 28 February 2007 (UTC)
:::You are right. The range of a recursive function has to be a set of natural numbers, so an r.e. set has to be a set of nat num's too. This makes me think though that maybe the comment about goedel numberings should be edited to reflect the fact that a goedel numbering function, while clearly intuitively effectively computable, cannot be, strictly speaking, recursive--? Also, does this mean that the Church-Turing thesis must also be restricted to functions from (n-tuples of) nat. num's to nat. num's--since clearly there are effectively computable functions (e.g. goedel numberings) that are not recursive? --[[User:Futonchild|Futonchild]] 21:52, 28 February 2007 (UTC)
| |||