Publish on 17th November 2019
Category: Birds
0

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

1

The Programming LanguageL

We will explore computability theory using an extremely simple programming language calledL.Let us take a look at this language.Luses variables holdingnumbers. Throughout the course, ‘number’ will refer to anonnegative integer.The variables namedX1, X2, X3, …are theinput variablesofL, Y is theoutput variableofL, andZ1, Z2, Z3, …are thelocal variablesofL.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

2

The Programming LanguageL

We do not have to write the subscript 1, so instead of X1or Z1we can write X or Z.Lalso includeslabels. These labels are namedA1B1C1D1E1A2B2C2D2E2… … … … …Again, the subscript 1 can be omitted.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

3

The Programming LanguageL

AprogramofLconsists of a list (a finite sequence) ofinstructions.What do the instructions look like?There are only three types of instructions inL:incrementdecrementconditional branch

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

4

The Programming LanguageL

In the following list of instructions, the letterVstands for anyvariablein the program, andLstands for alabel:V V+1 increase by 1 the value of thevariable VV V-1 If the value of V is 0, leave it unchanged; otherwise decreaseby 1 the value of the variable V.If V0 GOTO L If the value of V is nonzero, performthe instruction with label L next;otherwise proceed to the nextinstruction in the list.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

5

The Programming LanguageL

These are the only three instructions in ourlanguageL.You will be surprised how powerful this extremely simple programming language is.We just need two more conventions:The output variable Y and the local variablesZiinitially havethe value 0.A program halts when it attempts to move to anonexistent instruction (beyond the end of the list)or branch to a nonexistent label.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

6

The Programming LanguageL

Note that we have an unlimited supply of variables and labels.Moreover, there is no upper limit on the value that a variable can contain.Therefore, the languageLis not a practical language, but it is well-suited for the theoretical evaluation of algorithms.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

7

Sample Programs

Consider the following program:[A] X X-1Y Y+1IF X0 GOTO AWhat function does this program compute?f(x) = 1, if x = 0= x, otherwise.What would we have to change if we wanted to compute the function f(x) = x?

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

8

Sample Programs

The following program computes f(x) = x:[A] IF X0 GOTO BZ Z+1IF Z0 GOTO E[B] X X-1Y Y+1IF X0 GOTO B

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

9

Sample Programs

In the previous example, the linesZ Z+1IF Z0 GOTO Lwere used to implement an instruction that we could callGOTO LFirst, we make sure that Z has a nonzero value, and then the conditional branch (actually, here it is an unconditional branch) is executed.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

10

Sample Programs

From now on we will use themacroGOTO L in our programs.We know that we could always replace GOTO L with itsmacro expansionto obtain a validLprogram.Now remember the program computing the function f(x) = x.Although it computes its output correctly, it deletes (sets to zero) the original input.This is an undesirable behavior, so we should come up with an improved program.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

11

Sample Programs

[A] IF X0 GOTO BGOTO C[B] X X-1Y Y+1Z Z+1GOTO A[C] IF Z0 GOTO DGOTO E[D] Z Z-1X X+1GOTO C

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

12

Sample Programs

The previous program justifies the introduction of a macroVV’The execution of this macro will replace the contents of variable V by those of variable V’ without changing the contents of V’.However, there is one problem:The previous program could rely on the initial condition Y = 0, which is not guaranteed for any variable V.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

13

Sample Programs

To solve this problem, we introduce the macroV0Its macro expansion is:[L] V V-1IF V0 GOTO LOf course, the label L has to be chosen to be different from any other label in the program.Now we can write down the macro expansion ofVV’:

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

14

Sample Programs

V 0[A] IF V’0 GOTO BGOTO C[B] V’ V’-1V V+1Z Z+1GOTO A[C] IF Z0 GOTO DGOTO E[D] Z Z-1V’ V’+1GOTO C

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

15

Sample Programs

Another example: f(x1, x2) = x1+ x2Y X1Z X2[B] IF Z0 GOTO AGOTO E[A] Z Z-1Y Y+1GOTO B

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

16

The Syntax ofL

We will now develop a precise mathematical description of the programming languageL.The symbolsX1, X2, X3, …are calledinput variables,Z1, Z2, Z3, …are calledlocal variables,and Y is called theoutput variableofL.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

17

The Syntax ofL

The symbolsA1, B1, C1, D1, E1,A2, B2, C2, …are calledlabelsofL.For variables and labels, the subscript 1 can always be omitted.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

18

The Syntax ofL

Astatementis one of the following:V V+1V V-1V VIF V0 GOTO LHere, V may be any variable and L may be any label.Note that the statement V V leaves all values unchanged, so it is a“dummy”command.We will later see why it is useful to have V V in our set of statements.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

19

The Syntax ofL

Aninstructionis eithera statement (unlabeled instruction) or[L] followed by a statement (instruction labeled L)Aprogramis a list (i.e., a finite sequence) of instructions.Thelengthof this list is called the length of the program.We also include theempty program– the program of length 0 – in the set of all programs.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

20

The Syntax ofL

While a program is being executed, its variables assume different numerical values.This motivates the concept of thestateof a program:A state of a programPis a list of equations of the formV = m,where V is a variable and m is a number,including exactly one equation for each variable that occurs inP(and possibly equations for other variables).

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

21

The Syntax ofL

Consider the following programP:[A] IF X0 GOTO BZ Z+1IF Z0 GOTO E[B] X X-1Y Y+1Z Z+1IF Z0 GOTO A

Is the listX = 4, Y = 3, Z = 3a state ofP?

Yes.

How aboutX1= 4, X2= 5, Y = 4, Z = 4?

Yes.

And X = 3, Z = 3?

No.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

22

The Syntax ofL

Let be a state ofPand let V be a variable that occurs in .Thevalueof V at is then the unique number q such that the equation V = q is one of the equations in .For example, the value of X at the stateX = 4, Y = 3, Z = 3is 4.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

23

The Syntax ofL

Consider a machine that can execute programs ofL.During program execution, this machine needs to store the state of a program, i.e., keep track of the values of variables.Is there anything else that needs to be stored?Yes, we also need to storewhich instructionis to be executed next.

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

24

The Syntax ofL

Therefore, we define asnapshotorinstantaneous descriptionof a programPof length n to be a pair(i, ) where 1 i (n + 1), and is a state ofP.The number i indicates the number of the instruction that is to be executed next.i = n + 1 corresponds to a “stop” instruction.A snapshot (i, ) of a programPof length n is calledterminalif i = n + 1.If s = (i, ) is a snapshot ofPand V is a variable ofP, then the value of V at s just means the value of V at .

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

25

The Syntax ofL

If (i, ) is a nonterminal snapshot ofP, we define the successor of (i, ) to be the snapshot (j, ) defined as follows:Case 1:Thei-thinstruction ofPis V V+1 and contains the equation V = m.Then j =i+ 1 and is obtained from by replacing the equation V = m with V = m + 1(the value of V at is m + 1).

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

26

The Syntax ofL

Case 2:Thei-thinstruction ofPis V V-1 and contains the equation V = m.Then j =i+ 1 and is obtained from by replacing the equation V = m with V = m – 1 if m 0.If m = 0, then = .Case 3:Thei-thinstruction ofPis V V.Then j =i+ 1 and = .

January 31, 2019

Theory of Computation Lecture 2: Programs and Computable Functions I

27

The Syntax ofL

Case 4:The i-th instruction ofPis IF V0 GOTO L.Then = and there are two subcases:Case 4a: contains the equation V = 0.Then j = i + 1.Case 4b: contains the equation V = m where m 0.Then, if there is an instruction ofPlabeled L, j is the least number such that the j-th instruction ofPis labeled L. Otherwise, j = n + 1.

0

Embed

Upload

toc01-31