The grass

In this section we want to give the formal definition (and therefore objective) of "automatic work" through the definition of Turing machine. The aim is to make it clear also sensitively what it means to do a job automatically.

Informal description of Turing Machine: See the Informal description of Turing Machine on Wikipedia. A nice picture of a Turing machine is given below.

 

Now, let's give the following

Formal definition of Turing Machine: A deterministic Turing machine with one tape and five field instructions (which we abbreviate with the term MdT1n5i), is the following sextuple:

T=(S, s0, F, A, β, δ )

where:

  • S is a finite non-empty set called set of states of the machine T;
  • s0 is an element in S called initial state of T;
  • F is a subset of S called set of final states of T;
  • A is an alphabet called tape alphabet of T;
  • β is a character in A which is called blank character of the tape of T;
  • δ : S x AS x A x {<, -, >} is a function called transition function of T;

If δ(s, a) = (t, b, m), the corresponding quintuple (s, a, t, b, m) can be considered as the instruction that runs when the machine is in state s and the I/O head reads the symbol a in the box/cell on which it is positioned. The instruction run implies 1) the transition to state t, 2) the writing of the character b in the cell on which the head is positioned, and 3) the head movement on the tape as follows:

  • one position to the left if m = <,
  • no movement if m = -,
  • one position to the right if m = >,

Note that this definition is based on the concept of set (which is a primitive concept <=> we all agree on the concept of set) and function (= subset of n-tuples of elements in the sets). Also at every moment, the machine configuration (= the state in which the machine is located, what is written on the tape and where the head is positioned on the tape) is defined (recursively, mathematicians would say) by the transition function δ from the configuration in the previous instant. All this means that the definition of Turing Machine is formal and therefore objective. In other words, it is a valid definition in the mathematical formal language and therefore has the property of objectivity typical of the logical deductive mathematical method (invented by Euclid). In general, any mathematical definition of a set of rules (such as those that govern the Turing machine) is referred to as a computational model.

In order to sensitively understand the characteristics of an automatic work, we do the following experiment. We choose at random a Turing machine with four states, say S = {0, 1, 2, 3}, and with an alphabet of the tape being composed of three symbols, say A = {a, b, c}. Status 0 in S is the initial state and the symbol c in A is the blank symbol of the tape. To identify a Turing machine we are missing to define the set of final states F and the transition function δ. We will choose these last two things at random. The reason for this is that I want to focus your attention on the ways in which work is done automatically and not on the purpose of the work. In other words, we define a system that will probably do unnecessary work, but that will do it automatically (because the system is a Turing machine). Let us proceed to the choice of F. For each state s in S toss a coin; if the outcome is head define s in F (i. e., s is a final state) if the outcome is tail define s not in F (that is, s is not a final state). Flipping the coin four times it came out the sequence (Cross, Head, Cross, Cross), and so F = {1}. Let us proceed with the random choice of the transition function δ : S x AS x A x {<, -, >}. For each pair was s0 in S and symbol a0 in A, we randomly choose the value of δ(s0, a0) of the transition function associated with the pair (s0, a0). In particular, we randomly choose a state s1 in S (representing the new state), we randomly choose symbol a1 in A (which is the new symbol) and choose at random a move m in {<, -, >} (which represents the movement of the machine head on the tape, where the symbol < represents a left head movement of one tape cell, - represents no movement of the head and > represents a right head movement of one tape cell). Each one of the 12 = 4 x 3 quintuple (s0, a0, s1, a1, m) <=> δ(s0, a0) = (s1, a1, m) is a randomly chosen instruction of our Turing machine. Proceeding in this way, I got the following instructions:

(0, a, 2, b, >),
(0, b, 2, a, -),
(0, c, 2, c, <),
(1, a, 2, c, >),
(1, b, 1, a, >),
(1, c, 3, b, -),
(2, a, 3, a, >),
(2, b, 0, a, >),
(2, c, 1, a, -),
(3, a, 1, c, >),
(3, b, 3, c, -),
(3, c, 1, c, -).

Note that, since state 1 is a final state (the only one in this case), the instructions (1, a, 2, c,>), (1, b, 1, a,>), (1, c, 3, b, -) are unnecessary because as soon as the machine is in state 1 it stops. So our Turing machine is described by the following set of instructions:

(0, a, 2, b, >),
(0, b, 2, a, -),
(0, c, 2, c, <),
(2, a, 3, a, >),
(2, b, 0, a, >),
(2, c, 1, a, -),
(3, a, 1, c, >),
(3, b, 3, c, -),
(3, c, 1, c, -);

with the convention that if the instructions are not defined for a certain state (in our case, the state 1) then this state is a final state. Randomly choosing an input string I got (remember that the symbol c is the blank/empty box symbol of the tape):

...ccaacbbcabcabacc... .

Hence, in our case we assume that, at the beginning of the computation, the head is placed in the box containing the bold underlined symbol of the input sequence (which in our case contains the symbol a). The initial configuration of the computation is therefore the following:

Execution step Machine state Tape content and head position
0 0 ...ccaacbbcabcabacc...

Starting from this initial configuration, the computation takes place according to the following sequence of transitions from one configuration to the next. Since the machine is in state 0 and the head reads the symbol a, the machine executes the instruction (0, a, 2, b, >). Hence, it goes to state 2, it writes b in the cell and then it moves the head one cell to the right. In this way, the machine goes in the configuration:

Execution step Machine state Tape content and head position
1 2 ...ccbacbbcabcabacc...

Now, since the machine is in the state 2 and the head reads the symbol a, it executes the instruction (2, a, 3, a, >). Hence, it goes to state 3, it writes a into the cell and then it moves the head one cell to the right. Therefore, in the second step, the machine must be in the configuration:

Execution step Machine state Tape content and head position
2 3 ...ccbacbbcabcabacc...

Since the machine is in the state 3 and the head reads the symbol c, it executes the instruction (3, c, 1, c, -), it then goes into state one, its head writes c and stands still. Hence, in the third step, the machine must be in the configuration:

Execution step Machine state Tape content and head position
3 1 ...ccbacbbcabcabacc...

As the machine entered the final state 1, the computation ends, and the machine's output is what is written on the tape. In summary, our Turing machine chosen at random with the following instruction set:

(0, a, 2, b, >),
(0, b, 2, a, -),
(0, c, 2, c, <),
(2, a, 3, a, >),
(2, b, 0, a, >),
(2, c, 1, a, -),
(3, a, 1, c, >),
(3 ,b, 3, c, -),
(3, c, 1, c, -),

if it is given the randomly chosen sequence: ... ccaacbbcabcabacc ... as input, it performs the following computation/execution steps:

Execution step Machine state Tape content and head position Executed instruction
0 0 ...ccaacbbcabcabacc... (0, a, 2, b, >)
1 2 ...ccbacbbcabcabacc... (2, a, 3, a, >)
2 3 ...ccbacbbcabcabacc... (3, c, 1, c, -)
3 1 ...ccbacbbcabcabacc... HALT

See the following Turing Machine simulator. In the simulator you can enter (by copying and pasting) our randomly chosen Turing machine and make it compute on our input string "aa bb ab aba" which was randomly chosen (note that the blank symbol in the simulator is the empty space " ". Also, get rid of the ",".).

We conclude this section with some comments.

Comment 1: the automatic way of working is human (that is, man is a machine). This is because a human being is always able to simulate a machine (it is what we did in this section: we simulated our Turing machine chosen at random). Usually, however, humans find it convenient to let machines do the automatic jobs. In this way, they can devote their time to do something else which is more interesting. In other words, we humans conveniently use machines as slaves. Besides, nowadays machines are also much much faster than humans to carry on automatic jobs (ie, the machines are fast slaves).

Comment 2: an information source can automatically communicate (or via algorithms) with a recipient by sending a Turing machine (or equivalently, an algorithm or program). The recipient will get the communicative message by simulating the received Turing machine on some input sequence or by executing the Turing machine on any Turing machine simulator.

Comment 3: automatic communication is an objective way to communicate (the only objective way to communicate that I know of). By this I mean that all the recipients can only interpret the received message (an algorithm) in the same way. This is because the message is encoding a set of rules defined in the logical deductive mathematical system. For example, having sent our Turing machine to various recipients along with our input sequence "...ccaacbbcabcabacc...", we are sure that in the second step of computation, all the recipients simulating the machine are in the state 3 and have the sequence "...ccbacbbcabcabacc..." written on the tape (somehow we are able to read minds !! and/or preview the future !!). In particular, if the same program is made running with the same inputs on two different machines (even belonging to two separate individuals), the two machines will give the same output (i. e., the machines are objective).

Comment 4: the automatic communication is mass communication media in that it can quickly reach a lot of people/systems. This is because usually the transmission of the message is carried out automatically by computers, which are very fast nowadays.