Computability: Basic theory of computational science

Discussion was boiling as to whether machines can be calculated electronically just before WW 2 or not. However, Alan Turing was proving positively (general theory of computability). That is the Turing machine that is said today. The greatness of this paper was to describe how to make electronic computers. Today's computers are all based on this paper. Then von Neumann developed into a built-in program computer, but the foundation of the computer remains unchanged. I wrote this book with the topic of today on the basis of my research note on my college days.

The mathematical field of mathematical computability is deeply related to mathematical logic and is a considerably broad field.

A Turing machine
It starts with defining the class of the function in which there is an "actual calculable function", ie an algorithm to calculate its value. The starting point is that if there is an algorithm to execute a certain task, in principle it is possible to produce a computing machine that executes that procedure without vinegar. Such a computing machine is "deterministic" in the sense that its future is all prescribed by the state at a certain point in operation.
We will now give mathematical definitions for mathematical object classes called Turing machines.
It is defined by analogy with certain physically realized computing machines. A mathematical definition of the class of things computed by this Turing machine is made possible. These functions will be called "computable functions". Then let's propose replacing the intuitive concept of "a function that can be actually calculated" with this new concept of "computable function". Whether this replacement is too narrow (that is, does it leave out functions thought to be actually calculated), or is it too wide (ie, it also includes functions not considered to be actually calculated), or , I will set the argument that I will shift after giving various definitions. Concludingly, Alan Turing is clarifying these points.
Let me introduce the proof of Alan Turing.
Although physically realized computing machines have a limitation that the capacity for storing input data m and various intermediate values ​​(for example, partial product in multiplication) arising in the calculation process is limited, here, Please imagine a measuring machine that can print symbols on this indefinitely arranged squares on the tape (below) that stretched to the bottom.



And this machine can take one of a finite number of possible internal states and the next action at the point of thinking is the internal state of the machine at that time and the finite expression on the tape at that time I think that it will be decided by combination of. Furthermore, if the machine were to be affected only by a single tape on the tape, not on all the tapes at a time (let's say that frame "the machine is watching") , The action at the next moment must be determined by the combination of the current internal state and the symbol written on the top that the machine is currently looking at. It is because the physically realized computing machine consists of parts such as gears and vacuum tubes (so the internal state of the machine at any point during operation is dependent on the actual placement state of these parts )), In fact, the only function of the internal state is to be able to decide the next action of the computing machine when given the knowledge of the symbol that is currently being viewed. Here, "the next action" processes that it must be one of the forms shown below. In other words, complete stop of the movement; giving a predetermined change to the sign of the top being viewed; moving one frame to the right or to the left, then giving a predetermined change to the internal state is. Therefore, the internal state is considered mathematically determined by a set of several rules. Of course, this rule specifies, for each of the symbols that the machine can print,