Friday, April 20, 2007

7 - Detour - Universal Turing Machines

What kind of a machine is that ?

I will explain but first let us look closely into what lies inside a computer. In fact if you look closely, you will find that at the lowest level, all that is there is a series of zeroes and ones. These symbols are grouped to represent bits, bytes, and then either pieces of data or pieces of logic that operate on the data that are called programs. The bottom line is that a huge collection of binary digits (1,0) can, and does, contain meaningful information.

What kind of information ?

As I said, there are two kinds of information ... data and programs. Consider a computer that calculates the monthly salary in a company. First, it must have information about each employee ... name, salary, days worked, perquisites .... this is referred to as data. Secondly, the computer must know the logic with which salary is calculated and taxes are deducted ... this is referred to as the algorithm or the program.

But both the data and the algorithm are finally stored in the computer as a series of zeroes and ones.

Yes, but people who use the computer and the computer itself knows which is where. Without going into great detail, let us accept that the logic that helps the computer to distinguish data from program is coded in the form of a higher-level program loosely referred to as the operating system. Classical computer programming techniques teach that data and programs be kept separate from each other and all computer systems, from mundane ones that calculate salary to extremely complex ones that send rockets to Mars, work on the basis of this fundamental principle -- without any exceptions.

So where does the Turing machine come in ?

The Turing machine is a mathematical construct that represents a hypothetical computer, and was conceived by Alan Turing[1] to model the most general of all computers. This computer has the capacity to store an extremely large number of binary digits (0’s and 1’s) and since it has no physical wear and tear, it can go one working for a very long time without any degradation of speed. The Turing machine can at any instant of time be in any one of many internal states. Data is fed into the Turing machine as string of binary digits on a very long tape. The machine also has a set of rules that specify what action to take when it reads a binary digit of data. The machine operates on the following very simple principle :

* Read the digit on the input tape that is in front of the machine
* Determine the current internal state of the machine
* Look at the set of rules and do these three things ....
+ Either change the digit on the tape OR leave it alone
+ Either move one position to the left OR to the right
+ Change the internal state of the machine and continue OR halt




A Turing machine is uniquely specified by the collection of states that it can be in and by the set of rules that it obeys. The Turing machine is the mathematical basis of any computer system and it has been mathematically proven that any problem, or situation, that can be resolved in a logical and rational manner, can be simulated on a unique Turing machine. Unfortunately, most problems dealing with human behavior cannot be directly modeled on a standard Turing Machine.




That is unfortunate. So how is relevant for us ? In this discussion …

We need to introduce a slightly more complex concept of the Universal Turing Machine.




What is that ?

The collection of states that a Turing Machine can be in and the set of rules that it obeys can be represented as a set of binary digits as well. This set of binary digits is similar to the regular set of binary digits that constitute the data, though the information encoded is quite different. Hence this bigger set of binary digits can be viewed as the input data to another Turing Machine. This higher level Turing Machine, generally referred to as the Universal Turing Machine, with its own collection of states and rules, can then simulate any other Turing machine .... by first processing the digits that represent the lower level Turing machine and then processing the digits that constitute the data.





The concept of the Universal Turing machine (UTM) is based on solid, mathematical logic and the proof of its existence is a significant mathematical achievement. There is nothing arbitrary about the UTM except that it is generally not known if or when the machine will stop processing the stream of binary digits. This means that the machine just might go on processing digits forever without ever arriving at a final answer. This solution is not acceptable to any mathematician ... but fortunately, as we will see later on, this limitation is not significant for the purpose of our analysis here.

So are you saying that you can model the mind as a Universal Turing Machine ?

Not so much as the mind but perhaps the thinking process is my end-game but before that, I have to first introduce you to another idea – that of self replicating programs.

Is that another oddity, from the world of computers ?

Yes and in general, such programs have very little commercial utility but for the fact that such techniques are used by malicious persons to create computer viruses that have very high nuisance value. When such a program executes, it creates an accurate copy of itself on the hard disk of the computer.

From a strictly mathematical point of view, self-replicating programs should satisfy two conditions


* the parent or the child program should be self contained and must not use any intermediate data file and
* the execution of the program should result in the creation of executable child code. No extra steps should be required to compile the source code of the child.

However, for all practical purposes, we can relax these assumptions and conceive of a program that, as it executes, reads some data from a file and makes some changes in it. The actual executing program is quite primitive and simple. However complex logic and decision events are embedded as data in the data file which gets changed when the program executes. So when the same program is executed a second time, it reads in a different set of logic and decision events and in all probability behaves in a manner that is different from its behavior during the first execution. Incidentally, it would also change the data file as well, which would affect its behavior on the third run ... and so on. A trivial example will make this clear.

A trivial example :

Let us assume that the data file has three numbers that are initially set to some arbitrary value between 1 and 10. The program has the capability to generate a beam of light where the proportion of the primary colours is in the same ratio of these three numbers .. so it generates a coloured beam. This beam of light is reflected back by a screen of some particular colour. The laws of physics determine the proportion of each primary colour in the reflected beam -- a red screen will reflect red light the most. The reflected beam is analyzed and the proportion of each primary colour is determined. The values of the three original numbers in the data file are UPDATED to bring the relative ratios closer to the ratios as analyzed in the reflected beam. Then the program terminates.




If the program is run a second time, the light it will generate will be closer to the colour of the reflecting screen and again the data values will be updated. Successive executions of the program will make the colour of the generated light closer and closer to the colour of the reflecting screen .... unless of course the colour of the screen is suddenly changed. In that case the experiment will, in effect, restart from the beginning. [Stage I]

Let us now isolate the physical equipment that generates and analyses light and treat it as a black box (BB1) that receives three numbers (coded in binary format) from the computer and sends three numbers back to it. A very large part of the rest of the computer program can be coded in appropriate binary code and placed on the data file itself. However, the logic is designed in such a manner that when the program executes it alters only that part of the file that has the colour values and not any other part. [Stage II]

Let us, next, isolate the enhanced data file, which contains the code-logic and the changeable data, and view this as another black box (BB2). Once again, the computer reads a stream of binary digits from BB2 and sends another stream of digits back to it. [Stage III]

What is left on the computer is a very core program that talks to two black boxes BB1 and BB2. If you think about it, you will realize that this core program is nothing but a Universal Turing Machine (UTM). All that it is doing is reading a stream of binary digits, deciphering some logic and acting on some data. This will become even clearer if we merge BB1 and BB2 into just one black box and add a simple multiplexing device at each end that allows the computer to communicate with both BB1 and BB2 over a single digital data channel. [Stage IV]

The trivial example of shining a light is used as an example to prove a point. The theoretical foundations of the UTM guarantee that any real world situation, that involves learning about and altering the physical environment, can be modeled on it though the size of the data file [ BB2 ] and the complexity of the physical devices [ BB1 ]will be enormous.

What the mathematics fails to guarantee is that even if we have the most powerful computers, the UTM will finish processing BB2 and achieve the result expected in BB1 in a finite amount of time.

Why are we spending so much time with the Universal Turing Machine ?

Let us begin by considering the human mind, or perhaps the brain, to begin with, as a Universal Turing Machine. The human being is born and a corresponding UTM starts to process data.

But where is the logic stored for the ‘core’ UTM ?

Let me assume that the initial logic could be stored in the hardware, or firmware of the human brain. As a very rough and initial analogy, the neurons in the human brain can be, at least initially, thought of as the equivalent of the logic gates that a computer chip has. Though range and versatility of the human brain is prodigious in terms of adaptability, the analogy is not too fallacious, especially because the ‘core’ code of the UTM is still finite. This is in contrast to the far larger and infinitely complex code required to handle all human interactions.

Where does it get its stream of input data ?

The input data stream begins, in the womb with every piece of external stimulus that it receives, perhaps unconsciously. In fact, this is the only data available to a child as it drops down the mysterious stairs of birth. Subsequently, additional channels of communication open up as the sense organs become activated and the person sees, reads, hears, touches, feels and in general learns about the environment. In all cases, the electrochemical transmission of the nervous system is the one and only data channel, carrying a flood of input into the UTM.

So there is no need yet to postulate a divine agent that breathes in life and spirit into the physical body.

The stream of information that floods in, is huge, far more than what can be stored in any computer today. As in the case of any UTM, it consists of data, information on how to process the data and possibly meaningless junk.

Meaningless, in this case, is a relative word. An input data stream has any meaning, if and only if, the logic to process that data stream has already been processed by the UTM. For example, a person who has never learnt mathematics would find mathematical symbols meaningless. From this point of view, most of the input data stream would be perfectly meaningless but for occasional strings of logic and data.

So it is as if the sentient entity is dipping into a universal pool of knowledge ?

The physical universe -- every single atom, molecule or higher-level objects like chairs, tables, books, movies .. in fact everything -- constitute a vast input data tape for the Universal Turing Machines that represents every conscious or living organism. Each living entity is an UTM that is processing a part of this data pool to which has physical access. Here are some examples of input data :
* the sight of a sunset
* the sound of a bell or mantra
* the smell of a flower
* the sensation of breeze on the face
* the physical action that has an impact on any part of the human body
* the knowledge of the existence of the stars and planets.
* the knowledge of scientific truths - Relativity, Quantum Mechanics, Evolution.
* the knowledge of the Upanishads

Every action that a person takes, from writing a book to leaving a banana peel on the road, can have an impact on every other person. This is because every UTM is not merely reading the input tape but also writing back on it -- modifying some part of the data pool.

How does the UTM write back on the tape ?
* it alters the position of some atom, molecule or higher-level object or creates new combinations of primitive objects.
* it generates new ideas, new patterns of knowledge, and leaves it behind in the form of books and other records.

The data in the pool is changing continuously. Can we visualize this data pool ?

One way of doing so would be model this data pool as network of binary digits strewn along the surface of sphere. As an UTM reads, processes and writes on one part of the data pool, it picks up the logical instructions to move to and read data from some other part of the surface -- this movement can be physical, one goes somewhere or intellectual, a new chain of thought is explored. The surface of a sphere is finite but unbounded, so there is no possibility of reaching the edge of this vast pool and then falling off !

However, this spherical surface is only an analogy. The actual data exists as information about the location and disposition of atoms and higher-level objects including, but not limited to intellectual property like books. To the UTM in the human brain, all this information appears as a stream of binary digits being fed in from an infinite tape.

How does consciousness appear ? How does intelligence reveal itself ?

Intelligent entities are often seen take action as a response to certain stimuli. Beginning with a simple thermometer where the mercury expands with the rise of temperature to sophisticated closed-loop control systems that measure various parameters and regulate complex machinery, the relation between input and output is governed by logical rules or algorithms. The UTM, as a model for the human thinking process, is the ultimate algorithmic device in this regard.

However, it is believed that consciousness is not algorithmic and hence cannot be modeled on the UTM. The line of reasoning behind this belief is as follows
* Consciousness is associated with desire or will. I raise my hand not because I have to but because I want to. No thermometer would want the mercury in it to expand.
* Consciousness is associated with self-awareness. A conscious entity is aware of itself. It needs no external input realize that it exists and is capable of raising its arm.

So how is it possible to have an algorithm based UTM that generates tangible, rational and meaningful output when it has no tangible input stimulus ? And that too when the output could be different in each case. For example one person draws a picture, another decides to go scuba diving and a third asks questions about the existence of God.

In each case, the particular UTM that represents the individual is indeed processing an input data stream, consisting of memories of past input and immediate input from the five senses, but this input is not perceptible or not intelligible to any other UTM in the vicinity. As we have said in the past, the data pool from which each UTM draws input is vast and every UTM is processing some part of it. Moreover, most of the input data is meaningless unless the algorithm to decode it has been encountered or read-in before.

So even if two UTM read the same part of the data pool, though this is unlikely, UTM-1 would not make any sense of the data but UTM-2 would understand it and react in some tangible way. UTM-1, that is trying to observe conscious behavior in UTM-2, would not perceive the data at all and conclude that UTM-2 is not reacting to any external stimulus but instead acting out of its own consciousness. Can a colour-blind person ever understand the exclamation of wonder that is expressed when a person with normal vision sees a rainbow ?

So to summarize what I have said so far …
* It is theoretically possible to envisage a computational device, a Universal Turing Machine, which can process a very large stream of data. The logic to process the data can be embedded in the data itself. However, the act of processing of the data is not always guaranteed to terminate with a meaningful answer. Real devices will decay and disintegrate before even a fraction of the available data is processed successfully
* The human brain ( or mind ) could be perceived as such a computational device such that, at birth, the neurons are arranged in such a manner that they can be modeled as a Universal Turing Machine.
* The physical environment, consisting of every atom, molecule and higher level object together with the various patterns they form among themselves represent (a) a vast pool of data equivalent to the input of an UTM and (b) this data pool is the repository of all knowledge and information available in the universe at a point in time. This data flows into the UTM or the conscious mind that it models, over the normal physical channels of the five senses. There is no need to postulate any extrasensory communication mechanism.
* This data pool is not static. UTMs corresponding to every conscious entity in the universe are reading data from some part of the data pool and writing back into the data pool. The process of writing back is done by subtle or significant changes in the position of some physical object ... small or large. The mere act of breathing is enough to change some data as well.

This line of logic (or speculation) can be faulted on the ground that the mental process is not logical and hence cannot ever be modeled by an algorithmic computational process.

In this case, let me insist that the process is indeed algorithmic, but the logic and algorithm is apparent to only certain entities (or UTMs) that have had the opportunity to read in the relevant part of the input data. But to those who have not had the opportunity to access and read the relevant part of the input data, the process seems irrational.

If viewed from this perspective, phenomena related to the human psyche, even if they are not repeatable or reproducible under laboratory conditions, can be analyzed rationally and modeled computationally.

Is this not all old wine in brand new bottles ? Is this not as if you are trying to recreate the first flush of euphoria that adherents of Artificial Intelligence experienced in the early late 1960s when computers were first becoming fashionable in eclectic academic circles? Is it not like as if naïve computer scientists are trying to prove, once again, that it was merely a matter of using brute force – very powerful computers and a rock solid program – to demonstrate intelligence in machines. This dream had failed but was rejuvenated again in the 1980s as, less ambitious Expert Systems – computers systems that could address problems in one functional domain. But even these too have now gone out of fashion ….

These attempts failed because in each case, the search was on for that “perfect” algorithm or computer program that could mimic the behavior of a human being. It is said that this failure was because the mind is NOT algorithmic and hence any attempt to model it algorithmically is like trying to push a square peg into a round hole and expecting a perfect fit.

So why are we trying an algorithmic approach again ?

This apparent confusion can be cleared up if address two basic misconceptions namely :

· There is one “perfect” algorithm that if and when located – invented or discovered – will solve the problem of understanding and responding to the universe of data.
* There is a clear demarcation between the “universe” of data and the algorithm [ or program] that processes the data.

Yes, the basis of intelligence as well as consciousness is algorithmic, but no, there will be never be THAT one perfect algorithm. The algorithm that we use to represent mental phenomena is one that is continuously changing – mutating and evolving – as it senses, reads in and processes [“understands”] sensory and other data.


Hence the mental faculties of intelligence and consciousness are not inherent properties of the algorithm, but of the data that is processed by the algorithm. At best, the mind may be equated to the algorithm, but consciousness – or the “soul”, or rather the properties and behaviors associated with it – is a property that emerges from the pattern of data that is available, read in and processed successfully by the algorithm.[2] What is even more crucial is that the in this process, the algorithm itself gets changed significantly so that it is quite likely that the same data, if presented a second time to the same entity, may not get processed in an identical manner. Hence there is no question of passing the test of repeatability or any other test that is put forward by rational scientists.

So we say that mental phenomena are algorithmic or computational and hence deterministic, but they are deterministic to the extent of only one instance !! Since the second or any subsequent instance could and most probably would differ from the first or any earlier instance, we are erroneously led to believe that the process is non-deterministic and hence non-computational.

OK, I understand that this is neither Artificial Intelligence nor is it expert systems but tell me why are we at all trying to understand this whole business of UTMs ? We had begun with the statement of Vedanta that the world is an illusion, that is Maya .. when, where and why did this new animal called UTM enter our discussion.

I told you that we would be taking two major detours … and that is where we were.

Fine, the detours are over, so let us just go back to Maya and restart the discussion from that point.

Yes and I have tried to establish that this Maya, or illusoriness of the world that we apparently see around us, is not as impossible an idea as it seems to be. It is quite conceivable to envisage a scenario where the world is not what it seems to be.

But then you went off into this UTM business ? I thought that you would explain to me the mysteries of the Brahman and the Atman.

I will, I will, but before that I had to straighten out our ideas on how we, as sentient conscious entities, handle the process of understanding our environment.

Why is that so difficult ? If we can understand physics and chemistry and mathematics and economics and law and accountancy why is it that we need all this mumbo-jumbo to understand the Brahman and the Atman.

The difference my friend is because in all this cases there is a clear and sharp distinction between (a) the Knower, (b) the to-be-Known and (c) the process of knowing. There is a clear object – say Newton’s Laws of Physics, then there is a subject, the student, the learner who is trying to understand and finally there is a well defined process of learning which could include listening to a lecture, establishing a hypothesis and then conducting an experiment.

But is that not the same in this case ?

Not quite, because in this case, the knower, the to-be-known and the process of knowing is all bundled into the same thing. In fact there are people who claim that it is impossible to know … because they raise the very fundamental question .. How can the knower be known ?

OK. One step at a time, what is that we are trying to know ?

Singularity !

[1] Alan Turing, who created the theoretical basis of what is now called computer software, is often referred to as the father of computer science. A brilliant mathematician, he worked for the British government during the Second World War and broke the encryption technology of the German “Enigma” coding machine. Unfortunately his homosexual orientation caused him to fall foul of the law of the land and he committed suicide at a very young age to avoid further humiliation.

[2] Ya Devi Sarvabhuteshu Chetanetyabhidhiyate, Namastasyai Namastasyai Namastasyai Namoh Namaha – Salutations to the Devi who abides in all beings in the form of Consciousness or Cognition

1 comment:

Rui leprechaun said...

Yes! Yes!! Yes!!!

Singularity is the key... for the Divine ME!!! :)


One day you will be completely alone. So try to be completely alone now. Because now you can recognize the beauty that is there. - Prem Rawat