April 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
1
The Parameter Theorem
Let us say that you have a partially computable function f that takes m + n inputs:f(x1, …,xm, u1, …,un)This function is computed by a program with number y.Now it turns out that you always want to use the same last ninputs(u1, …, un) whenever you call f.So you would like to use a function g taking only the first m inputs and using fixed values for the last n ones:g(x1, …,xm)This function is supposed to give the same outputs as f for any input (x1, …,xm) if(u1, …, un)never changes.
April 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
2
The Parameter Theorem
Now how can I obtain this function g?It is very easy! Since there is a program that computes f(x1, …,xm, u1, …, un), I can reuse the code for f and just prepend the following instructions to it:Xm+1 u1Xm+2u2…Xm+nunObviously, this new program computes g(x1, …,xm) with fixed values for(u1, …, un).
April 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
3
The Parameter Theorem
We said that f is computed by program number y. But what is the number z of the program that computes g?Clearly, the code for g depends on the fixed values we want to assign to(u1, …, un), and it also depends on the original program with the number y and the number n of inputs that g will still take, and the number m of inputs that will be kept constant.Computing z thus depends on all of these variables and is achieved by the function S:Smn(u1, …, un, y)The parameter theorem states that this function always exists and is primitive recursive.
April 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
4
The Recursion Theorem
Let us say that we have a partially computable function g that takes (m + 1) inputs.Then the recursion theorem tells us that we can always find at least one number e, such that the program with number e takes the m last inputs of g and then computes the same output that g would produce for the same inputs and the first input being e:e(m)(x1, ...,xm)=g(e,x1, ...,xm).
April 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
5
The Recursion Theorem
Now let us say that we have a function g like this:g(z, x) = z.With the help of the recursiontheorem, we know that we can always find a number e such thate(x) =g(e, x) = e.Such programs generate copies of themselves.Thus the parameter theorem is the theoretical foundation of the existence of computer viruses.
April 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
6
Rice’s Theorem
Letbe some collection of partially computable functions of one variable.We associatewiththefollowing index set R:R= {t N | t}.Rwill be a recursive setif there isan algorithm which accepts asinput the numbert ofa programandreturns thevalue TRUE or FALSE depending on whether or not the functioncomputedbythis program belongsto.
April 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
7
Rice’s Theorem
Some examples are:(1)is the set of computable functions;(2)is the set of primitive recursive functions;(3)is the set of partially computable functions whicharedefined forall buta finite number of values of x.Theorem 7.1 (Rice's Theorem):Letbe a collection of partiallycomputable functionsof one variable. Let there be partially computablefunctions f(x) andg(x) such that f(x) belongs tobut g(x) does not. ThenRisnot recursive.
April 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
8
Rice’s Theorem
Rice’s Theorem tells us that there is no way to algorithmically determine non-trivial properties of the function computed by another program.Trivial properties are those that apply to all partially computable functions or none of them.Thetheorem uses functions f(x) and g(x)- suchthat f(x) belongs toa collectionbut g(x) doesnot - for the sole purpose of excluding such trivial cases.
April 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
9
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 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
10
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 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
11
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.
April 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
12
Numerical Representation of Strings
First, we define two primitive recursive functions
where R(x, y) and x / y are defined as in Section 3.7.Basically, R+ and Q+ are the “usual” remainder and quotient functions, except that remainders are now in the range between 1 and y instead of 0 and y –1.
April 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
13
Numerical Representation of Strings
So whenever y divides x, we do not have a remainder of 0 but a remainder of y, and accordingly the quotient is one number below the “actual” quotient.Therefore, like with the usual quotient and remainder, it is still true that:x/y = Q+(x, y) + R+(x, y)/y,only that now we have 1 R+(x, y) y.We will use the functions Q+and R+to show how to obtain the subscripts i0, i1, …, ikfrom any integerx > 0.
April 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
14
Numerical Representation of Strings
Let us define:u0= xum+1= Q+(um, n)Then we have:u0= iknk+ ik-1nk-1+ … + i1n1+ i0u1= iknk-1+ ik-1nk-2+ … + i1:uk= ikThe “remainders” R+are exactly the values of the im:im= R+(um, n), m = 0, …, k.
April 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
15
Numerical Representation of Strings
This is analogous to our usual base-n notation:u0= xum+1= Q(um, n)Then we have:u0= iknk+ ik-1nk-1+ … + i1n1+ i0u1= iknk-1+ ik-1nk-2+ … + i1:uk= ikThe remainders R are exactly the values of the im:im= R(um, n), m = 0, …, k.
April 16, 2019
Theory of Computation Lecture 17: Calculations on Strings II
16
Numerical Representation of Strings
Example:Find binary representation of number 13:Then u0= x = 13; n = 2u1= Q(13, 2) = 6; i0= R(13, 2) = 1u2= Q(6, 2) = 3; i1= R(6, 2) = 0u3= Q(3, 2) = 1; i2= R(3, 2) = 1u4= Q(1, 2) = 0; i3= R(1, 2) = 1Then w = 1101.Thus k = 3 and we havex = 123+ 122+ 021+ 120
0
Embed
Upload