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:
“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)
“Where do whites fit in the New Africa? Nowhere, I’m inclined to say ... and I do believe that it is true that even the gentlest and most westernised Africans would like the emotional idea of the continent entirely without the complication of the presence of the white man for a generation or two. But nowhere, as an answer for us whites, is in the same category as remarks like What’s the use of living? in the face of the threat of atomic radiation. We are living; we are in Africa.”
—Nadine Gordimer (b. 1923)
“An illustrious individual remarks that Mrs. [Elizabeth Cady] Stanton is the salt, Anna Dickinson the pepper, and Miss [Susan B.] Anthony the vinegar of the Female Suffrage movement. The very elements get the “white male” into a nice pickle.”
—Anonymous, U.S. women’s magazine contributor. The Revolution (August 19, 1869)