Content deleted Content added
→Circularity of Definitions: good catch |
Invalid definition of r.e. set |
||
Line 35:
--[[User:Ashsong|Michael Stone]] 00:25, 11 March 2006 (UTC)
:Good catch. The definitions in [[computable function]] should be reworked, and probably [[computable function]] and [[recursive function]] should be merged. --[[User:Trovatore|Trovatore]] 00:41, 11 March 2006 (UTC)
== Invalid definition of r.e. set ==
This is the invalid definition of recursively enumerable set from the article
:There is an algorithm that, when given an input — typically an integer or a tuple of integers or a sequence of characters — eventually halts if and only if the input is an element of S.
The problem is that there is no formal definition of ''algorithm'' (unless you choose the nonstandard definition that identifies algorithms with Turing machines, or something else equally nonstandard). The definitions of ''recursively enumerable set'' that apear in current texts all make reference to one of the several equivalent formally defined models of computation. It is only via Church's thesis that they identify the sets that are recursively enumerable with the sets that are enumerable by some “algorithm.” This confusion about Church's thesis is pervasive in many of the articles about computability.
Several of the comments for the suggested merge of [[Recursive function]] and [[Computable function]] suffer from the same confusion. There can be no formal definition of computable function which does not make reference to some model of computation.
[[User:CMummert|CMummert]] 20:25, 14 July 2006 (UTC)
| |||