Turing tests

As a pendant to the last post, let me suggest that a true AI should be able, with no prior domain-specific knowledge, to (1) learn the rules of sudoku from a verbal description, and go on to (2) learn and apply the solving strategies I describe, including especially the form of reasoning that exploits the solvability guarantee.

As far as I know, we are very very far from such a ‘true AI’.

Posted in Uncategorized | Leave a comment

Solving sudoku puzzles

Here is how I approach sudoku, almost all of it learned ‘on the job’.

[Ideally, I would include in this post nice pictures of the grid, or pieces of it, but I’m not prepared to invest that much effort in html hacking/research. So we will have to settle for verbal descriptions.]

I have my own notion of how to label the 81 squares: the obvious a1–i9 scheme borrowed from chess doesn’t appeal to me because the digits 1–9 are already needed to represent the items being placed. Instead I name the columns A–I, left to right, and the rows R–Z, top to bottom. So squares have names like CS, HX, and so on.

As I mentioned before, I transcribe newspaper or online puzzles onto my own grids (on decent paper that can take fountain pen ink without bleeding), about 7cm square.

The notations I make (aside from filling in digits whose position can be determined) are almost always assertions of the form ‘digit k must be placed in one of the squares of set Σ’. For example, if I can determine that there must be a 7 in one of the two squares {AR, AS}, I write a small ‘7’ on the horizontal line that separates those squares. This same fact can be written in a linearized form, for discussion purposes, as 7AR|7AS, or more compactly as 7ARS (‘distributing’ the ‘A’ over the ‘R’ and the ‘S’ in the obvious way).

I have conventions for notating facts involving more widely separated squares; the details are unimportant. I see what I can accomplish by considering pairs of squares, and then work up to triples and so on as needed. Note, though, that I very seldom resort to exhaustive listings of the digits a single square might contain: assertions like 7AR|9AR.

Using these methods, the most difficult placements to see are those where, for a given square, all digits but one have been ruled out; but it usually suffices to glance occasionally at the rows or columns that have only a few squares not labeled in any way, note the digits that are prima facie candidates for those squares, and see what eliminations can be made in the light of the other sudoku constraints.

Early on in teaching myself sudoku I worked out the important type of reasoning whereby (to use the linearized version of my notation) the facts 3EFX and 7EFX combine to form the much more useful fact (37)(EFX). I refer to this as a ‘locked pair’, although I don’t think this is the standard nomenclature. There are two digits to be placed in two squares, and they ‘lock out’ other digits that might otherwise have been placeable in those squares. So if the facts 3EFX and 8EXY are already known, discovering the fact 7EFX locks the squares EX and FX, and we can place the digit 8 in square EY.

These methods suffice for the vast majority of puzzles. I’ve read about the technique known as ‘X-Wing’, which involves squares that themselves form a rectangle, such as AR, FR, AV, FV. If we determine the ‘horizontal’ facts 3AFR and 3AFV, we can also conclude the ‘vertical’ facts 3ARV and 3FRV. But I almost never find myself using this kind of reasoning.

On the other hand, a form of reasoning that I use often but have never seen discussed (it’s not easy to search for) involves what I call solvability arguments. Here we rely on the fact—or meta-fact—that published sudoku puzzles are guaranteed to have a unique solution.

Here’s how it works in the simplest form: suppose we have the facts (45)(GHT) and 4GHZ. We can conclude that ¬5GZ and ¬5HZ, because otherwise the four squares involved would be undecidable: we might have 4 in GT and HZ and 5 in HT and GZ, or the other way around. Looking at this from the point of view of a sudoku constructor, if four squares forming a rectangle contain only two digits among them, one of those squares must be included among the données or the puzzle will be unsolvable.

In another common setup, suppose again that we have (45)(GHT) and that 1, 4, and 5 need to be distributed among squares GX, GZ, and HZ. These latter squares form a triangle. The two linear placements (45)(GXZ) and (45)(GHZ) are both impossible: the first would make GT unfillable, while the second is ruled out as in the previous paragraph. So only the diagonal placement (45){GX,HZ} is possible, and we can place 1 in the remaining square of the triangle, GZ.

Sometimes solvability arguments can turn into long daisy chains: if we have, for example, (35)(AUV), (86)(DUV), (13)(EUV), and (16)(GUV), we can see that *(58)(HUV) would cause a problem, by joining up the ends of the chain 5–3–1–6–8 and making all ten squares unsolvable.

Posted in Uncategorized | 1 Comment

Learning from our mistakes

… but not in the usual sense :-)

Various people have noticed that the errors we make can give interesting insight into brain processes that are normally invisible. I think I’ve read that Douglas Hofstadter shares this interest, and keeps an error log for later analysis.

Errors committed in the process of handwriting are a good example. Here’s one I caught a few days ago. The phrase was ‘shoe repair’; I was writing lower-case italic (I seldom use a true cursive) and found that I had started to turn the first stroke of the first ‘r’ into a descender. I analyze this as bleed-forward from the planned formation of the ‘p’ that was to have been the next consonant. I think I have noticed, from this and similar cases of interference, that consonant letters seem to occupy sort of a separate ‘channel’ in the brain.

Posted in Uncategorized | Leave a comment

Teaser for The Shadow of Consciousness

I just got my copy of The Shadow of Consciousness: A Little Less Wrong by Peter Hankins, the consciousness behind the very fine long-running blog Conscious Entities. Here, to tempt you to order the book, is the Prologue:

In the latter part of the twentieth century there was a remarkable quest into one of the last areas of darkness on the intellectual map. The problem of explaining what consciousness is and how it works had in the past been considered such difficult territory, a landscape so strewn with pitfalls and so rich in scope for embarrassment and failure that prudent researchers didn’t go there; it became a kind of Forbidden Realm. Now, though, there was optimism in the air and one after another new expeditions were being equipped.

The venture was not co-ordinated; it was more as if, one after another, a stream of aspiring heroes rode out to take on the dragon and bring back the prizes single-handed. Several different strategies were advocated and champions of all kinds came to try them, from grizzled veteran knights with Nobel prizes already slung from the pommels of their saddles, to optimistic young wizards with what they hoped were magic formulae. There were two prizes that could be won on this quest; an Easy One and a Hard One, and there was no agreement about which to take first, or even that both prizes were real. Some said they were real enough, but only to be found in a land of mystery barred to humankind.

The quest turned out to be more difficult than the optimists had expected. In different ways and different places the venturers ran into inexplicable barriers in the darkness, or found themselves bogged down in what seemed to be invisible swamps. Those who pursued the grail of the Hard Quest often contented themselves with merely bringing back evidence that the beast was truly out there; but sometimes they fought a battle and came back with trophies that seemed to others, on examination, to be the heads of deer or rabbits rather than that of a fearful monster. Some heroes in this position insisted that the monster of the quest had always, in fact, been a rabbit—what else could it have been? Some disdained that quest altogether; what dragon, they demanded?

There are still bold folk riding out to try their prowess now and then; but the first impulse and the early optimism has died down. Thoughtful commentators generally do not expect the great quest of consciousness to be achieved very soon.

We have learned a few things, though. I think we can see that many of the attempts on the prize to date, and indeed some investigations that were pursuing other quests, were running into essentially the same invisible problems in different forms and different places. Four things about the world have proved especially troublesome: inexhaustibility, irrelevance, haecceity, and (by no means least) reality.

By plotting the places in which the explorers were stopped by something dark and ungraspable and adding the result to the fragments of trustworthy description brought back by scarred and battered explorers we can get a grip on these problems and, as it were, sketch the outline of the mighty but elusive beast from the shadow it casts.

That is what I mean to attempt in what follows—and in so doing learn, I hope, how to be a little less wrong.

You can learn more about the ‘four especially troublesome things’ in the author’s blog posts Inexhaustibility, Pointing, Haecceity, and Reality.

Posted in Uncategorized | Leave a comment

Brain exercise

Just something quick today. See how many English monosyllables (base forms only) you can think of (within a reasonable amount of time) in which the vowel sound is spelled ‘oa’ and pronounced like the vowel in ‘home’. A list of 48 is given in the next paragraph (highlight to make visible).

[oaf, oak, oast, oat, oath, boast, boat, bloat, broach, coach, coal, coast, coat, coax, cloak, croak, foal, foam, float, goad, goal, goat, gloat, groan, groat, hoax, load, loaf, loam, loan, loath, moan, moat, poach, roach, road, roam, roan, roast, soak, soap, shoal, shoat, stoat, toad, toast, throat, woad]

Posted in Uncategorized | 2 Comments

The last TECO user?

That might be me, but more likely I am one of a small group.

What is TECO? In a few words, “a text editor which is also a complete programming language”. There is a fine and entertaining overview in this memoir by Dan Murphy, the original author; you can also take a look at what Wikipedia has to say.

TECO—in fact, my own implementation thereof—is still the text editor I use every day. Here’s how that came about.

Back in the 70’s and 80’s I used TECO in various forms on PDP-10 systems, including a version that I think was called ‘TV’ in which the upper portion (about 18 lines) of a terminal screen displayed a window into the buffer being editing, while the lower portion displayed the current command as typed.

This was the model for my first reimplementation, for the Atari ST, in 68000 assembly language. This was part of a larger program—about 50K bytes in total, as I remember it—that incorporated a 68000 assembler and disassembler, some primitive debugging facilities, a simple command line and a few internally-coded commands (list a directory, for example), and a terminal emulator.

A few years later, when faced with a job where I was using an 8086-type machine, I made a second assembly-language implementation that used a swap file and other mechanisms to hide that architecture’s nasty 64K limit on contiguous arrays.

Finally I was able to move to a third version, written in CWEB, Donald Knuth’s admirable ‘Literate Programming’ dialect of  C. This is what I use today, on both Linux and OS X.

Catering only for myself, I never felt the need to implement all the obscure commands that made their way into TECO. My versions have always been whole-file editors, disregarding the read-a-page / write-a-page cycle that was part of the original. I have always treated the command language as case-sensitive; by making capital letters available in their own right this in turn avoids the need for the two-character ‘Ex’ and ‘Fx’ commands used by ‘classic TECO’.

In further nods toward modern programming practice (and sanity) I never implemented the GOTO command, relying only on loops (and loop exits) and conditionals. Even though TECO’s native command language is basically a kind of bytecode, my versions have always ‘compiled’ the entire command string into a second version for interpretation; this has the advantage that if there is a (detectable) typo it can be caught before making any changes to the editing buffer.

[added 2017-05-02]: One innovation that I made in my versions (even, I think, the first, Atari ST version—but I have no way to check right now) was that the four keys ‘[’, ‘]’, ‘;’, and ‘'’, which form a little grid toward the right end of the QWERTY keyboard, become immediate-action commands that cause the displayed window on the buffer to scroll. (None of them are needed as the first character of a legitimate command string, as it happens.) ‘[’ brings in a new line at the top of the window (‘scroll down’) while ‘;’ brings in a new line at the bottom of the window (‘scroll up’); ‘]>’ and ‘'’ are ‘page down’ and ‘page up’. Note that unlike many editors these scrolling actions do not affect the location of ‘point’ (where editing happens), and in fact can leave the window in a state where ‘point’ is not displayed. An empty command (double-ESC) will redraw the window centered on the current position of ‘point’. Having done this, it made sense to add ‘/’ (also not needed at the beginning of a command string) to mean “Please move ‘point’ to the middle of the window as currently displayed.”

Posted in Uncategorized | 2 Comments

Thoughts on rereading The Moon is a Harsh Mistress

There are a number of novels that I have read more than once, and in some cases many times, finding that the world they transport me to is one worth revisiting. Most of these are genre novels, including the work of a number of mystery writers with a highly ‘literate’ style. (This stylistic texture is what largely characterizes the ‘world’ of these books.) I have all the mystery works of Dorothy Sayers, Cyril Hare, and Edmund Crispin, almost everything by Michael Innes and Michael Gilbert, and a good few by Geoffrey Household. Maybe some day I’ll have more to say about these authors or their works.

Then there is the fantasy / science-fiction continuum. In these cases the book takes one to a different ‘world’ in a somewhat stronger sense. Here The Lord of the Rings is the standout: I can’t even estimate how many times I’ve read it, or dipped into it, over the last ~45 years.

I’ve re-read much of Robert Heinlein’s work, but the ones with real staying power are his two masterpieces, Stranger in a Strange Land and The Moon is a Harsh Mistress, the subject of this post.

You should read it, of course. (Some spoilers follow, so read on with discretion if you care about such things.)

One thing that the Wikipedia article doesn’t mention explicitly is the way the use of the Moon as a penal colony follows the precedent of Australia. (I don’t know if it’s still true, but where American English uses ‘transportation’, British usage long preferred ‘transport’, the former word being strongly associated with the meaning ‘exile of convicts to Australia’.)

Since various nations exiled prisoners to the Moon, the colloquial English spoken there is sprinkled with lexical and grammatical elements from, especially, Russian (the words gospodin and tovarishch, the omission of articles). The Australian connection is alluded to by the title of the first of the book’s three parts, “That dinkum thinkum”. All this linguistic flavor contributes to the depth and reality of the alternate world of the novel.

The main action of the novel concerns the revolution that frees Luna from the hegemony of Earth’s Federated Nations. Some economic squeezing has been going on, causing unrest and revolutionary sentiment, but the stakes are raised when the three central human characters come to realize that the ecology of Luna, involving the mining of lunar ice and mineral nutrient deposits to support the growing of grain for shipment to Earth, is radically unsustainable and will result in “food riots six years hence, cannibalism in eight”.

Our situation is not all that different, really. The size of Earth’s current (and projected) population, and the energy-use expectations of the richest one or two billion of us, are also radically unsustainable. But we have no easy targets to revolt against: “We have met the enemy and he is us.”

A notable feature of the novel, and the reason I wrote ‘the three central human characters’ above, is the creation by Heinlein of a fairly well-realized and admirable character who is an AI: Mycroft (‘Mike’) Holmes. The premise, as the narrator, Mannie, states it on page 2 is:

When Mike was installed in Luna, he was pure thinkum—a flexible logic—“High-Optional, Logical, Multi-Evaluating Supervisor, Mark IV, Mod. L”—a HOLMES FOUR. … Human brain has around ten-to-the-tenth [1011, actually] neurons. By third year Mike had beter than one and a half times that number of neuristors.

And woke up.

Indeed, from the use of the expression “woke up”, it is clear that Mike is not only an AI but an artificial consciousness. It also becomes an essential plot point that the ‘owners’ of Mike do not realize that he has achieved sentience: only Mannie understands that Mike is no longer a mere computer, knowledge that he shares only with his two co-conspirators. Mike provides the calculations as to how pressing the ecological crisis is; he then becomes the ‘chairman’ of their revolutionary cell, and invents a second personality ‘Adam Selene’ to play that role by audio and video.

Although this premise is makes for a highly appealing element in the novel, it is, of course, absurd. If AI/AC ever happens, it will most certainly be by design and intention, not inadvertence: the building blocks (‘neuristors’) will likely have an architecture very different from what is most economical in the building of a ‘mere computer’.

Still, as many times as I have read the book, I get sad when Mike ‘dies’ at the end ….

Posted in Uncategorized | Leave a comment