 Publications: 64 | Followers: 0

## toc04-16

Publish on Category: Birds 0

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+2u2…Xm+nunObviously, 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 thate(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
Letbe some collection of partially computable functions of one variable.We associatewiththefollowing index set R:R= {t N | t}.Rwill 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):Letbe a collection of partiallycomputable functionsof one variable. Let there be partially computablefunctions f(x) andg(x) such that f(x) belongs tobut g(x) does not. ThenRisnot 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 collectionbut 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 = iknk+ ik-1nk-1+ … + i1n1+ i0n0x = 3102+ 7101+ 2 = 372.If w = 372 is anoctalrepresentation of an integer, then we would have n = 8 and therefore:x = 382+ 781+ 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 = iknk+ ik-1nk-1+ … + i1n1+ i0n0.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 = 333+ 132+ 231+ 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= iknk+ ik-1nk-1+ … + i1n1+ i0u1= iknk-1+ ik-1nk-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= iknk+ ik-1nk-1+ … + i1n1+ i0u1= iknk-1+ ik-1nk-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 = 123+ 122+ 021+ 120

0

Embed

Share