The Abstract Machines of Computation Theory. Marvin Minsky's Computation, Introduction and Finite-State Machines

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

[Central Entry Directory]
[Computation Entry Directory]

Marvin Minsky

Computation:

Finite and Infinite Machines

Chapter 1 Physical and Abstract Machines

1.2 Machines as Physical Models of Abstract Processes

Someone describes a machine to us. We are not initially interested in how it is constructed. We first want to know how the machine works in principle. How does it work?

The idea of a machine usually centers around a some abstract model or process. (5c)

Consider a theory in physics. Perhaps material circumstances do not support the theory. In that case we criticize the theory, not the material world. However, imagine we design and build a machine. Soon it breaks down. So we fix it. Unlike in physics, we do not criticize the theory. Instead we find fault with the system's material parts. (5-6)

[In other words, we are designing, building, testing and evaluating abstract machines for computational tasks.]

Part I Finite State Machines

Chapter II Finite-State Machines

2.0 Introduction

We may also call finite state machines, 'finite automata.' The operations of these 'highly idealized' machines "proceed in clearly separate 'discrete' steps from one to another of a finite number of configurations or states. (11b)

Because they are finite, we may completely describe their structure and behavior without any ambiguity or approximation.

It is much harder to deal with more realistic models of mechanical systems, in which variable quantities like time, position, momentum, friction, etc., vary smoothly over continuous, imperceptibly changing ranges of values. (11c)

[These would be the natural machines that compute analogically. We later will discuss as examples Pythagoras' monochord and golden ratio.]

Nonetheless, our digital systems are still quite powerful, and in many ways they can approximate anything that an analog physical system can accomplish. [We later address also the issue of approximation in terms of the analog/digital argument from "noise."]

2.0.1 Moments of Time

The finite machine's operations occur throughout a linear sequence of discrete time moments, "between which nothing happens." (12c)

One may imagine these moments as occurring regularly like the ticking of a clock, and we identify the moments with integers -- the variable for time, t, takes on only the values 0, 1, 2, . .

(12d)

2.1 States and Signals

From the point of view of its user or environment, the machine may be regarded as a "closed box with input and output channels." Every now and then, the user acts upon the machine through the input channels. And at other times the machine acts upon the user through the output channels. Unless we want to know how things work on the inside of the box, we do not need to know what takes place inside it. Hence we call it a "black box."

We are concerned with the set of distinguishable states that characterize a channel at any given moment. Each time-point is discrete. One of a finite number of possible states or conditions corresponds to each discrete moment in time.

We might symbolize the state using alphabet letters, numbers, or such words as "yes" and "no." In our examples, we consider our electric switch to be in either an "on" or an "off" position. So our finite state machine theory is not concerned with continuous or analog devices "which can be set to transmit any of an infinite set of fractions of a signal."

We want to know how our machine behaves. So we need to determine how its outputs depend on its inputs. Then we could know the output for some certain specified time.

One restriction we will introduce here is this -- the output state at the moment t doesnot depend on the input state at that same time t. This is to say, that we won't admit the possibility of signals traversing a unit instantaneously. But the output at timet + 1 will usually depend, at least in part, on the input signal at the previous momentt. This restriction reflects the physical impossibility of instantaneous transmission from one place to another. It is necessary here for a simpler reason: to prevent unrealizable -- paradoxical -- descriptions of situations when channels are interconnected, and to prevent infinitely fast behavior -- also physically unrealizable. (14 c.d, my emphasis on instantaneous)

[Soon we will examine natural computers and the way they instantaneously calculate infinite computations.]

Minsky, Marvin. Computation: Finite and Infinite Machines. London: Prentice-Hall International, Inc., 1972.