Publish on 17th November 2019
Category: Birds
0

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

1

Diagonalization and Reducibility

We will now look at two techniques for proving that a set is not recursive or not even r.e.These techniques are calleddiagonalizationandreducibility.The idea behind diagonalization is to conduct a proof by contradiction.First, we make the assumption that a certain set A can be enumerated in a suitable fashion.Second, we show that, with the help of the enumeration, we can define an object b with b A.

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

2

Diagonalization and Reducibility

For example, we proved Theorem 2.1 using a diagonalization argument to show that HALT(x, y) or{(x, y) N2| HALT(x, y)} is not computable.Here, the set A is the class of unary partially computable functions.Assertion 1 (A can be enumerated) follows from the fact thatLprograms can be enumerated.For each n, letPnbe the program with number n.Then all unary partially computable functions are in the following list: (1)P0, (1)P1, (1)P2, …

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

3

Diagonalization and Reducibility

We first assumed that HALT(x, y) were computable and performed a proof by contradiction.Then we wrote a programPthat computes (1)Pwhich involved the (assumedly computable) predicate HALT(x, y).Finally, we showed that (1)Pdoes not appear in the list (1)P0, (1)P1, (1)P2, …From this contradiction we concluded that HALT(x, y) cannot be computable.

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

4

Diagonalization and Reducibility

The idea was to writePsuch that for every x,(1)P(x) if and only if (1)Px(x).In other words,HALT(x, #(P)) HALT(x, x)This means that (1)P(x) differs from each function (1)P0, (1)P1, (1)P2, … on at least one input value.(1)Pcannot be (1)Pn, because(1)P(n) if and only if (1)Pn(n).

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

5

Diagonalization and Reducibility

So (1)Pdoes not appear in the list (1)P0, (1)P1, (1)P2, …, which satisfies Assertion 2 (there is a b A).By this contradiction we can conclude that HALT(x, y) is not computable.The term diagonalization is derived from the visualization of this proof technique.

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

6

Diagonalization

The elements on thediagonalmake it impossible for (1)Pto be any of the (1)Pn.

(1)P0(0)

(1)P0(1)

(1)P0(2)

…

(1)P1(0)

(1)P1(1)

(1)P1(2)

…

(1)P2(0)

(1)P2(1)

(1)P2(2)

…

…

…

…

…

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

7

Diagonalization

Another example:Let TOT be the set of all numbers p such that p is the number of a program that computes a total function f(x) of one variable:TOT = {z N | (x) (x, z)}Since (x, z) x Wz,TOT is simply the set of numbers z such that Wzis the set of all nonnegative integers.Theorem 6.1:TOT is not recursively enumerable.

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

8

Diagonalization

Proof:Suppose that TOT were r.e.Since TOT (we know that there are total unary functions), by Theorem 4.9 there is a computable function g(x) such that TOT = {g(0), g(1), g(2), …}.Let h(x) = (x, g(x)) + 1.Since any g(x) is the number of a program that computes a total function, (x, g(x)) is defined for all x, and h(x) is a computable function.Let h(x) be computed by a program with number p.Then p TOT, which means that p = g(i) for some i. Thenh(i) = (i, g(i)) + 1by definition of h= (i, p) + 1since p = g(i)= h(i) + 1since h is computed by p.Contradiction!

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

9

Diagonalization

The elements on thediagonalmake it impossible for the function h to be computed by any of the programs g(x).

(0, g(0))

(1, g(0))

(2, g(0))

…

(0, g(1))

(1, g(1))

(2, g(1))

…

(0, g(2))

(1, g(2))

(2, g(2))

…

…

…

…

…

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

10

Diagonalization

Theorem 6.1 gives a reason why we base our studies of computability on partial rather than total functions:By Church’s Thesis, Theorem 6.1 shows that there is no algorithm to determine whether anLprogram computes a total function.

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

11

Reducibility

Another important technique for determining nonrecursive sets is thereducibilitymethod.Once some set (such as the set K) has been shown to be nonrecursive, we can use that set to give other examples of nonrecursive sets.

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

12

Reducibility

Definition:Let A, B be sets. Then A ismany-one reducibleto B, written A mB, if there is a computable function f such thatA = {x N | f(x) B}.In other words, x A if and only if f(x) B.“Many-one” means that f does not have to be one-one.If A mB, then testing membership in A is “no harder than” testing membership in B.To test whether x A we can compute f(x) and then test whether f(x) B.

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

13

Reducibility

Theorem 6.2:Suppose A mB.If B is recursive, then A is recursive.If B is r.e., then A is r.e.Proof:Let A = {x N | f(x) B}, where f is computable, and let PB(x) be the characteristic function of B.Then A = {x N | PB(f(x))}.If B isrecursive, then PB(f(x)), the characteristic function of A, is computable, so A is recursive.If B isr.e., then B = {x N | g(x)} for some partially computable function g.Then A = {x N | g(f(x))}, and since g(f(x)) is partially computable, A is r.e.

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

14

Reducibility

We will often use Theorem 6.2 in the following form:If A is not recursive (r.e.), then B is not recursive (r.e.).Example:K0= {z N | r(z)(l(z))} = {x, y | y(x)}Obviously, K0is r.e. However, we can show that K0is not recursive by reducing K to K0.K = {n N | n Wn}.Now x K if and only if x, x K0, and the function f(x) = x, x is computable.Therefore, K mK0, and K0is not recursive.

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

15

Numerical Representation of Strings

So far, our programs in the languageLhave been usingnatural numbersas their inputs and output.For many applications, however, we would prefer to perform computations onstringson some alphabet instead.You remember that we introduced anumbering ofLprogramsso thatLprograms could be used as input and output of another (or the same)Lprogram.With regard to strings, we will use the same approach:We willassociate numbers with stringson A in a one-one manner.

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

16

Numerical Representation of Strings

We will use a system that is very similar to our everyday one-one mapping ofnatural numberstostrings of digits.There we have a set D of digits, and we define an order s0, …, s9on these digits:D = {s0, …, s9} = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.There are n = 10 elements in our set of digits.Then any string w of digits can be written asw = siksik-1… si1si0,where 0 im n - 1 and k = |w| - 1.

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

17

Numerical Representation of Strings

For example, if we have the string w = 372, thenk = 2, i2= 3, i1= 7, i0= 2.To find the number associated with this string, we use exactly the following formula:x = iknk+ ik-1nk-1+ … + i1n1+ i0n0x = 3102+ 7101+ 2 = 372.If w = 372 is anoctalrepresentation of an integer, then we would have n = 8 and therefore:x = 382+ 781+ 2 = 192 + 56 + 2 = 250

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

18

Numerical Representation of Strings

Now let us develop such a method for strings on an alphabet A.Remember that the set of all strings on an alphabet A, including the empty string, is called A*.Again, let us assume that there is a particularorderof symbols in A.We write A = {s1, …, sn} and define that the sequences1, …, sncorresponds to this order of symbols.Then any string w on A can be written asw = siksik-1… si1, si0, where 1 im n and k = |w| - 1.Theempty stringis indicated by w = 0.

April 11, 2019

Theory of Computation Lecture 16: Calculations on Strings I

19

Numerical Representation of Strings

Then we use exactly the same formula as before to associate w with an integer x:x = iknk+ ik-1nk-1+ … + i1n1+ i0n0.With w = 0 we associate the number x = 0.For example, consider the alphabet A = {a, b, c} and the string w = caba.Then x = 333+ 132+ 231+ 1 = 81 + 9 + 6 + 1= 97.Now why is this representation unique?We can prove this by showing how to retrieve the subscripts i0, i1, …, ikfrom x for any x > 0.

0

Embed

Upload

toc04-11