Showing posts with label Turing Machines. Show all posts
Showing posts with label Turing Machines. Show all posts

20 Apr 2009

Argument from Noise, 4. Three Arguments, 4.3 The Argument from Noise, in Schonbein, Cognition and the Power of Continuous Dynamical Systems


[Nick Bostrom & Anders Sandberg argue for digital computation instead of analog for simulating human cognition. They base their contention in part on the "argument from noise." The entries in this series summarize Schonbein's defense of that argument.]




Whit Schonbein

Cognition and the Power
of Continuous Dynamical Systems

4. Three Arguments against AANNs

4.3 The Argument from Noise



Previously we saw Fields argue that measurement in analog systems causes disruptions in operation. Schonbein disagreed. However, noise will cause this problem. (65c)

Neuronal information transmission involves an element of intrinsic noise. In fact, analog artificial neural networks (AANNs) can still function normally even without absolute precision.
If we conceive of the ideal case of inter-node communication in an AANN as involving infinite-precision weights, then successful communication in real-world contexts (i.e., despite noise) indicates that not all the precision provided by the posited real values is required for the system to function normally. This is because noise renders the lesser-significant bits useless (i.e., unreliable) for the purposes of carrying out the relevant computation, and therefore these bits can be ignored. (65d)
Hence analog noise limits its computational power.
If the presence of noise removes the utility of lesser-significant digits for carrying information, we should expect the computational power of systems that rely on those digits to be reduced in the presence of noise. Indeed, AANNs subjected to noise are reduced in computational power to finite automata, and often to a power less than that of finite automata. (65-66)
When subjected to typical noise, AANNs do not exhibit computational power greater than TMs, and will probably be reduced to levels below that of TMs. In short, AANNs only enjoy super-Turing-computability under ideal circumstances, and such circumstances are not what we find in actual cognitive systems. (66)

Schonbein addresses two possible responses to this attack on analog.

1) The Noise does not Matter

Say we want to reduce an AANN's computational power to the level of a Turing machine. To do so, we need to designate points along its operation. At these points the machine is in a certain determinate state at a determinate time. All the information in between we disrupt with noise. The Turing machine will be able to compute certain functions. The AANN will be able to compute no more than the Turing machine if the noise renders useless the variations between points.
However, noise is random. Therefore, we cannot determine a priori which bits will be ineffectual: At one time it may be at the nth bit. So (the response goes) we cannot segment the space of the network in such a way as to yield a set of discrete states, as required by computation, traditionally defined, since the boundaries of the desired state are constantly shifting. (66b)
[We cannot reduce AANNs to Turing machines, because there is no formula to determine how random noise can disqualify certain bits of information. Such a method might always inevitably make the AANN less computationally powerful than Turing machines, because the noise eliminates needed data.]

However, a system will not often use reliable information. So if noise makes some information unusable, it will not use it. So consider the method above when we disrupt the AANN system with noise at certain points. The argument above was that this will make the system less powerful than a Turing machine, rather than equal. For, the noise might disrupt vital information rather than inconsequential information. However, Schonbein's point is that if the information proves unreliable, the system will not use it anyway. So the system will not be any more disrupted. We could in fact render it equally powerful as the Turing machine using this method.


2) The Noise is Necessary

There is a second defense that AANN systems are super-Turing computable despite noise. We might argue that noise is a necessary part of cognition. In fact, perhaps the very reason we need analog is because it has noise.

The problem with this response is that it treats random noise interference and the relevant information as equally important. However, when we explain the relation between beliefs and desires, we need to maintain this distinction. Bob desires milk. He believes it is at the store. So Bob goes to the store and returns with milk. No part of his decision was decided by noise.

Thus this response « fails to honor a basic commitment of belief/desire psychology. » (67a) This field of study « explains behavior by showing how particular events fall under generalizations. » Consider Bob. He operates according to a relevant generalization : « anyone who desires something and believes it can be obtained at a certain location will take steps to reach that location, » with all things being equal. But if noise is necessary to how we make decisions, then we cannot articulate a standard generalization for what guides our decisions. We might as well just say, « if someone knows where to get what they want, only God knows what they will do about it. »

So we cannot argue that noise is irrelevant or necessary. But analog is only superior to digital when noise is either irrelevant or necessary. So there are no grounds to say that analog is superior to digital. (67c-d)


Schonbein, Whit. "Cognition and the Power of Continuous Dynamical Systems." Mind and Machines, Springer, (2005) 15: pp. 57-71.
More information at:


PDF might be available to you at:




Argument from Noise, 4. Three Arguments, 4.2 Argument from Measure, in Schonbein, Cognition and the Power of Continuous Dynamical Systems


by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Central Entry Directory]
[Computation Entry Directory]
[
Schonbein's Cognition and the Power of Continuous Dynamical Systems, Entry Directory][Nick Bostrom & Anders Sandberg argue for digital computation instead of analog for simulating human cognition. They base their contention in part on the "argument from noise." The entries in this series summarize Schonbein's defense of that argument.]




Whit Schonbein

Cognition and the Power
of Continuous Dynamical Systems

4. Three Arguments against AANNs

4.2 The Argument from Measure


Fields argues that it does not matter if analog systems are more precise. On account of certain physical limitations, our model can only correspond one-to-one with the system in a digital fashion. Schonbein formulates the argument thus:

1. If a virtual machine M (e.g. a Turing machine) is to be realized in a physical system S, it must be possible to put states of M into correspondence with states of S. [We have a modeled design for a pipe-joint that doubles the amount of incoming water.]
2. In order to construct this mapping, the states of S must be measured. [Our pipe-joint needs to measure incoming water-volume in order to know what amount to add to it.]
3. Measuring a state of S involves adding energy to the system. [We will have to use an electrical device to measure the incoming water amounts.]
4. The more precise our measurements are – the « smaller » the state being measured is – the more probable it is that our measurements will influence the behavior of the system. Thus measuring a state will result in S not making the transition to the state it would have entered had it not been perturbed. [If we have to measure the water to absolute precision, that will take a computer an enormous amount of time, maybe even infinite time. So such an analog measurement will hinder the operation of the pipe-fixture.]
5. Therefore, there is an upper bound on the precision we can achieve in measuring the states of S. [Our device can only be so precise without disrupting its own operation.]
6. Therefore, the only correspondences that can be constructed are those that possess a finite number of states. [Our model or design for the pipe-fixture will potentially be able to handle infinitely many variations in water volume. However, we will only be able to correlate these infinite possibilities to a finite number of possible states in our physical device.]
7. Therefore, a Turing machine (TM) can compute any machine realized by S. [Thus, some digital pipe device of sufficient computational/measuring ability can be just as precise as an analog one, even if our design/model itself can theoretically deal with continuous variables.]

According to Fields, so long as we accept premises 3 and 4, « a continuous dynamical system cannot, even in principle, exhibit behavior that cannot be simulated by a universal Turing machine. » (65a)

Schonbein finds two problems with Fields' argument.

1) We cannot follow Fields to his conclusion that a TM machine can compute anything that a continuous system can compute. For, we know already that analog artificial neural networks (AANNs) are super-Turing-computable. They can compute functions that Turing machines cannot.

2) We should not think that our inability to measure the computed variations poses any limit on the machine's ability to compute them. [Two rivers merge. The juncture adds the volumes of both tributaries. We cannot measure the inputs and outputs exactly. But that does not stop the juncture from combining every smallest bit from both.]
it is fallacious to infer from our lack of ability to measure the states of a system to the conclusion that those unmeasured (or unmeasurable) states are not relevant to the behavior of the system – to do so is to confuse our metaphysics with our epistemology. (65b)
We are not interested so much in measuring the systems. We firstly want just to model it.


Schonbein, Whit. "Cognition and the Power of Continuous Dynamical Systems." Mind and Machines, Springer, (2005) 15: pp. 57-71.
More information at:


PDF might be available to you at:



19 Apr 2009

Argument from Noise, 3. Beyond Traditional Computation, in Schonbein, "Cognition and the Power of Continuous Dynamical Systems"

by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Central Entry Directory]
[Computation Entry Directory]
[
Schonbein's Cognition and the Power
of Continuous Dynamical Systems, Entry Directory]


[Nick Bostrom & Anders Sandberg argue for digital computation instead of analog for simulating human cognition. They base their contention in part on the "argument from noise." The entries in this series summarize Schonbein's defense of that argument.]




Whit Schonbein

Cognition and the Power
of Continuous Dynamical Systems

3. Beyond Traditional Computation


Jerry Fodor is an example of a classicist who argues that Turing machines suffice to model cognition. Others, for example, Van Gelder, contest that we need a more computationally powerful model for human cognition. For, cognitive behavior might be "much more subtle and complex than the standard concept of representation [and therefore computation] can handle." (qt. 60b)

Horgan explains that the alternative dynamical systems approach "'involves a potentially more powerful kind of mathematics' that can deal with a cognition system that realizes 'a function so complex and subtle that it is not tractably computable.'" (qt60bc)

It is not entirely clear what "more powerful" means in these claims. We could use Schonbein's "computational hierarchy." We list which computers are capable of computing which functions. The more powerful ones are those that can compute more functions than the others. This is probably because they have greater resources to do so.

Those who argue for non-classical models also advocate continuous rather than discrete values for defining cognitive models. Van Gelder, for example, notes that "differential equations utilize continuous values." (60c) And Horgan explains that "the mathematics of dynamical systems is fundamentally continuous mathematics rather than discrete mathematics." (60c)

Turing required that computational states be discrete. But the values in continuous systems make use of "infinitely precise values" that can "differ by an arbitrarily small degree." Hence analog systems differ fundamentally from traditional digital automata. (60d)

Continuous systems, then, are "non-computational" in the sense that they can compute functions that are not Turing-computable. Furthermore, Horgan believes that "suitably modified neural networks are the sorts of things that could realize such 'non-computational' systems." (60d)
He writes,
dynamical systems whose transitions are computable are actually a relative rarity, and it is certainly possible for noncomputable dynamical systems to be subserved by neural networks at least if the networks are made more analog in nature by letting the nodes take on a continuous range of activation values, and/or letting them update themselves instantaneously rather than by discrete time steps. (qt61a, emphasis mine)
In fact, it has already been shown that analog artificial neural networks (AANNs) are more computationally powerful than Turing machines. They are super-Turing-computable.
these networks are relatively simple: They are first-order, recurrent, and synchronously updated; they use saturated-linear activation functions; and have a finite number of nodes. (61b)
If such a system used just numerical quantities that were rational numbers (and hence are specifiable as ratios between integers), then they would be Turing equivalent. "However, if one allows for continuous weights and activations, AANNs are capable of computing functions not computable by TMs" (61c)

Dynamicists claim that we need computational models more powerful than Turing machines in order to model cognition. "Part of this claim revolves around the use of formalizations that make use of continuous values, which implies that these systems cannot be understood in terms of classical computation." (61c) Because certain neural networks can handle continuous variables, it is "at least logically possible" to produce super-Turing-equivalent systems.

However, a number of arguments have been offered to the conclusion that AANNs (and other continuously valued automata) are nomologically impossible, i.e., not realizable by physical systems in our world. (61d)
Schonbein will now examine three such arguments.


Schonbein, Whit. "Cognition and the Power of Continuous Dynamical Systems." Mind and Machines, Springer, (2005) 15: pp. 57-71.
More information at:


PDF might be available to you at:


14 Apr 2009

Argument from Noise, 2 The Power of Computation, in Schonbein, "Cognition and the Power of Continuous Dynamical Systems"


[Nick Bostrom & Anders Sandberg argue for digital computation instead of analog for simulating human cognition. They base their contention in part on the "argument from noise." The entries in this series summarize Schonbein's defense of that argument.]





Whit Schonbein

Cognition and the Power
of Continuous Dynamical Systems

2. The Power of Computation


Our current understanding of computation begins with Turing's introduction of the Turing Machine (TM) in 1936.

A Turing Machine contains these components:
1) a controller,
2) a tape head, and
3) a tape of unbounded length.

The controller is found to be in different states at different stages of the computation. The number of states is finite. We will call them q0 - qn.

We divide the tape into discrete squares. In any square may be found a symbol. The set of symbols we call the 'alphabet.' At any given moment, we find the tape head positioned over one of the squares. [Turing images are from Marvin Minsky's Computation: Finite and Infinite Machines]



The machines proceeds through a series of discrete motions. Each time, the tape-head writes a symbol on the tape, and moves to the left or right. There are different formats for describing the machines behavior. These would be ways to display the machine's program or instructions. They take the form of hypotheticals. For example, they might say, "If you are in state q1, and you read a w1 on the tape, then write a w2 over it, move to the left, and change to state q2." One formalized way to render such an instruction is the quintuple: {q1, w1 → w2, R, q2}
All the rules can be given in one "transition table."



[Considering seeing this entry for Boolos & Jefferey's explanation and rendition of other display formats, and this entry where we carry-out an interesting Turing computation of the natural numbers.]

A TM computes the value of a function by beginning with some input finitely represented on the tape, and then running according to the deterministic procedure described by the transition table. The output of the calculation is the string remaining on the tape when the machine halts. (59b)

We must note one important feature that both Turing Machines and all other computational systems share. Their set of symbols and operations are always finite. Hence these systems are finitely specifiable: "any given TM can be fully described in a finite amount of space and time." (59bc). Now, if instead the machine's states and symbols admitted of a continuum of variation, then they would not be finitely specifiable; for, the possible states and symbols would be infinitely many.

Turing Machines are illustrations for the basic workings of all computational automata. They all share the basic features of finite specifiability and discreteness. However, most other computational systems are more complex. Each different kind of system can compute its own class of functions. Certain functions require machines with more resources. By ranking the functions according to the computational resources needed to compute them, we may determine a hierarchy of functions. This ordered list would also indicate the hierarchy of computing power of the machines capable of computing them. Turing Machines are more computationally powerful than most other sorts of systems. So if another system is as powerful as a Turing Machine, we will call it "Turing-equivalent." And if the system can compute functions that even a Turing Machine cannot compute, then we will call it "super-Turing-equivalent." (59-60)


Schonbein, Whit. "Cognition and the Power of Continuous Dynamical Systems." Mind and Machines, Springer, (2005) 15: pp. 57-71.



31 Mar 2009

Turing Computation of the Natural Numbers


by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Central Entry Directory]
[Computation Entry Directory]


Turing Computation
of the Natural Numbers


We will now build from our previous post on Turing machines. What we want is a mechanical computation of the natural numbers.

[I obtain the following program from Peter Bradley's wonderful animated site on Turing Machines.]

Our abstract machine will compute the natural numbers and display them in binary. So it is a "binary counter" machine.

This is its program, displayed as a "machine table." The S represents the number that the machine is reading. The subscript '0' means it would be a zero, and the subscript '1' means it is a one.



The q's stand for the two different instructions. L means to move left. R means to move right. There are two boxes for each q instruction, because the machine will see either of two symbols (1 or 0), and according to which one, it will perform some distinct task. We could articulate the instructions this way.

q1) If the scanned symbol is zero, write a zero overtop of it, move to the left, and begin instruction q1. If the scanned symbol is one, write a one overtop of it, move to the right, and begin instruction q2.
q2) If the scanned symbol is zero, write a one instead, move to the left, and begin instruction q1. If the scanned symbol is one, write a zero instead, move to the right, and begin instruction q2.


We will follow it through all the steps leading to its count of four.

It begins on a zero.



All the other boxes are zero except for one. At two spaces to the left of the starting point, there is a '1'. We do not read this with the number. Its function is to 'bump' the machine back to the right so it may continue its adding. All the boxes to the right of the bumper are the binary digit places that display each new counted number as it is added. However, this display shows them inversely. Hence we need to think of the ascending digit places moving to the right. So normally 100 equals four in binary. But here it would be displayed as 001.

So the machine finds itself at the second zero. We place a yellow arrow wherever the machine is found at the start of the given instruction. It always moves at the end of the instruction. We display its direction with black arrows.


We begin at the first instruction q1. Because the machine starts at a zero, we look to S0. It tells the machine to write a zero, and to move to the left. There is already a zero there, so nothing changes.


Likewise for the next step. Instruction q1 repeats.



But now the machine stands above a '1'.
It writes a '1' again, then it moves to right and begins instruction q2.



At this box there is a zero. So the machine replaces it with a '1', moves the left, and begins instruction q2. At this point, we have our first counted value: 1


The number it scans next is a '1', so it writes a '1' over it, moves to the right, and begins instruction q2.



Here the machine finds a '1'. So it replaces it with a zero, moves to the right to begin q2. But notice the similarity to when we clear the binary abacus.



At the next place it finds a zero. Instruction q2 tells it then to write a '1' instead and move to the left. This is equivalent to the carry procedure on the binary abacus.

So we see our first instance of clear and carry performed by the Turing Computer.


It now sees a zero. Instruction q1 tells it to write another zero, move to the left, and begin instruction q1.



It arrives upon the bumper. Instruction q1 tells it to write another '1' over it, move to the right, and begin instruction q2.



Now it sees a zero in the units place of our number display. Instruction q2 tells it to write a '1', move to the left, then begin instruction q1. In this way, we have added another number to get three.



It hits the bumper again, so it goes to the right and begins instruction q2.



Now it sees a '1' in the units place. Instruction q2 tells it to write a '0' instead, move to the right, and begin instruction q2. Here again is a clear procedure.



It sees another '1' in the next digit place. Instruction q2 tells it to write a zero, move to the right, and begin instruction q2. This is the second part of the clear/carry procedure.


Now it sees a '0'. Instruction q2 tells it to replace the '0' with a one, move the left, and begin instruction q1. This is the carry procedure that gets us to four. Now, the machine repeats the same clear/carry process as it had before.

Given an infinite amount of time, it will display the infinity of natural numbers.



See Peter Bradley's site on Turing Machines

Programing Abstract Machines: Turing Machines in Boolos & Jeffrey's Computability and Logic

by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Central Entry Directory]
[Computation Entry Directory]


Turing Machines

Introduced by Boolos and Jeffrey


Our abstract machine is a man in a box. His cube travels along a railroad track.



The rail ties mark discrete squares along the track. The car may move along the track in either direction. We have rail workers on either end, always ready to add more track and ties as the box nears the edges.

Almost all the rail-ties have nothing but white ballast stones placed between them. But showing in a select few squares is one symbol from a finite set. They are configured using black ballast stones arranged against the background of the usual white ones.

The symbols in the square can be anything. And we will refer to them abstractly using variables, so to allow for every possibility. Hence we consider the finite number of symbols that may be found or placed in the squares S1, S2, ... Sn. The empty squares we will call S0. In our more concrete example, S0 will be a '0' in the square, and S1 will be a '1'.

The box's bottom is missing. So the man inside can read the symbols in each square. And he can change them or add a symbol to a blank square. The "poor mug" inside may also push or pull the box one place to the right or left. [below is a modification of the Boolos and Jefferey diagram. Image credits below.]


So the man performs his three actions: reading, writing, and moving. He does so according to a list of instructions. Any one instruction on the list has its own number i. He will be in a certain state at each stage of the computation process. What determines the state is the particular instruction he is performing. The total number of instructions is m. So we call the internal states q1, q2, ..., qm.
"He is in state qi when he is carrying out instruction number i."

Each instruction is formulated as a conditional. So it tells him what to do, depending on whether the symbol he reads is S0 or S1 or .... or Sn.

There are n + 4 things the boxed computer man can do. He can
1) Halt the computation.
2) Move one square to the right.
3) Move one square to the left.
4) Write S0 in place of whatever is in the scanned square.
5) Write S1 in place of whatever is in the scanned square.
.
.
.
n + 4) Write Sn in place of whatever is in the scanned square.

The instruction he carries-out is the state he is in. Depending on what that is, and on what symbol he is scanning, the man will perform one or some other of these n + 4 overt actions. And unless he is halted, he will also perform covert acts "in the privacy of his box." Namely, he will determine what will be the next instruction (the next state). "Thus, the present state and the presently scanned symbol determine what overt act is to be performed, and what the next state is to be." (22b)

There are a number of ways that we may specify the overall program of instructions the man is to follow. For example, we might use a machine table, a flow graph, or a set of quadruples. These three types of descriptions are illustrated below. This is how they appeared for a machine that writes three symbols S1 on a blank rail track, and then halts, scanning the leftmost of the three.



We will now look more closely at this example.

The man begins above an empty square (which we depict with a '0'). His instructions are, "if the square is empty, write symbol S1. And if there is a number S1 in the square, move one square to the left. Halt after writing three S1's"

More explicitly, when following instruction q1, the man is to
1) If the scanned symbol is S0, write an S1 in the initial square and repeat instruction q1. But
2) If the scanned symbol is S1, move left and following instruction q2 next.

So we will represent the instructions according to the three methods.

The computer box begins above a zero.



His initial part of his first instruction is a conditional. If it is '0', make it '1.' Then repeat instruction q1.

First the machine sees a zero. So it enters a '1'. Then it returns to the beginning of this instruction.


This first conditional of the initial instruction is displayed these ways for the different formats. In the machine table, we begin with q1. If it sees symbol So, he is to write an S1. The table displays the 'q1' in S1q1 to indicate that we go back to the beginning of the instruction.


In the flow chart, the circular arrow indicates the return to the same instruction.



And in the quadruples, the repeated q1 indicates the return to the instruction's beginning.



So the computer box returns to the beginning of q1. At the beginning, it says that if it reads S0, to write S1. But it does not read S0. The next part of the instruction says that if the symbol is S1, then move to the left and begin instruction q2. Thus our machine moves left.



We use an L to indicate the move-left operation in our three ways to show the program.







Instruction q2 is the same as q1, only one recurrence further in the process. Our computer sees a zero, so it enters a 1 and returns to the beginning of q2.



And the notations follow as before.







Now that it sees the 1 it has written, it moves left to begin q3.








It now sees a zero, so it writes a 1. But the instructions end here. Each of our displays of the program cease giving the man more tasks to perform.











Boolos, George, and Richard Jeffrey. Computability and Logic. Cambridge: Cambridge University Press, 1989.


Modified train track image from: