Before any machine is designed, a prototype or a model is constructed. This model gives an overview of what the machine will do, what will be the inputs and what will be the outputs. The inner working of the machine depends on the relation between inputs and outputs. A model is not the real thing,  a model is created to understand how to build the real machine. The basic model of computation (also called the Model of Computing), serves the same purpose.  A model of computing defines the capabilities of an abstract computer. Research on formal models of computation was initiated in the 1930s and 1940s by Turing, Post, Kleene, Church, and others.

A model of computing specifies:

1. What operations an algorithm can do (like addition, subtraction, moving data from one memory location to another), and
2. Cost of operation. The main resources of a computer are the CPU time and memory (random access memory). So, an efficient algorithm should require the smallest possible memory and execute as quickly as possible. A programmer should write a program that uses these two resources efficiently. So, the cost of computation involves CPU time and memory. Certain operations are faster than others, e.g., addition is faster than multiplication and subtraction is faster than division. Sometimes addition and subtraction will also require lesser memory.
3. A model of computation is not a physical device, it is a mathematical idea. Based on this model of computation we build an algorithm.
4. A computer does not only do calculations, it also communicates with its environment. The environment of a computer is its memory and CPU. So a computer exchanges data between memory and CPU.
5. Ofcourse, a model of computing should be implementable by a physical machine.

We know that a program is written in a computer language (like Python, Java, etc) and a computer is needed to run a program. This relation between program, programming language and a computer is shown on the left side in the above diagram. In a similar way, the relation between an algorithm, pseudocode and model of computation is shown on the right side of this diagram. The double-headed arrows indicate that there is an equivalence between the two blocks. So, from this diagram we see that:

(i) the mathematical equivalent of a program is an algorithm (and vice-versa),  

(ii) the mathematical equivalent of a programming language is pseudocode or statements  steps in structured English, and 

(iii) the mathematical equivalent of a computer is the model of computation. 

There are many models of computation but we shall state only a few here and study the most basic of these, i.e., the Random Access Machine. A few models of computation are:

1. Random Access Machine
2. Turing machine
3. Combinatory logic.
4. Finite State Machine

Random Access Machine (RAM): The abbreviation RAM also stands for Random Access Memory, but here we are using the abbreviation for Random Access Machine. A Random Access Machine is a mathematical model of a computer. Such a Random Access Machine consists of a stored program, a central processing unit and a computer memory. Any location in the memory can be accessed directly without having to read the earlier locations and that is why the word ‘random’ is used. Such a mathematical model of computing allows the following operations: addition, subtraction, multiplication, division and comparison. Each operation is assumed to take a constant time.

Need for studying models of computation:

1. Natural languages like English, Hindi are rich languages because a wide variety of ideas can be expressed through these languages. But the drawback of these languages are that they can be ambiguous. So a word or a sentence may have more than one meaning which can cause confusion. 
2. A programming language should be able to express complex ideas in a simple and unambiguous way. 
3. Expressiveness of a programming language means how easily the programmer can express a complex idea. 
4. For example, in many programming languages we come across the statement x = x + 1. This can also be written as “ADD 1 TO X GIVING X” or in a simple way as x++. 
5. So we see that expressiveness is concerned with the meaning not with the way a statement is written. 
6. The expressiveness of a programming language is concerned with its semantics and not with syntax. Syntax is concerned with grammar of the language like whether to put a semicolon or colon, etc) and semantics is concerned with the meaning of the statement.
7. Expressiveness of a programming language is what you can make a machine do; expressiveness is not concerned with how a human being understands the statement.
8. Different languages have different levels of expressiveness.
9. A language like Python or R is more expressive than C language.

A complicated software may be developed using more than one programming language. For example, many IoT systems may be developed using two languages because one language (like C) will be easier to program in (more expressive) for some tasks, and another language like assembly language will be faster to execute. A system that uses two or more languages is called a heterogeneously programmed system. Modules of the system developed in one language must communicate without errors with modules developed in another language. We say that the modules are interoperable.

Categories: Blog, Computer Science, Programming

Tags: Basic model of computation, combinatory logic, finite state amchine, FSM, importance of models of computation, Kleene, model of a computer, model of computing, need for studying models of computation, random access machine, Turing machine