Remarks
According to the Church-Turing thesis, any effectively calculable function is calculable by a Turing machine, and thus a set S is recursively enumerable if and only if there is some algorithm which yields an enumeration of S. This cannot be taken as a formal definition, however, because the Church-Turing thesis is an informal conjecture rather than a formal axiom.
The definition of a recursively enumerable set as the domain of a partial function, rather than the range of a total recursive function, is common in contemporary texts. This choice is motivated by the fact that in generalized recursion theories, such as α-recursion theory, the definition corresponding to domains has been found to be more natural. Other texts use the definition in terms of enumerations, which is equivalent for recursively enumerable sets.
Read more about this topic: Recursively Enumerable Set
Famous quotes containing the word remarks:
“I thought my razor was dull until I heard his speech and that reminds me of a story that’s so dirty I’m ashamed to think of it myself.”
—S.J. Perelman, U.S. screenwriter, Bert Kalmar, Harry Ruby, and Norman Z. McLeod. Groucho Marx, Horsefeathers, as a newly-appointed college president commenting on the remarks of Huxley College’s outgoing president (1932)
“There are remarks that sow and remarks that reap.”
—Ludwig Wittgenstein (1889–1951)
“So, too, if, to our surprise, we should meet one of these morons whose remarks are so conspicuous a part of the folklore of the world of the radio—remarks made without using either the tongue or the brain, spouted much like the spoutings of small whales—we should recognize him as below the level of nature but not as below the level of the imagination.”
—Wallace Stevens (1879–1955)