# Can we use domains other than the naturals in computability theory?

I wonder why people assume the domain of a computable function is $\mathbb N$? For example, in Wikipedia.

Can its domain be any countable set rather than $\mathbb N$?

Can its domain be an uncountably infinite set?

• There is no point in restricting the domain. As for uncountable set, it would mean infinitely many symbols set in the initial TM tape. In that you could encode the solutions of any problem with finite input. It could have consequences. Commented May 27, 2014 at 6:52

The domain is finite strings of symbols from some alphabet – i.e., initial contents of Turing machine tapes. The natural numbers can be easily coded as finite strings: either in unary using length or in some higher base using symbols from the tape alphabet as digits. Other countable sets (e.g., integers and rationals) can be coded if, and only if, there is a computable bijection between that set and the naturals. However, you can't let your domain be any countable set: for example, if you want your domain to be the set of Turing machines that halt on every input, you couldn't even tell which Turing machine a given finite string codes.

There's no way to use an uncountable domain because the initial contents of the tape must be finite and there are only countably many finite strings over any finite alphabet.

Models of computation based on "continuous domains" were initially developed by Dana Scott in the '60s (see Domain Theory).

Working from the reals, the domain is a partial order on certain subsets (compact intervals) of the reals, each of which can be identified with a real, but with a topology distinct from the usual. Computable functions, like continuous functions, preserve "limits" of computationally enumerable elements of the domain. For a good overview, see: Formalisation of Computability of Operators and Real-Valued Functionals via Domain Theory

• Please give references in a way that is robust against link rot; see here for a guide. Commented May 27, 2014 at 16:27

its worth mentioning here theres a significant body of theory about theoretical computational models over the reals, "real computation". the model is in some ways more powerful than Turing machines and is also subject to some academic debate about its relative role in CS. see eg:

During the Hellenistic period in Greece, constructions by circle and ruler were an important computational tool. As an example, try to look at deferent and epicycle from the Ptolemaic system of astronomy not as an explanatory model, but as a practical algorithm for computing approximate positions of stars by circle and ruler. Also note that civil engineering needs computational tools for determining the static of buildings, and that circle and ruler are not too bad for that purpose. There are limitations to this computational method, when very small and very huge magnitudes occur together in the same computation. This is one of the rare occasions where greeks used techniques vaguely related to our modern positional number systems.

Papyrus was cheap enough to make this a practical method of computation, at least when you were not from Pergamon. Pliny the Elder claims that Pergamon tried to compete with Alexandria, and as a consequence papyrus was temporarily withheld from them. They invented parchment as a reaction, or at least significantly improved the production methods and the quality of parchment. But parchment was probably still too precious to consume it for something as auxiliary as computations.

This answer is "freely based" on information from The Forgotten Revolution: How Science Was Born in 300 BC and Why It Had to Be Reborn. I googled a bit to ensure that what I write is not too far off from "current consensus", but I'm lazy and this answer should be considered as "quite inaccurate".

Forgive me if get this wrong because I am here to try and learn as much as possible.

But it seems to me that, regardless of the base used there cannot be an infinte number of characters. As each character is used once (not sure about this) the computer or maybe its to do with chaos theory or the laws of probability or physics or something, but as each character is used once it can not be used again on its own, so each character has to be combined with another to form a string. So if you have 1 million characters and you now using strings of 2 characters you have 2 million possible strings to use, than once they are all used you need to use strings of 3 characters, so you have 3 million possible strings to use (I think but I'm not sure; my basic maths is rubbish) and so on till you have 1 000 000 000 000 possible strings. It would not take a computer a day to go through all possible combinations if it were set up to do just that. But if it is just going through the string combinations as normal it probably uses the same string multiple times so it would probably take years.

Please correct me if I am wrong, I am not great with maths (please see profile) please explain in a conceptual mannor.

This whole concept of a domain for a computable function is intriguing to me, What is the Function of N?

• In computability, one might discuss machines that take input without an upper bound on its length. So it makes sense to talk about an infinite domain, since then you have an infinite amount of different input strings ($1, 11, 111, ...$, for example). Commented May 28, 2014 at 22:30
• " So if you have 1 million charicters and you now using strings of 2 charicters you have 2 million possable strings to use" - No. You have $1,000,000 \cdot 1,000,000$ different possibilities. You have to count all the different combinations. Commented May 28, 2014 at 22:36
• I'm sorry but I can't work out what you're trying to say. Commented May 29, 2014 at 0:03
• but dosent 1million times 1millioon give 12 million ? would that not be the limit ? Commented May 30, 2014 at 10:35