Theory of Computation| COMP 203 | 1- Definition of L-language

Content : 00:00 definition of L-language 16:25 program 1 (simple) 21:17 program 2 ( f(x) =x ) labels input variables output variables local variables instructions Theory of Computation fb :   / science-corner-111220231102483   نظرية الحوسبة نظريات الحاسابات شرح computability بالعربى Theory of Computation بالعربى Theory of Computation Book : COMPUTABILIW, COMPLEXITY, AND LANGUAGES FUNDAMENTALS OF THEORETAL COMPUTER SCIENCEE COMPUTABILITY : A Programming Language Our development of computability theory will be based on a specific programming language Y". We will use certain letters as variables whose values are numbers. (In this book the word number will always mean non- negative integer, unless the contrary is specifically stated.) In particular, the letters X1 X2 X3 ... will be called the input variables of Y, the letter Ywill be called the output variable of Y, and the letters Z 1 Z 2 Z3 ... will be called the local variables of Y. The subscript 1 is often omitted; i.e., X stands for X1 and Z for Z 1. Unlike the programming languages in actual usc, there is no upper limit on the values these variables can assume. Thus from the outset, 5Y must be regarded as a purely theoretical entity. Neverthe- less, readers having programming experience will find working with 5" very easy. In 5Y we will be able to write "instructions" of various sorts; a "program" of 5Y will then consist of a list (i.e., a finite sequence) of instructions. For example, for each variable V there will be an instruction: V+--V+ 1 A simple example of a program of Y' is X*-X+ I X*-X+I "Execution" of this program has the effect of increasing the value of X by 2. In addition to variables we will need "labels." In Y' these are A, B, C1 D, E1 A 2 B 2 C 2 D 2 E 2 A 3 ''" Once again the subscript 1 can be omitted. We give in Table 1.1 a complete list of our instructions. In this list V stands for any variable and L stands for any label. Table 1.1 Instruction Interpretation V - V + I Increase by 1 the value of the variable V. V - V - I If the value of V is 0, leave it unchanged; otherwise decrease by I the value of V. IF V # 0 GOTO L If the value of V is nonzero, perform the instruction with label L next; otherwise proceed to the next instruction in the list. These instructions will be called the increment, decrement, and conditional branch instructions, respectively. We will use the special convention that the output variable Y and the local variables Zi initially have the value 0. We will sometimes indicate the value of a variable by writing it in lowercase italics. Thus x, is the value of X,. Instructions may or may not have labels. When an instruction is labeled, the label is written to its left in square brackets. For example, [B] Z - Z - I In order to base computability theory on the language Y', we will require formal definitions. But before we supply these, it is instructive to work in- formally with programs of Y'. computability theory computability theory pdf computability in toc computability theory books computability and complexity computability معني computation theory computation theory شرح بالعربي compute يعنى ايه computation معناها بالعربي compute معنى computations معني l computation definition l computational resources f# computation expressions f# computation expressions monad