Computer Science : Theory of Computation : Introduction

From bitrary
Jump to: navigation, search

Computer Science : Theory of Computation

Introduction by an Example

Computers run programs. (Obvious, right?) One of the programs can be a car racing game. The car racing game, a program, hereafter P_0, is a simulator that simulates the driving of a car. However, simulators can be created for many things, including computers. There are many kinds of computers and one of the questions is, whether one computer can theoretically execute all of the programs that another computer can? To simplify this contemplation, the different kinds of computers are marked with computer type and in this text the computer types are designated with arbitrarily computer type names: "computer_type_Foo", "computer_type_Bar", "computer_type_Gee".

Suppose a computer C_Foo_1, which is of type "computer_type_Foo", runs a simulator that in stead of simulating the driving of a car simulates the operation of another computer, C_Bar_1, that has a type of "computer_type_Bar". A simulation of a computer simulates how the simulated computer runs one of its programs. In this case the simulated computer is the C_Bar_1. C_Foo_1 can execute any program that the C_Bar_1 can execute, because the C_Foo_1 can execute a simulator of the C_Bar_1 and the simulated C_Bar_1 can execute anything that the C_Bar_1 can execute.

$all\_programs(C\_Bar\_1) \subset all\_programs(C\_Foo\_1)$

If one of the programs that the C_Bar_1 can run is a simulator of computer C_Foo_2 that is of type "computer_type_Foo", then

$all\_programs(C\_Foo\_2) \subset all\_programs(C\_Bar\_1)$

because the C_Bar_1 can execute any C_Foo_2 program by executing the C_Foo_2 simulator with that C_Foo_2 program. Due to the fact that the C_Foo_1 and the C_Foo_1 are of the same computer type, the "computer_type_Foo",

$all\_programs(C\_Foo\_1) = all\_programs(C\_Foo\_2)$

and therefore

$all\_programs(C\_Foo\_1) \subset all\_programs(C\_Bar\_1)$

From Set Theory: $\lbrace \lbrace A \subset B \rbrace \bigwedge \lbrace B \subset A \rbrace \rbrace \Rightarrow \lbrace A \equiv B \rbrace$


$ \lbrace \lbrace all\_programs(C\_Foo\_1) \subset all\_programs(C\_Bar\_1) \rbrace \bigwedge \lbrace all\_programs(C\_Bar\_1) \subset all\_programs(C\_Foo\_1) \rbrace \rbrace \Rightarrow \lbrace all\_programs(C\_Foo\_1) \equiv all\_programs(C\_Bar\_1) \rbrace $

That is to say, if one type of computer is able to simulate the work of another type of computer and that other type of computer can simulate the work of the former, then both of those computer types are able to execute the same programs. If long arrows are used for designating the availability of a simulator, like "A can simulate B", $A \longrightarrow B$, then it is possible to start drawing directed graphs, as shown at the following image.

Bitrary softf1 com Theory of Computation Diagram t1 dia v0.png

Please note that from theoretical point of view all computer types that form a directed cycle are able to execute the same set of programs. Id est according to the above image the computers of type "computer_type_Gee" can execute the same programs that both, computers of type "computer_type_Foo" and computers of type "computer_type_Bar", can execute.

Theory of Computation and the Translation of Programs from one Programming Language to Another

From theory point of view computers are mathematical objects that may have a physical representation, like, for example, RAM-machines have, but they are not required to be physically producible. The "computer" can be a programming language with its stdlib. A translator from one programming language to another can be a combination of a computer simulator and some program that generates the program that the simulated computer will execute during the simulation.

Extra Subjective Notes

At first glance the Theory of Computation seems to be a piece of cake, nothing to it, but the creation of computer simulators can be really hard. That's where the "PhD level material" comes to play.