Turing Machines
The intuition of Turing Machines is a necessary understanding in the science that governs digital computing devices. However, it has much higher significance. It proves outright that formal logic cannot emulate decision making capability (intuition), which is a characteristic of human thinking !!!
‘It proves that algorithmic approach cannot be ever a substitute to human intelligence.’
A Turing Machine is associated with anything that is digital device — from the simplest embedded micro controllers in a flying drone to sophisticated supercomputers. Turing machines are computers in theory — The fundamental logical model of the computer. A modern-day computer has Boolean Algebra implementing this logical model. A practical computer is a multidimensional extension of the concept of Turing Machines. Extensions spanning from memory storage, to peripherals, or to media — everything associated with a ‘computer’ (anything that has an embedded Central Processing Unit at its core).
What is a Turing Machine?
A Turing Machine (TM) is an abstract mathematical model of a computing device. It is based on a formal logical system that governs its behavior. They are abstract and don’t exist as objects. They are conceptual theoretical apparatus, like a blueprint of a building.
Turing Machines were conceived by Alan Turing in his seminal paper, ‘ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM’, published in 1936. Turing’s endeavor was to provide a direct, irrefutable ‘practical proof’ to David Hilbert’s Entscheidungsproblem. The Entscheidungsproblem was a mathematical approach to a possibility looming over mathematicians and logicians — the possibility of one and all assimilating mathematical framework.
History of the Entscheidungsproblem
In the 1690s, Godfrey Wilhelm Leibniz, a German mathematician, after devising his ‘Stepped Reckoner’ mechanical calculator, extended his thoughts to formulating a universal machine, that could verify every mathematical statement. i.e. the machine could say if a mathematically formulated statement was true or false. This was more of a philosophical query than a purely logical one. However, the matter needed a scientific approach to explore and analyze.
In 1928, David Hilbert, a German mathematician, and a proponent of Formalism, proposed a set of three questions, at the International Congress of Mathematicians (ICM), Bologna:
- Was mathematics complete?
- Was mathematics consistent?
- Was mathematics decidable?
Hilbert’s propositions were to direct the research on mathematics and related sciences for another century. The problems were Hilbert’s attempt at proving and reinforcing mathematics as a complete deductive science. He attempted at placing mathematics on an unassailably sound foundation, with axioms and rules of procedure laid down once and for all. The third came to be known as the Entscheidungsproblem (German for ‘Decision Problem’).
The Decision Problem has its significance in Computer Science — it paved way for the first theoretical general-purpose computer. Turing attempted to solve the Decision Problem devising his own ‘machines’, and proving that they would not know for their manner of construction, if they would ever provide an output for a valid input. This came to be known as the Halting Problem.
‘There can be no machine, which, given the construction of a second machine and a finite input, decide whether the (second) machine would finish running or would run forever.’
Note: Some infinite loops can be quite useful. For instance, event loops are typically coded as infinite loops. However, most subroutines are supposed to finish (halt) with intended result(s).
The construction of the machine throws light on its behavior — what does the machine do? We interpret this as an ‘algorithm’ to solve a problem. There can be no universal algorithm that can decide whether a formulated mathematical statement holds or does not.
Note:
- Turing Machine is a highly intuitive concept. And to elucidate the concept itself is serious effort. We quote some statements and sentences ‘as is’ from the cited literature for this reason.
- We focus on the intuitions behind the theory rather than the proof of the theory. Turing paper could be downloaded here.
The Turing Machine
Let us imagine a device with a finite, discrete set of possible states, q1, q2, …. qn. These will be called the internal states of the machine; Turing himself called these m-configurations or machine configurations.
The machine is supplied with an infinite paper tape divided into sections (or squares), each square carrying a symbol. For example: blank, 0, 1 or a number. At any time, there is one square on the tape that is being scanned by the machine. The “scanned symbol (r)” is the only thing that the machine is “directly aware” of, as its environment.
The Behavior of the machine can be summarized as follows:
1. It either erases or prints a symbol in the scanned square.
2. It either moves the tape left or right.
3. The Machine may change its state.
Assume that qn is the current state of the machine. The pair (qn, r) will be called the “configuration”. Thus, the current state and scanned symbol (r) determines the possible behavior of the machine. If the machine is supplied with a tape and set in motion, starting from the correct initial m-configuration, the sequence of the symbols printed by it will be called the sequence computed by the machine.
Example of a simple Turing Machine
A machine that computes (prints on a blank tape) the simple sequence of 0s and 1s: 01010101…
- The machine is to have four m-configurations ‘b’, ‘c’, ‘e’, ‘f’ and is capable of printing ‘0’ and ‘1’.
- ‘R’ means “the machine moves so that it scans the square immediately on the right of the one it was scanning previously”. Similarly, for ‘L’.
- ‘E’ means “the scanned symbol is erased”
- ‘P’ stands for “prints”. ‘P0’ stands for “print 0”. ‘P1’ stands for “print 1”.
Complex scenarios of Turning Machines and its capability to prove that algorithms CANNOT be ‘self-aware’ is shown under Annexure of this article.
Artificial Intelligence and Turing Machines
What we know as Turing Machines are algorithmic processes. There can be no ‘angel-eye’ process that can watch over a second process. This may be explained by an analogy of a blind man in a desert.
Imagine a blind man on a horse who has been lost in a dry desert with supplies enough for a week. Also, let us suppose the gait lengths of the horse’s trot are slightly different for the near side (left side of a horse) than for the offside (right side). Without a navigating mechanism perceivable by touch, the rider is bound to go around in circles, for the deformity of gait in his horse. The lesser perceivable the gait difference, the larger would the circle be. He would continue in this loop, until he decides to break out of it, which he is very likely to, even maybe after trotting around for a week. The trot of the horse seeking its destination is a mechanical process here. It is an algorithm that runs — either to its good effect or not.
The decision could be his desperation in not reaching the end of his desert, or simply ‘a flare in his gut’. For whatever reason, our man stops his horse to contemplate the ‘situation’. Let’s suppose our horse-and-rider pair is a Turing Machine and that they fall into the loop in an hour they hit the desert. The pair simply relies on the horse’s trot seeking its end — their destination. In short, they have nothing to count upon, but the mechanical procedure of the trot. Turing’s insolvability of the halting problem simply implies that our equestrian Turing Machine is never going to break out of this loop, provided for its ‘dud’ gait. In other words, it fails to trigger ‘fire in the gut’ by itself, which made the horse rider of earlier scenario reflect on his ways.
The fire in the gut
Machines are algorithms in theory. The Entsheidungsproblem and Turing’s halting problem and its proof by contradiction implies one thing — we cannot synthesize the ‘fire in the gut’ algorithmically. And we know the fire in the gut relies on insight, intuition. It’s a ‘feeling’, not a habituated rational activity. It distinguishes analytical reason and human consciousness. A formal mathematical system cannot synthesize human consciousness, insight, or intuition by any means.
The Decision Problem
‘Can we jump over the decision problem with a random choice?’
Well, imagine that we are playing with a person (or a computer) a game of chess. Our opponent makes moves alright, according to the rules of the game. But what if the player isn’t applying his ‘creativity’ at each move? The decision making at each step-in relation to previous steps is of supreme importance in playing a game of chess. We have dozens of moves we could legitimately make at any stage of the game. If at each stage, we run a (pseudo again, and algorithmic!) random number generator to choose a move, we might be having a dunce as an opponent against all odds. We better not play!
Next week: Technological Monopoly.
Previous week: Digital Revolution — The Timeline.
First week: Can Machines Think?
Annexure
Computable sequences
Turing originally devised the concept of Turing machines in the context of the string of symbols (0 and 1 in the example TM) printed out on the infinite tape. These strings of symbols are called computable sequences. This could however be extended to computable numbers (e.g. computing the value of pi), or computable functions (e.g. the value of sin x). The line of attack on the decision problem remains the same. Conversely, a computable sequence is a sequence of symbols which could be simulated by a TM, i.e. by an algorithmic procedure (or a computer program in the context of programming languages).
We adopt a nomenclature convention for Turing Machines that compute different sequences. Turing called these Standard Descriptions (S.D), or more conveniently for logical treatment, Description Numbers (D.N).
Standard Descriptions (according to Turing’s original nomenclature) for a Turing Machine could be DADDCRDAA, DAADDRDAAA, DAAADDCCRDAAAA, DAAAADDRDA, etc.
Description Numbers could be 31332531173113353111731113322531111731111335317, 3133253117311335311173111332253111173111133531731323253117, etc.
Insolvability of the Decision Problem
We may come up with a list of Turing Machines as T1, T2, …, T3133253117311335311173111332253111173111133531731323253117, …, Tn. n standing for the description number of the TM.
We may also contemplate a Turing Machine Tu, the function of which is to accept the description number of another Turing Machine Ti, and act upon subsequent symbols of the tape acting as Ti. This ‘universal’ TM would also have a number, say u.
The list of Turing Machines, all starting from T1, T2, T3, … are not working Turing Machines. A vast majority of them are ‘duds’. Turing, using Cantor’s Diagonal Slash Argument, effectively could come to a conclusion that a machine that accepts a Description Number as the input and provides a ‘true’ or ‘false’, as whether the machine is a dud or not respectively, is an impossibility. The Entscheidungsproblem has no solution !!! i.e. there exists no Turing Machine H, which could state that a Turing Machine Ti will halt (succeed) or not — i.e. it keeps operating indefinitely or not.
Citations:
The Emperor’s New Mind, Roger Penrose, Oxford University Press
On Computable Numbers, with an Application to the Entscheidungsproblem, Alan Turing
