patternMinor
Is there a clear definition of "computable" for models of computation which are not turing complete?
Viewed 0 times
definitioncomputablecomputationarewhichturingcompleteforclearmodels
Problem
This is a follow-up of another question here, and I hope it is not too philosophical. As Raphael pointed out in a comment on my previous question, I don't really get the definition of "computable", but according to some papers I read, the definition is also not really clear when it comes to models of computation weaker than turing machines because of the encoding of the input and output.
The typical definition of turing computable is as follows:
Definition 1: A function $f : \mathbb{N}^k \to \mathbb{N}$ is called turing computable iff there is a turing machine $M$ which computes $f$ using a suitable encoding of the natural numbers as strings.
The definitions differ in what exactly is a suitable encoding is, but most refer to binary encoding, unary encoding or decimal encoding as the one fixed and suitable encoding. It is also possible to show that fixing one encoding is required for the definition of turing computability. But what makes, say, binary encoding of natural numbers special so that we can axiomatize it as the one suitable encoding? Probably because it fits the intuitive notion of what computability means coincidentally.
Now what if we look at weaker models of computation than turing machines? For example, let's consider the set $M_c$ of "crippled" turing machines with the alphabet $\{0,1\}$ which may only move to the right, and a definition of crippled turing computable which is consistent with that of turing computability:
Definition 2: A function $f : \mathbb{N}^k \to \mathbb{N}$ is called crippled turing computable or computable in $M_c$ iff there is a crippled turing machine $M$ which computes $f$ using a suitable encoding of the natural numbers as a string.
If we define "suitable encoding" as "binary encoding", then the function $f : \mathbb{N} \to \mathbb{N}, n \mapsto n+1$ is not computable in $M_c$. If we axiomatize "suitable encoding" as "unary encoding", then $f$ is computable in $M_c$. This seems awkward given the fact that everyon
The typical definition of turing computable is as follows:
Definition 1: A function $f : \mathbb{N}^k \to \mathbb{N}$ is called turing computable iff there is a turing machine $M$ which computes $f$ using a suitable encoding of the natural numbers as strings.
The definitions differ in what exactly is a suitable encoding is, but most refer to binary encoding, unary encoding or decimal encoding as the one fixed and suitable encoding. It is also possible to show that fixing one encoding is required for the definition of turing computability. But what makes, say, binary encoding of natural numbers special so that we can axiomatize it as the one suitable encoding? Probably because it fits the intuitive notion of what computability means coincidentally.
Now what if we look at weaker models of computation than turing machines? For example, let's consider the set $M_c$ of "crippled" turing machines with the alphabet $\{0,1\}$ which may only move to the right, and a definition of crippled turing computable which is consistent with that of turing computability:
Definition 2: A function $f : \mathbb{N}^k \to \mathbb{N}$ is called crippled turing computable or computable in $M_c$ iff there is a crippled turing machine $M$ which computes $f$ using a suitable encoding of the natural numbers as a string.
If we define "suitable encoding" as "binary encoding", then the function $f : \mathbb{N} \to \mathbb{N}, n \mapsto n+1$ is not computable in $M_c$. If we axiomatize "suitable encoding" as "unary encoding", then $f$ is computable in $M_c$. This seems awkward given the fact that everyon
Solution
Some basic fact that you are missing here is that all the encodings that you mention are equivalent from the perspective of computability: there is a computable function mapping the binary encoding of a number to its unary encoding, or vice versa. Therefore for the sake of defining computability, it does not matter which of these encodings you choose for numbers. Just fix your favorite encoding.
Computability is at its core a property of string functions $f\colon \Sigma^ \to \Sigma^$. When you define computability in any other domain, you have to fix an encoding. In practice, all "reasonable" encodings are equivalent in the sense of the preceding paragraph, so the exact encoding doesn't matter.
The encoding does, however, matter in restricted models of computation. To take an extreme example, suppose that you consider time-restricted Turing machines: say you want your machine to terminate in time $O(n^c)$ for some $c$, where $n$ is the length of the input (as a string). We can no longer switch between binary encoding and unary encoding, because binary encoding is much more compact. When we talk about a polynomial time computable function of integers, we specify that integers are encoded in binary. Even this is a somewhat arbitrary choice, since decimal encoding would lead to the same notion of polynomial time computability.
So to answer your question – the encoding is specified as part of the definition of the restricted model.
Computability is at its core a property of string functions $f\colon \Sigma^ \to \Sigma^$. When you define computability in any other domain, you have to fix an encoding. In practice, all "reasonable" encodings are equivalent in the sense of the preceding paragraph, so the exact encoding doesn't matter.
The encoding does, however, matter in restricted models of computation. To take an extreme example, suppose that you consider time-restricted Turing machines: say you want your machine to terminate in time $O(n^c)$ for some $c$, where $n$ is the length of the input (as a string). We can no longer switch between binary encoding and unary encoding, because binary encoding is much more compact. When we talk about a polynomial time computable function of integers, we specify that integers are encoded in binary. Even this is a somewhat arbitrary choice, since decimal encoding would lead to the same notion of polynomial time computability.
So to answer your question – the encoding is specified as part of the definition of the restricted model.
Context
StackExchange Computer Science Q#40066, answer score: 6
Revisions (0)
No revisions yet.