toc01-31

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 V0 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 X0 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 X0 GOTO BZ  Z+1IF Z0 GOTO E[B] X  X-1Y  Y+1IF X0 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 Z0 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 X0 GOTO BGOTO C[B] X  X-1Y  Y+1Z  Z+1GOTO A[C] IF Z0 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 macroVV’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 macroV0Its macro expansion is:[L] V  V-1IF V0 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 ofVV’:
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 Z0 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 Z0 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 V0 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 X0 GOTO BZ  Z+1IF Z0 GOTO E[B] X  X-1Y  Y+1Z  Z+1IF Z0 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 V0 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.