Problems and Languages

Encoding of a Set

Let S be any set, and let Σ be any alphabet. An encoding of S over Σ is defined to be a one-to-one function S → Σ^{∗}. Given such an encoding, the language of S is defined to be the set of all strings which are encodings of members of S.

When we say that a set S is regular, recursive, polynomial time, etc., we always have a specific encoding of S in mind, and we mean that the language of S is regular, recursive, polynomial time, etc..

For most applications, S ⊆ U, where U is some universal set which has a given encoding, which S inherits.

For example, the set of natural numbers can be encoded over Σ = {1} by using unary notation, i.e., the number n is encoded as the string 1^{n}. Then, for example, the set of multiples of 3 is regular, because the language {1^{3i}} is a regular language.

Encoding of a Problem

A problem consists of a set of instances, where for each instance, there is a solution. Fix an encoding of both instances and solutions of a given problem. Then, the problem is a function from strings to strings, i.e., if w is the encoding of an instance of the problem, f(w) is the encoding of of the solution of that instance.

Consider, for example, addition of natural numbers. A problem instance is encoded as a non-empty string of digits, followed by the symbol +, followed by another non-empty string of digits, such as “43 + 517”. The solution to a problem instance is a string of digits, in this case, “560”.

Encoding of a 0-1 Problem

A 0-1 problem is defined to be a problem where, for each instance, the solution is either true (1) or false (0). In this special case, the language of the problem is defined to be the set of encodings of problem instances for which the solution is true. In this case, we usuall identify the problem with its language.

For example, we can define a 0-1 addition problem to be strings of symbols which encode addition facts, such as “43 + 517 = 560”.

Encodings of Numbers

An encoding of numbers is called a numeration system, and the encoding of one number is called a numeral.

Standard numeration systems for N, the set of natural numbers, include the unary, binary, and decimal numeration systems, over the alphabets {1}, {0, 1}, and {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, respectively. We can encode the set of integers by using the additional symbol “−” for negative numbers.

Exercise 1 The knapsack problem with integer input is well-known to be N P-complete if binary or decimal encoding is used for the inputs. Prove that the problem is polynomial time if unary encoding is used for the inputs.

Rational Numbers

Let Q be the set of rational numbers. We can encode Q by using fractions, where each rational number is written as the encodings of two integers separated by the symbol “/”, such as “23/57”. To ensure uniqueness, we insist that the denominator never be negative, and that the fraction is reduced to the lowest terms.

Real Numbers

Let ℜ be the set of real numbers. There is no encoding of ℜ, since it is an uncountable set. However, there is a way to express every real number as a 0-1 problem.

Given a real number x, let Q_{x} ⊆ Q be the set of all rational numbers less than or equal to x. Intuitively, if we “know” Q_{x}, then we “know” x, since two real numbers x and y can be distinguished by a rational number that lies between them. We then identify the real number x with the set Q_{x}, which means, with the language of all encodings of members of Q_{x}.

Thus, for instance, if we say x is recursive, we mean that the language of all encodings

of members of Q_{x} is recursive. http://www.ams.org/journals/proc/1954-005-05/
S0002-9939-1954-0063328-5/S0002-9939-1954-0063328-5.pdf

For example, every rational number can be considered to be a real number, and as such, is trivially recursive, since it is easy to decide whether a given fraction is less than or equal to another given fraction.

As another example, \sqrt{2} is recursive, since the truth of the statement n/m ≤ \sqrt{2} can easily be decided.

The well known transcendental number π, the ratio of the circumference of a circle to its diameter, is also recursive. Hint: \frac{π}{4} = ∑_{i=0}^{∞}(−1)^{i} \frac{1}{2i+1}.

Exercise 2 Prove that a real number x is recursive if and only if there is a machine that runs forever, writing the decimal digits of x onto an output tape.

Exercise 3 Let S be a set of natural numbers. Let x_{S} ∈ ℜ be defined by

x_{S} = ∑_{i∈S} 2^{−i}

Prove that x_{S} is recursive if and only if S is recursive.

Note: since not all sets of natural numbers are recursive, not all real numbers are recursive.

Exercise 4 Suppose that x is a real number, and that there exists a machine M that runs forever, printing a sequence of rational numbers that converges to x. Does this prove that x is recursive? Prove or give a counter-example.