Bill Wadge's Blog

I’ve been to Greece often enough that I’ve picked up a bit of (modern) Greek. Like anyone in  my situation, I’ve had fun spotting Greek words with Englishs cognates based on Greek roots, popping up with unusual meanings in unusual contexts. Here’s my story of a typical day in a Greek visit, using some of these words. (I also translate some Greek idioms, like “the Bill Wadge”). Based on a true story.

Continue reading →

Time for another break from research (at least the normal kind).

I seem to be always discovering fundamental Laws of the Universe, especially about teaching. I’d like to share some of them with you.  They are each called “Wadge’s Law” … by me. Maybe the name will catch on. Here they are.

Wadge’s Law (of traffic)

No matter how late you go through an orange light, the guy/gal behind you follows you through.

Nothing says fun like formal power series!

A formal power series is a (usually) infinite polynomial in x. For example

1 + x + x² + x³ + x⁴ + …

This is an expression, not a number. If we give a value to x, we may get a number, or the evaluation may run away (diverge) on us (if |x|≥1).

Continue reading →

Lucid is based on a simple temporal logic. The time model follows from formalizing iteration as it appears in imperative programs with, say, while or for loops.

In this model there is a first or initial time point, and every time point has a unique successor. Imperative iterations normally terminate, so we should have only finitely many time points. Lucid avoids the complications of finite time domains by making everything at least notionally infinite, so that the domain of time points is the natural numbers with the usual order.

In temporal logic logicians have studied a huge variety of time domains. What do they mean in terms of iteration and how do we write iterative programs over nonstandard time domains?

Continue reading →

In the last post we introduced eod (end-of-data), a special sentinel value used to mark the end of a finite Lucid stream. Streams in Lucid are all formally infinite (non terminating) but we can use eod to represent finite streams as infinite ones filled with eod past a certain point. For example  the finite stream of the first five  primes is

2, 3, 5, 7, 9, eod, eod, eod, …

The input and output conventions are adjusted to interpret eod as termination. If the above stream is the output, the implementation will ‘print’ the first five values and terminate normally. If a user inputs the first five values, then terminates the input stream, this is not treated as an error. Instead, the ‘missing’ values are evaluated to eod if requested.

Continue reading →

As I’ve already explained, Lucid can be understood as functional programming with an added time dimension. What about other dimensions? In particular, what about a space dimension?

The late Ed Ashcroft and I discovered this possibility when we tried to “add arrays” to Lucid. Initially, we intended Lucid to be a fairly conventional, general purpose language. So we considered various ‘features’ and tried to realize them in terms of expressions and equations.

Continue reading →

And He took the five loaves and the two fish, and looking up to heaven, He blessed and broke and gave the loaves to the disciples; and the disciples gave to the multitudes. So they all ate and were filled, and they took up twelve baskets full of the fragments that remained. – Matthew 14.

The logician Willard Quine defined a paradox as an “absurd” statement backed up by an argument.

The famous result of Banach and Tarski definitely counts as a paradox by this definition. They proved that it is possible to take a unit sphere (a ball with radius 1), divide it into five pieces, then by rotations and translations reassemble it into two unit spheres.

Continue reading →

The Liar Paradox is simple enough to explain – is the following statement true or false?

This statement is false.

If it’s true then it’s false, but if it’s false then it’s true  … nothing works.

In my not-so-humble opinion, most (maybe all) paradoxes are the last step in a proof by contradiction that some unstated assumption is false.

In this case, the assumption is that the above statement is meaningful – is either true or false. The assumption is false, the statement is meaningless. End of paradox.

Continue reading →

In the last post there was plenty about Gödel but not much about Grammar and Go-the-game. Time to pay my debt!

Basically I said that Gödel’s results proved that no fixed set of facts and rules can on their own form the basis of mathematical knowledge. I said that hard-earned experience is indispensable. That mathematics is ultimately an experimental science. (This is not the usual take on Gödel’s work.)

Continue reading →

More than eighty five years ago  Kurt Gödel proved, roughly speaking, that no fixed set of a formal facts (like 23+14=37) and rules (like x+y = y+x) can establish the truth or falsity of every theorem about arithmetic over the counting numbers.

This result, known as Gödel’s Theorem, has a lot of formal and informal consequences. It means there is no computer program that can infallibly decide whether or not a statement about arithmetic is true or false. It means we will never know everything about arithmetic, though we may know more and more as time goes on. It means, however, that this knowledge will not come about purely as a result of manipulating formal facts and rules. We will have to rely on other sources, including experiment.

Even more interesting is the fact that this situation – the limits of facts and rules – reappears in other domains, including games, natural language, and even psychology.

Continue reading →