Content deleted Content added
Futonchild (talk | contribs) No edit summary |
→Does S have to be a set of natural numbers?: resp. to User:Futonchild |
||
Line 64:
:::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)
::::Yes, it is true that the things called Godel numberings in computability theory, like the Godel numbering of the sentences of a formal language, cannot literally be "computable functions" unless their ___domain and range are included in the set of legal inputs/outputs of whatever model of computation we use. I used the word "corresponds" in this article precisely for that reason. Unfortunately the WP article on Godel numberings is currently in very bad shape. Feel free to edit either article if you would like to improve them.
::::And yes, the Church-Turing thesis is limited to functions whose ___domain and range are included in the set of possible inputs/outputs of the model of computation. For example, the successor operation on [[ordinal]]s, although in some sense effective, can't be computable because there is no model of computation that can represent all the ordinals as inputs. [[User:CMummert|CMummert]] · <small>[[User talk:CMummert|talk]]</small> 23:14, 28 February 2007 (UTC)
| |||