Search Results for: Halting

It’s a rare thing to find a clear and simple explanation for something complicated – something like the Pythagorean Theorem or calculus or whatnot.  It’s even rarer to find a clear and simple explanation for something that challenges the very pillars of logic – something like Gödel’s Theorem or the halting theorem.  But J. Glenn Brookshear treats readers of his text Computer Science: An Overview to a remarkably clear exploration of the halting theorem in just a scant 3 pages in Chapter 12. I found this explanation so easy to digest that I thought I would devote a post to it, expanding on it in certain spots and putting my own spin on it.

Now to manage some expectations:  it is important to note that this proof is not rigorous; many technical details needed to precisely define terms are swept under the rug; but neither is it incorrect.  It is logically sound if a bit on the heuristic side.

The halting theorem is important in computer science and logic because it proves that it is impossible to construct an algorithm that is able to analyze an arbitrary computer program and all its possible inputs and determine if the program will run to a successful completion (i.e. halt) or will run forever, being unable to reach a solution.  The implications of this theorem are profound since its proof demonstrates that some functions are not computable and I’ve discussed some of these notions in previous posts.  This will be the first time I’ve set down a general notion of its proof.

The basic elements of the proof are a universal programing language, which Brookshear calls Bare Bones, and the basic idea of self-referential analysis.

The Bare Bones language is a sort of universal pseudocode to express those computable functions that run on a Turing Machine (called Turing-computable functions).  The language, which is very simple, has three assignment commands:

• Clear a variable
• Increment a variable
• Decrement a variable

In addition, there is one looping construct based on the while loop that looks like

while x not 0 do;
   ...
end;

While primitive, these commands make it possible to produce any type of higher level function.  For  example, Brookshear provides an algorithm for computing the product of two positive integers:

Note: for simplicity only positive integers will be discussed – but the results generalize to any type of computer word (float, sign int, etc.).

Now Bare Bones is a universal language in the sense that researchers have demonstrated that all Turing-computable functions can be expressed as Bare Bones algorithms similar to the Multiply function shown above.  Assuming the Church-Turing thesis, which states that the set of all computable functions is the same as the set of all Turing-computable functions, allows one to conclude that Bare Bones is sufficiently rich to encode all algorithms that express computable functions.

One particularly important Bare Bones algorithm is something I call x-test (since Brookshear doesn’t give it a name).

The job of x-test is simple: it either terminates when x is identically zero or it runs forever otherwise.

The Terminate flag is assigned a value of 0 if x-test fails to halt and 1 if it does.

The next step brings in the concept of self-reference.  The function x-test takes an arbitrary integer in and gives the binary output or 0 or 1.  Since x-test is expressed as a set of characters in Bare Bones and since each character can be associated with an integer, the entire expression of x-test can be associated with an integer.  To be concrete, the string representation of x-test is:

‘while x not 0 do;\n    increment x;\nend;’

A simple python program, called string_to_int:

def string_to_int(s):
    ord3 = lambda x : '%.3d' % ord(x)
    return int(''.join(map(ord3, s)))

transforms this string to the (very long) integer

119104105108101032120032110111116032048032100111059010032032032032105110099114101109101110116032120059010101110100059

Using this integer in x-test results in the Terminate flag equal 0.

Of course, any expression of x-test in any programming language will result in a nonzero integer and so x-test never has a chance to terminate.

But there are clearly functions that do terminate when they are expressed as input for their own execution (one obvious example is the duel function to x-test where the while loop stops if x is non-zero).  Such functions are said to be self-terminating.

Although it may look like a lot of effort for nothing, this notion of self-terminating functions is the key to the halting theorem and all that remains is to combine the above results with some clever thinking.

The clever thinking starts with the assumption that there exists a function, which I call the Hypothetical Halting Program (HHP), that can analyze any arbitrary program written in Bare Bones along with any corresponding input and determine which combinations will terminate (decidable) and which will not (undecidable).

Again, to be concrete, let’s look at what the HHP would do when looking to see if x-test is self-terminating.

The HHP would be given the x-test function and the corresponding input (x-test in integer form) and would determine, just as we did above, that x-test won’t terminate – that is, x-test is not self-terminating.

Now such a function that works only on x-test is easy to understand; the text above that argued against x-test being self-terminating is one such instantiation.  However, the goal is to have the HHP be abale to analyze all such algorithms so that we don’t have to think.  Already, warning bells should be going off, since the word ‘all’ is a pretty big set, in fact infinite, and infinite sets have a habit of behaving badly.

But let’s set aside that concern for the moment and just continue our assumption that HHP can do the job.  As we progress, we’ll see that our assumption of the existence of the HHP will lead to a contradiction that rules out this assumption and, thus, gives the desired proof.  Operating without this foresight, we argue that since the HHP is computable it must be able to find expression as a Bare Bones program.  And since the HHP analyzes Bare Bones programs, it must be able to analyze itself and determine if it is self-terminating – spitting out a 1 if so and a 0 otherwise.

Now we can construct a new program, called the HHP++, that is the sequential running of the HHP followed by x-test.

We can always do this in Bare Bones by first running HHP and then assigning its output (0 or 1) to the input of x-test.  And here is where it gets interesting.

Take the HHP++ and let it test itself to see if it is self-terminating.  If it is self-terminating, the HHP piece will confirm it so and will output a value of 1.  This value is then passed to the x-test piece which then falls to halt.  If the HHP++ is not self-terminating, the HHP piece will output a 0 which, when passed to the x-test piece, halts the operation.  Thus the HHP++ is a program that is neither self-terminating nor not self-terminating and so the only way that can be true is that our original assumption that the HHP exists is false.

It is remarkable that using such a simple argument, the human mind is able to rule out the possibility of general function like the HHP.

In keeping with the New Years Theme, this month’s column lists the five most important accomplishments from the world of logic, mathematics, computing, or philosophy in the last 100 years.  This idea is an offshoot of the books Five Golden Rules: Great Theories of 20^th Century Mathematics – and Why They Matter

and Five More Golden Rules: Knots, Codes, Chaos and Other Great Theories of 20^th Century Mathematics,

both written by John Casti.  In these works, Casti devotes a chapter to each of the following:

1. Minimax Theorem (Game Theory)
2. Brouwer Fixed-Point Theorem (Topology)
3. Morse’s Theorem (Singularity Theory)
4. Halting Theorem (Theory of Computation)
5. Simplex Method (Optimization Theory)
6. Alexander Knot Polynomial (Knot Theory)
7. Hopf Bifurcation (Dynamical System Theory)
8. Kalman Filter (Control Theory)
9. Hahn-Banach Theorem (Functional Analysis)
10. Shannon Coding Theorem (Information Theory)

with items 1-5 being from the first book and 6-10 from the second.

The idea of ranking my own top 5 had been pinballing around the back of my mind since I first encountered these books in 2015 and when the opportunity presented itself for this month’s theme, I thought I would seize it and run.  But it is important to be aware that the list I’ve compiled here is my own, inspired by Casti’s work, but independent in both content and analysis.  In fact, I think Casti misses the two most important contributions even with a list of 10 – but that is a matter of judgement and taste.

So, without any more preamble, let’s get to the list.

5. Kalman Filter

It is hard to overemphasize the Kalman filter’s importance to real time computing.  The algorithm allows for fitting and estimation to be performed, in the presence of noise and uncertainty, during the course of process, such as the motion of a robotic arm or the flight of a spacecraft.  The filter takes in measured points as they become available and ‘re-fits’ the new point in the context of all previous points thereby giving an improved estimate of the state of the system.  The key point is that the system directly takes into account both the uncertainty in the measurements as well as the short-comings of any physical model of the motion.  The introduction of the Kalman Filter gave rise to a whole industry of algorithm development (extended Kalman Filters, unscented filters, Bayesian networks, etc.) that balance model-based prediction (e.g. Newton’s laws) with uncertainty in knowledge and measurement – the essential ingredient for computation in the real world.  Final note:  Casti also recognizes the Kalman filter.

4. Optimization Techniques

This entry is a catch-all for a variety of algorithms and approaches that have been stirred into action with the advent of the computer.  While not particularly glamourous, optimization methods solve a host of real world problems associated with getting the best; as long as best can be mathematically encoded in something called an objective function.  There are two basic families of optimization algorithms:  indirect and direct.  In the indirect method, additional equations, typically called adjoint equations, are added to the problem to be solved and the response of the new variables in these equations indicates when controls should be applied and how.  In the direct methods, a set of controls are assumed at the onset and their values are adjusted to achieve optimality.  Optimization techniques find application in thousands of practical problems including trajectory optimization, operations research, and economic modeling.  Final note: Casti singles out the simplex method for special recognition.  While this method is of particular importance in both the history of optimization and the particular application to economics, its limitation to linear problems is a significant liability, hence the larger scope of this entry.

3. Shannon’s Mathematical Model of Information

In 1948, Claude Shannon published A Mathematical Theory of Communication in The Bell System Technical Journal.  This paper, considered a landmark, set the stage for the modern digital age and for the advances in the field of telecommunications (wired and wireless).  Building on the ideas of Nyquist and Hartley, Shannon essentially created the field of information theory and the digital signal processing that follows in its train.  His theory defined the notion of information (a bit), sets the theoretical limits on the amount of information that can be transfers, adapted the idea of entropy to communications, and provided a set of theorems that defined what could and could not be done in a communications system.  Final note: Casti recognizes the importance of Shannon’s work in his second book and increased my own recognition of the importance of Shannon’s work.

2. Fast-Fourier Transform

Deemed as one of the most important numerical algorithms ever created, the fast fourier transform or FFT is the workhorse of the modern digital age.  There are so many applications that it is hard to even list a fraction of them but some of the most important ones are:  1) signal processing in telecommunications, 2) image construction in medical imaging, and 3) spectrum analysis of scientific data ranging from the mechanics of materials to response of electrical components to quantum mechanics.  An FFT system resides in virtually every home in the US in the high definition televisions, cellphones, videogame systems, and so on.  Final note:  Casti has no mention that I’ve found of the FFT.

1. Gödel’s Theorem

Rounding out the top of this list is the far-reaching analysis on the limit of logic (mathematical and otherwise) that Kurt Godel provided the world in 1931.  This theorem, along with the closely related theorems due to Tarski (undefinability theorem), Church (undecidability) , and Turing (halting theorem) states that formal logic must be either incomplete or inconsistent.  All of these related theorems deal with how logic views or expresses statements about itself and have profound implications on human thought, philosophy, and artificial intelligence.  I also interpret them as saying something essential about man as a rational animal and, therefore, about the human condition as I’ve written in earlier posts (Gödel’s Theorem – General Notions, Turing, Godel, and the Universe, Logic and Limits, Bare Bones Halting, and Self-Reference and Paradoxes).  The full content of these results will no doubt be explored for years to come.  Final note:  Casti focuses more on the halting theorem and its implications for computing.

One can’t really be alive, work with computers, writing algorithms to solve hard problems, and be ignorant of the importance of a good algorithm.  Most texts on scientific programming, which formed the bulk of what I read in my formative technical years, possess at least on cautionary tale about how slow a computation can be if the algorithm is bad.

One classic tale I like, which is often trotted out with gusto, is the calculation of the Fibonacci numbers.  As a reminder, the nth Fibonacci number is the sum of the two previous ones

\[  F_n = F_{n-1} + F_{n-2} \; . \]

So to compute $F_{100}$, one need to compute $F_{99}$ and $F_{98}$, each of which need the two below them.  Computing naively causes a lot of repetition since one computes $F_{98}$ and $F_{97}$ to compute $F_{99}$ and $F_{97}$ and $F_{96}$ for $F_{98}$ and so on.  Of course, a fast algorithm exists which essentially involves recording these values once computed, thus ensuring that they are computed only once in the recursion.

While compelling, this cautionary tale is a bit of a cheat.  Someone actually knows the best algorithm and it happens to be quite fast and, generally speaking, it isn’t all that interesting to compute the Fibonacci numbers oneself, since they are immutable.

Much more interesting are the situations that are dynamic.  Finding the best route to visit an arbitrary list of cities is the stuff of legends with which the famous Traveling Salesman Problem (TSP) wrestles.  This problem is often listed as hard, or rather NP-Complete, a class of algorithms that belongs to the larger class of NP-Hard problems.

Roughly speaking, NP problems (or which NP-Complete and NP-Hard belong) are computational problems that do not possess known algorithms that can find solutions in polynomial time.  What that means is that as the input data set, usually thought of as consisting of $N$ entries, is increased (i.e. $N$ grows) the computing time required to find a solution grows much fasters than any polynomial in $N$.  Usually the growth is exponential, although worse cases, such as combinatorial growth, also occur.  This is in sharp contrast with the P class of computational problems that do possess known algorithms that can find solutions in polynomial time.

The curious thing about NP problems are that while they are not quickly solvable, they are quickly checkable.  This phrasing means that while it takes a long time to find a solution for a large input data set, once the solution has been found it can be verified in a relative short period of time that scales as a polynomial in $N$.

This distinction is hard to understand and this difficulty is compounded by the fact that the NP class has three qualifiers making for NP, NP-Complete, and NP-Hard as well as containing the P class.  In addition, problems like the TSP are very specialized and complex making them very hard to relate to in general

Note: The reason NP-Hard lies partially outside the NP boundary is because some NP-Hard may not even be decidable. Undecidable problems possess no definitive answer to the computing question with which they are posed.  That such problems exist inescapably follows from Turing’s analysis of the halting problem.

So I searched for a simplified problem that I could sink my teeth into.  A problem that would be tractable enough to play with but still demonstrated the ‘NP-ness’ in a way that I could relate.  After some trial-and-error, it seems that Subset Sum Problem (SSP) fits the bill.

The SSP asks the following question.  Given a sum $S$ and a set of integers $Q$ is there a proper subset of $Q$ that sums to $S$.   It is provable that the SSP is NP-Complete:  a solution exists (i.e. the problem is decidable) ; it is hard to find a solution, especially when $Q$ has a lot of elements; and it is easy to check the solution once the answer is revealed.

That the SSP is decidable is actually trivial to see.  Given a subset $P \in Q$ of integers, it is easy to sum them together and to test whether the result equals $S$.  By playing with a simple configuration for $Q$, it was easy to demonstrate that it is hard to just find a subset that sums to the desired value and that is equal easy to check once an answer is proffered.

Consider the following $3 \times 4$ block of integers between 1-9, inclusive.

The sum of all of them is 53 and the smallest number in the set is 1, so it is also easy to answer no to the SSP when $S$ is outside this range.  But what about the rest of the values?  Can any value between 1 and 53 be represented?  (It should be clear that 1 is represented trivially by one of the 1s in Q and that 53 is represented by the whole set).

For a test, can we find a subset that sums to 19?  That answer is obvious if one stares at the grid for a while.  Since there is a 9 in the grid, all one needs to find is two numbers that sum to 10 in order to demonstrate that 19 is a valid subset sum.  One such possibility is

How should we go about answering the general question?  This is where the NP part comes in.  In general, the best algorithms known are not polynomial in complexity.  I won’t try to prove this; I am simply stating the conclusion of the computer science community.   But being NP, it is easy to check that a proposed solution is valid in polynomial time.  For example, it may not be obvious that 47 is contained as a subset sum within the grid but the following shows it to be true

Each of the blocks of different shades of red sum to 10 (i.e.: 6 + 4; 9 + 1; 8 + 2; 5 + 4 + 1) and the light orange block is a 7. Checking that solution is easier than finding it in the first place or in finding an alternative (note that one trivial change can be done in 3 cell to get a different set that subset sums to 47 – hint – look at the blocks that remained white).

Now back to the general question as to whether any sum can be constructed.  Consider the grid now colored so that the red subsets sum to 30 and the white portion of the grid consists of the numbers 1, 2, 3, 4, 5, and 8.

Since the numbers 1, 2, 3, and 4 can sum to every number on the range 1-10, we already have that all numbers from 1 to 40 are subset sums.  For example, 27 can be formed from the two pairs of tens (say 1 + 9 & 7 + 3) and from 3 + 4.  Finally since 8 + 2 = 10 and 8 + 3 = 11, the remaining sums from 41 through 52 are also achievable.  Thus we have proved that all values between 1 and 53 are achievable.

Note that the time it takes to confirm any of these values is much shorter than the time it would take an algorithm to find these solutions.  That is what it means to be NP-Complete.

As I mentioned in last week’s blog, I was encouraged by Casti’s chapter on the Halting Theorem and questions of undecidability in logic and computing.  In fact, I was inspired enough that I resolved have another go at studying Gödel’s theorem.

To give some background, many years ago I came across ‘Gödel, Escher, and Bach: An Eternal Golden Braid’ by Douglas Hofstadter. While I appreciate that his work is considered a classic, I found it difficult and ponderous.   Its over 700 pages of popularized work did little to nothing to really sink home Gödel’s theorem and the connections to Turing and Church.  What’s more, Hofstadter seems to say (it’s difficult to tell exactly as he mixes and muddles many concepts) that Gödel’s work supports his ideas that consciousness can emerge from purely mechanistic means at the lowest level.  This point always seemed dodgy to me.  Especially since Hofstadter left me with the impression that Gödel’s theorem showed a fundamental lack in basic logic not an emergent property.

For this go around, I decided that smaller was better and picked up the slim work entitled ‘Gödel’s Theorem’ by Nagel and Newman.  What a difference a serious exposition makes.  Nagel and Newman present all the essential flavor and some of the machinery that Gödel used in a mere 102 pages.

Note that formal logic is not one of my strong suits and the intellectual terrain was rocky and difficult.  Nonetheless, Nagel and Newman’s basic program was laid out well and consisted of the following points.

To start, the whole thing was initiated by David Hilbert, whose Second Problem, challenged the mathematical community to provide absolute proof of the consistency of a formal system (specifically arithmetic) based solely on its structure.  This idea of absolute proof stands in contrast to a relative proof where the system is question is put into relation to another system, whose validity and consistency is accepted.  If the relation between the two is faithful, then the consistency of the second system carries over or is imparted to the first.

Hilbert was unsatisfied by the relative approach as it depended on some system being accepted at face value as being consistent and finding such a system was a tricky proposition.

The preferred way to implement an absolute proof is to start by stripping away all meaning from the system and to deal only with abstract symbols and a mechanistic way of manipulating these symbols using well-defined rules.  The example that Nagel and Newman present is the sentential calculus slightly adapted from the ‘Principia Mathematica’ by Whitehead and Russell.  The codification of the formal logic system depends on symbols that fall into two classes: variables and constant signs.  Variables, denoted by letters, stand for statements.  For example, ‘p’ could stand for ‘all punters kick the football far’.  There are six constant signs with the mapping

The idea is then to map all content-laden statements, like ‘If either John or Tim are late then we will miss the bus!’, to formal statements like ( (J $\vee$ T ) $\supset$ B) with all meaning and additional fluff removed.  Two rules for manipulating the symbols, the Rule of Substitution and the Rule of Detachment, are adopted and four axioms are used as starting points.

In using this system, one has to sharpen one’s thinking to be able to distinguish between statements in the system (mathematical statements like ‘2 > 1’) from statements about the system (meta-mathematical statements like ‘2>1’ is true or that the ‘>’ symbol is an infix operator).  One must also be careful to note the subtle differences between the symbol ‘0’, the number 0, and the concept of zero meaning nothing.

The advantage of this approach is that the proofs are cleaner, especially when there are many symbols.  The disadvantage is that it takes time and effort to be able to work in this language.

The consistency of the formal system is shown when there is at least one formal statement (or formula) that cannot be derived from the axioms.  The reason for this is complicated and I don’t have a good grasp on it but it goes something like this.  The following formula ‘p $\supset$ (~ p $\supset$ q)’ can be derived in the sentential calculus.  If the statements S and ~S are both deducible then any statement you like can be derived from the axioms (via the Rules of Substitution and Detachment) and the system is clearly inconsistent.  In the words of Nagel and Newman:

For the sentential calculus, they point out that the formula ‘p $\vee$ q’ fits the bill since it is a formula, it doesn’t follow from the axiom.  Thus this system is consistent. Note that there is no truth statement attached to this formula.  The observation simply means that ‘p $\vee$ q’ can’t be obtained from the axioms by a mechanical manipulation.  They present this argument in their chapter titled ‘An Example of a Successful Absolute Proof of Consistency’.

Well despite that lofty achievement, they go on to show how Gödel took a similar approach and mostly ended any hope for a proof of absolute consistency in formal systems with a great deal more complexity.  Gödel used as his symbols the numerals and as his rules the basic operations of arithmetic and, in particular, the arithmetic of prime numbers. Using an ingenious mapping from of the variables and constant symbols to numbers, he not only could encode the structure of the formal system itself, he could also encode statements about the formal system as well (meta-mathematics).  In the language of Hofstadter, these are self-referential statements, although Nagel and Newman don’t use this term.

Using this approach, Gödel was able to prove that there is no absolute proof of consistency.  At best, the system can say about itself that it is either incomplete or inconsistent.  If the system is incomplete, there are true statements that are not part of the axioms and that cannot be derived from them.  Enlarging the set of axioms to include them doesn’t work since they presence begets new unprovable truths. If the system is inconsistent, then everything is ‘true’ as discussed above.

Nagel and Newman leave the reader with come final thoughts that are worth contemplation.  On the hope that Hilbert’s program can be successfully completed they have this to say

They also comment on the possibility of proving consistency from an outside-looking-in approach using meta-mathematical techniques when they say

Finally, they have this to say about artificial intelligence (although that term wasn’t in vogue at the time they published

And there you have it. A whirlwind tour of Gödel’s theorem with a surprise appearance of the philosophy from antiquity and the ideas about artificial intelligence.

Something about the book ‘Five Golden Rules: Great Theories of 20^th-Century Mathematics and Why They Matter’ by John L. Casti caught my eye the other day at the library.  On a whim, I signed the book out and started reading.  Living up to the promise of the title, the book had five chapters, each one devoted to one of the great math theories of 20^th century.  All in all, I had been exposed, at least superficially, to all the topics covered so I wasn’t sure what I would get out of the book other than some additional insight into material I already knew or confirmation of my wisdom in staying away from topics that I didn’t.

Anyway, I am quite glad that the mechanism of providence pointed me at this book because the connections that Casti draws are worth thinking about.  None of these connections was as profound for me as the deep link that he explores in Chapter 4 entitled ‘The Halting Theorem (Theory of Computation)’.

In this chapter, Casti first presents the concept of the universal Turing machine (UTM) as a mechanism for attacking the question of Decision Problem (or Entscheidungsproblem) proposed by David Hilbert in 1928.  Casti then couples this presentation with a discussion of the famous Gödel Incompleteness Theorem.

I’m simply a beginner in these fields and Casti omits important details and glosses over a variety of things to help the novice.  From this point-of-view, I can’t recommend his work.  But I am grateful and excited about the perspective he provided by making this linkage.

To understand my excitement, let me first try to fill in some of the background as best as I can.

Hilbert’s Decision Problem asks the following question.  Given a set of input data and an algorithm for manipulating said data, is there a way to know if the algorithm will be able to make a yes/no decision about the input.  For example, if the input data is a set of axioms in a logical system and some corresponding assertion in the same system and the algorithm is a logical formalism, such as the classical syllogism, will the algorithm be able to prove or disprove the assertion as either true (yes) or false (no)?

While the Decision Problem might seem straightforward enough to talk about it at a seminar, when it comes to actually tackling the question there are some vague conceptions that need further elaboration.  Specifically, what does the term ‘algorithm’ really mean and what constitutes a workable algorithm seem to have been the murkiest part when the problem was first posed.

Turing chose to clarify the algorithm concept by the invention of the machine which bears his name.  The UTM is a basic model of computation that is often used to understand the theory behind computer programming. It is also the avenue that allowed Turing to a way to tackle Hilbert’s Decision Problem.  The basic ingredients for a UTM are a tape or strip of paper, divided into squares, a set of symbols (usually ‘0’ and ‘1’) that can be written into the squares, and a box that has a mechanism for moving the strip left or right, a head that reads from and writes to the strip and that contains an internal state that allows the UTM to select an action from a pre-defined set, given the internal state and current symbol being read.  A typical graphical representation of an UTM looks like

The UTM can represent the input to the decision process by a particular pattern of symbols on the strip.  It can also implement the step associated with an algorithm by encoding these also to symbols on the tape.  So the entire nature of the Decision Problem comes down to the question as to whether once the UTM starts if it will ever halt; hence the name of the name of the chapter.

Kurt Gödel took a different approach to answering the Decision Problem.  He developed a way to map any formal system to a set of numbers, called Gödel numbers.  Then by formally manipulating these numbers, he was in position to try to answer Hilbert’s challenge.

Now it is reasonable to suppose that all not every question has a yes or no answer.  Questions about feeling, opinion, or taste spring to mind.  But I think that most of us expect that questions of mathematics and logic and programming have answers and that we should be able to figure them out.  The remarkable thing about the work of both Turing and Gödel is that there are cases where the formal logical system simply can’t decide.

In the language of Turing, there are computational problems for which there is no knowing beforehand if the algorithm will terminate with an answer.  In the language of Gödel, no matter is done to a logical system in terms of refining existing axioms or adopting new ones, there will always be truths that are unprovable.

I was quite aware of Godel’s theorem and even wrestled with it for a while when I was concerned about its implications to physical systems.  Eventually, I decided that while man’s logic may be limited, nature didn’t need to worry about it because she could make decisions unencumbered by our shortcomings.

I was also quite aware that Turing’s machine was used fruitfully as a model computation.  What I was unaware of until reading Casti’s book was the parallel between the conclusions of Gödel and of Turing.

And here we arrive at the source of my excitement.  As I’ve already said, I remain convinced that Nature can decide – that is to say that Nature is free of the issues discussed above.  And yet, in some capacity the Universe is an enormous Turing machine.

So why does Nature always make a decision and why does the computation of trajectories, and the motion of waves, and evolution of quantum bit of stuff always reach a decision?  It may not be the decision we expect or anticipate, but it seems clear that a decision is reached.  And so, by looking at how the Universe as a Turing Machine (UaaTM) differs from a Universal Turing Machine, one may learn more about both.  This is the exciting new idea that has occurred to me and one which I will be exploring in the coming months.