Abstract:In Part 1 of this book we have defined the computable functions f : ℕk→ℕ and the computable functions f : (W(∑))k→ W(∑). These definitions, however, are not applicable to functions on the rational num...In Part 1 of this book we have defined the computable functions f : ℕk→ℕ and the computable functions f : (W(∑))k→ W(∑). These definitions, however, are not applicable to functions on the rational numbers, on finite graphs, on the real numbers, etc. It is not even defined whether a "standard numbering" ν : ℕ→W(∑) is computable or not. Obviously, new definitions are needed. One method for defining the computable functions f : M1→ M2 is to develop a new computability model for the sets M1 and M2. As we have seen in Part 1, any new computability model requires the development of an extended theory and the justification of a thesis like Church's Thesis. We already know that a computability theory may be reducible to another one, e.g. computability on words may be reduced to computability on numbers by a standard numbering v : ℕ→ W(∑) (Theorem 1.7.5), or computability of functions ℕk→ ℕ can be reduced to computability of functions ℕ→ℕ by the tupling function π(k) (Lemma 1.2.16). This indicates a second method for introducing computability of functions M1→ M2. The elements of M1 and M2 are named (or encoded) by numbers, and a function f: M1→ M2 is called computable iff it results from a computable function which transforms names (i.e. numbers) into names. In this case no new theory of computability has to be developed, but still theses corresponding to Church's Thesis have to be discussed, namely whether the "namings" of M1 and M2 are "intuitively effective". Of course, this method is only applicable to denumerable sets since the set of available names, namely ℕ, is only denumerable. A naming by natural numbers will be called a numbering. In this chapter we shall study effectivity w.r.t. given numberings. The question of effectivity of numberings will be discussed later in a separate chapter.Read More
Publication Year: 1987
Publication Date: 1987-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot