Transporter Beam of Death SMBC


As I was reading Roger Penrose’s 1989 “The Emperor’s New Mind,” I was amused to find his argument against the teleporter technology used in the Star Trek series. As far as I know, this is one of the earliest cases of someone seeing teleportation as being a complete dissolution of the person being beamed, tantamount to them being killed, then reassembled from new raw material at the destination point. One of the questions he raises is, “what if you send the target’s data to a repeater station, and the station fails to notify the sender that the target has been fully reassembled on arrival?” In this situation, the sender would rebuild the target, only to find out that they now have two versions of the same person. Which one would they have to kill in order to rectify this?

Roger seems to have overlooked the possibility that this kind of situation is highly desirable for overcoming the traditional shortcomings of DNA cloning (that is, cloning someone from a DNA sample will not duplicate their thoughts or memories). Now, if you use a “malfunctioning” teleporter, you get perfect clones. Problem solved.

Yet another proven use for 3D printers…

Anyway, these are some of Zach Weinersmith’s takes on the topic. From Saturday Morning Breakfast Cereal.


(Images used for review purposes only.)

Colossal Gardner, ch. 39


We now enter the section on Physics, starting with Time Travel.
According to Gardner, the very first time travel SF story, The Clock That Went Backwards, was written by Edward Page Mitchell, editor of the New York Sun, published anonymously in 1881. It was quickly forgotten until it was reprinted by Sam Moskowitz in his anthology of Mitchell’s stories, The Crystal Man, in 1973. H. G. Wells, then 22, started The Chronic Argonauts in 1888 in The Science Schools Journal, but he was so ashamed by it that he ended the serial after 3 installments and destroyed every copy he found. He completely rewrote the tale as The Time Traveler’s Story, for The New Review beginning in 1894. He became instantly recognizable when the book was released in 1895. What Martin likes about this novella is in the introduction, where the Traveler describes the theory behind his machine: “Time is a fourth dimension. An instantaneous cube can not exist. The cube we see is at each instant a cross section of a “fixed and unalterable” four-dimensional cube having length, breadth, thickness and duration. “There is no difference between Time and any of the three dimensions of Space,” says the Time Traveler, “except that our consciousness moves along it.””


(All rights belong to their owners. Images used here for review purposes only. Feynman’s graph for a time traveler to the past.)

He then goes on to mention Isaac Asimov’s The End of Eternity, and Vonnegut’s Slaughterhouse-Five, and the work of Hermann Minkowski when he tidied up Einstein’s special theory of relativity. We also get examples for Kurt Godel, and Richard Feynman (part of which earned him a Nobel Prize in 1965 for his space-time approach to quantum mechanics). Then there’s Fredric Brown’s First Time Machine, which traps the main character in a 60-year time loop. In general, time travel stories involve some form of paradox (someone goes into the future, takes an artifact back into the past, and that becomes the invention of the thing that only existed in the future), and various theories have formed to address these paradoxes. One example is with tachyons, theoretical particles that move faster than light. If they do exist, they can’t be used for communication, according to G. A. Benford, D. L. Book and W. A. Newcomb in Tachyonic Antitelephone.

The rest of the chapter addresses the various forms of paradoxes, and how different SF authors and physicists tried to work around them, including the Many Worlds interpretation. It ends with Fredric Brown’s Experiment, with Professor Johnson showing off his time machine. He’s holding a brass cube and standing near the platform of the machine. It is 6 minutes to 3 PM, and he tells his audience that at exactly 3 he’ll place the cube on the platform and send it 5 minutes into the past. Therefore, at 5 to 3, the cube should appear on the platform and disappear from his hand, and exactly at 3, disappear from the platform and reappear in his hand to be sent back in time. At 5 to 3, the cube makes its jump, and Johnson is very happy. But one of his guests asks, “what if you change your mind now and DON’T send it back in time?” Johnson thinks about this and decides to see what will happen. At 3 PM, he doesn’t put the cube on the platform. The cube remains, but the entire universe, including Professor Johnson, his colleagues and the time machine, disappears.

Time travel limericks:
A. H. Reginald Buller, Canadian botanist (1923):
There was a young lady named Bright,
Whose speed was far faster than light;
She started one day
In a relative way,
And returned on the previous night.

J. A. Lindon:
When they questioned her, answered Miss Bright,
“I was there when I got home that night;
So I slept with myself,
Like two shoes on a shelf,
Put-up relatives shouldn’t be tight!”

Challenge: Prove that commercial time travel is not a pipe-dream.

Penrose, Turing Machine 2


The way Roger Penrose develops his code examples is kind of backward, as if we’re starting by learning a higher level language like C, and slowly edging closer and closer to machine code. This is not really a big deal, but it does help to know the end state we’re heading for.

The next algorithm is a unary implementation of Euclid’s routine for calculating the greatest common divisor. I’m going to use this opportunity to make my Turing machine a bit more universal. Instead of hardcoding the algorithm into the Select Case code, I’m going to store it in a separate textfile that I’ll then read into an array at the start of the program. The tape head transport section will work the same. It’s just that I’ll be checking the ‘current state + read bit’ by using a for-loop to run through the array to locate the instruction for the matching algorithm state. In this way, my Turing machine can run any algorithm written for unary data (data where numbers are represented by long strings of 1’s that are zero-separated). I will, though, hardcode in the algorithm file name, because I’m lazy that way.

First, the Euclid algorithm. Instead of using an arrow (“->”), I’m just going to pick a dash (“-“) to separate the current state value from the instruction for that state. Note that the original program from the last blog entry didn’t really make it obvious that the state numbers are binary. They could easily be decimal or hexadecimal, as long as I remain consistent about it. But, eventually we’re going to want everything to be in binary, so I’ll start making the state values binary here.

‘ Penrose unary version of Euclid’s GCD algorithm
‘ Stored in the file euc.txt.

00-00R
01-11L
10-101R
11-11L
100-10100R
101-110R
110-1000R
111-111R
1000-1000R
1001-1010R
1010-1110L
1011-1101L
1100-1100L
1101-11L
1110-1110L
1111-10001L
10000-10010L
10001-10001L
10010-100R
10011-11L
10100-00STOP
10101-10101R

Then, the program is:

‘ turing_m2.vbs
‘ More universal machine. Reads euc.txt algorithm by default.

””””””
Const ForReading = 1, ForWriting = 2, ForAppending = 8

dim algo(100, 4)
algoMax = 0

dummy = readAlgorithm(“euc.txt”)

tapeBit1 = “1111111111111111”
tapeBit2 = “11111111”
tapeReel = “0000000” & tapeBit1 & “0” & tapeBit2 & “000”
headPos = 1
machineState = “0”
RStop = false
tapeChr = 0

wscript.echo vbCRLF & “GCD for ” & countOnes(tapeBit1) & ” and ” & countOnes(tapeBit2) & ” = ?”

while Not RStop
tapeChr = mid(tapeReel, headPos, 1)
fullStatement = machineState & tapeChr

stateNum = findState(fullStatement)

if(stateNum = -1) then
RStop = true
else
if(algo(stateNum, 3) = 0) then
RStop = true
end if
machineState = algo(stateNum, 1)
dummy = writeToTape(headPos, algo(stateNum, 2))
headPos = moveHead(headPos, algo(stateNum, 3))
end if
wend

wscript.echo “Ping: ” & left(tapeReel, headPos – 1) & ” (” & countOnes(left(tapeReel, headPos – 1)) & “)”

Previously, moveHead() received headPos and moveDirection, where moveDirection was either “L” or “R”. Because I’m now storing each piece of the algorithm in separate cells of the algo() array, it’s actually easier to preload the array with the integers -1 and 1, and simply add them to headPos. I still have to worry about trying to move past the ends of the tapeReel string, though.

Function moveHead(hp, dir)
ret = -1
if(hp = 1 AND dir = -1) then
tapeReel = “0” & tapeReel
ret = 1
elseif (hp = len(tapeReel) AND dir = 1) then
tapeReel = tapeReel & “0”
ret = hp + dir
else
ret = hp + dir
end if
moveHead = ret
end Function

writeToTape() doesn’t have to change.

Function writeToTape(wttHP, wttVal)
lstr = “”
rstr = “”
if(wttHP = 1) then
rstr = right(tapeReel, len(tapeReel) – 1)
elseif (wttHP = len(tapeReel)) then
lstr = left(tapeReel, wttHP – 1)
else
lstr = left(tapeReel, wttHP – 1)
rstr = right(tapeReel, len(tapeReel) – wttHP)
end if
tapeReel = lstr & wttVal & rstr
writeToTape = true
end Function

countOnes() doesn’t have to change, either.

Function countOnes(coStr)
ret = 0
for i = 1 to len(coStr)
if(mid(coStr, i, 1) = “1”) then
ret = ret + 1
end if
next
countOnes = ret
end Function

This part is all new. I’m passing the name of the algorithm file, which I then open and read, and end with closing the file. Each line will take the form “state+BitRead-newState+writeBit+Direction” (eg. – “10101-110R”), where the state is “1010”, BitRead = “1”, newState = “11”, writeBit = “0”, and Direction = “R”. I’ll parse each line and store it in the multi-dimensional array algo() as follows:
algo(lineNo, 0) = state & BitRead
algo(lineNo, 1) = newState
algo(lineNo, 2) = writeBit ‘ string character
algo(lineNo, 3) = Direction ‘ L = -1, R = 1, STOP = 0
Note that I default algo(lineNo, 3) to 0, in case there’s a bad value for Direction, which will force the machine to stop when it reaches that state in the main program.

Function readAlgorithm(rAFN)
set fso = CreateObject(“Scripting.FileSystemObject”)
wscript.echo “Reading file: ” & rAFN
Set inData = fso.OpenTextFile(rAFN, ForReading, True)

while(not inData.AtEndOfStream)
str = inData.readline
algo(algoMax, 0) = left(str, instr(str, “-“) – 1)
tempStr = right(str, len(str) – instr(str, “-“))

algo(algoMax, 3) = 0 ‘ Default to Stop
if(instr(tempStr, “STOP”) > 0) then
algo(algoMax, 1) = left(tempStr, len(tempStr) – 5) ‘ New state
algo(algoMax, 2) = mid(tempStr, len(tempStr) – 5, 1) ‘ Write bit
else
algo(algoMax, 1) = left(tempStr, len(tempStr) – 2) ‘ New state
algo(algoMax, 2) = mid(tempStr, len(tempStr) – 1, 1) ‘ Write bit
tempDir = right(tempStr, 1) ‘ Move direction
if(tempDir = “L”) then
algo(algoMax, 3) = -1 ‘ Move left
elseif(tempDir = “R”) then
algo(algoMax, 3) = 1 ‘ Move right
else wscript.echo “Bad Move Head Direction: ” & tempDir
end if
end if

algoMax = algoMax + 1
wend

inData.close
readAlgorithm = true
end Function

This part is also all-new. findState() replaces the original Select Case code from the last blog entry. It simply runs through the algo() array, searching algo(lineNo, 0) for a match to ‘state+BitRead’. If it finds a match, it returns that array row number. Otherwise, it prints out an error message, and returns -1, which the main program will interpret as a program abort.

Function findState(fsS)
ret = 0
while (strComp(algo(ret, 0), fsS) <> 0 AND ret < algoMax)
ret = ret + 1
wend
if(ret = algoMax) then
wscript.echo “State not found: |” & fsS & “|”
ret = -1
end if
findState = ret
end Function

Amazingly, everything worked the first time (after I’d worked out all the other bugs). What I mean is, the euc.txt algorithm executed perfectly. Using A = 12 and B = 8, euc.txt found the greatest common divisor to be 4. I tried a few other values, and the answers all came out right, and the program ran fast.

TapeReel = “000111111111111011111111000”

Next up, UN x 2.
And, taking the next step to universality, with the introduction of binary expansion.

Carded answer, and a Widget


Puzzle: What is Smith’s rule in the example game?

“If the last card is lower than the preceding legally played card, play a card higher than the last card, otherwise play a lower card. The first card played is correct unless it is equal to the starter card.”

Plus – An Eyebeam Widget

The nuts and bolts of Escher World. (Care of Sam Hurt.)

Colossal Gardner, ch. 38


We close out Games and Decision Theory with The New Eleusis. The game Eleusis was invented by Robert Abbott, then an undergraduate at Colorado University, in 1956. Abbott had been studying the “Aha!” moment when people make discoveries, and Eleusis, named after the ancient Greek Eleusinian Mysteries, is a good simulation system for this. Abbott released the full rules for the game in his book Abbott’s New Card Games (1963). Martin D. Kruskal, a mathematical physicist, made improvements to it, releasing his rules in the monograph, Delphi: A Game of Inductive Reasoning (1962). Gardner himself introduced Eleusis in his column in Scientific American in 1959, and because it had evolved so much over the years, he decided to write the current chapter as an update.

For the newest (at the time of the writing for this chapter) version, you need 4 to 8 players, and two standard decks of playing cards (sometimes a round lasts long enough that you need a third deck). A full game consists of one or more rounds, and players take turns dealing each round. Because the players are attempting to divine the thinking processes of the dealer, that player is often given the titles God, Nature, Tao, Brahma, the (Delphi) Oracle, or simply Dealer. The dealer’s first job is to think up a “secret rule.” This rule defines what cards can be legally played during a player’s turn. The players have to determine this secret rule, and the faster one of them does, the higher their score. One key part of the game is that the dealer gets scored too, so it’s to their benefit to create a rule that is not too easy or too hard.

An example of a rule that’s too easy: “Play a card of a color different from the color of the last card played.” Gardner’s suggestion for a better rule is: “Play so the primes and non-primes alternate.” But, depending on the players, this rule could be too hard or too simple. A rule that’s too difficult would be: “Multiply the values of the last three cards played and divide by 4. If the remainder is 0, play a red card or a card with a value higher than 6. If the remainder is 2, play a black card or a picture card… etc.”

Martin offers 3 example rules for use with inexperienced players.
1) If the last legally played card was odd, play a black card. Otherwise, play a red one.
2) If the last legally played card was black, play a card of equal or higher value. If red, play a card of equal or lower value (face cards are numbered 11, 12, 13. Ace = 1).
3) The card played must be either of the same suit, or the same value as the last card played.

“The secret rule must deal only with the sequence of legally played cards.” It cannot include things like the sex or ages of the players, the time of day, or whether Dealer scratches his/her ear, etc. The secret rule must be written down for later confirmation, and it is ok for Dealer to give a hint, such as “Suits are irrelevant to the rule,” or “The rule depends on the two previously played cards.”

After recording the rule, Dealer shuffles the double deck and deals 14 cards to each player and none to themselves. They then place a “starter card” face up on the table to the extreme left of the playing surface. To determine the starting player, Dealer counts off the value of the starting card, going around the players from Dealer’s left. The indicated player begins play, which continues clockwise around in the circle. A play consists of placing one or more cards on the table. To play a single card, the player takes a card from their hand and reveals it to everyone. If the card is playable according to the rule, Dealer says “Right,” and it is then placed to the right of the starter card on the “main line.” (The main line is the list of correctly played cards extending horizontally to the right. See below.)

If the card doesn’t fit the rule, Dealer says “Wrong,” and it’s placed under the last card played. Vertical columns of cards are called “sidelines,” and consecutive incorrect plays extend the same sideline downward. Dealer gives that player 2 more cards, expanding their hand, as a penalty. If a player thinks they know the rule, they can play a “string” of 2 to 4 cards at once, overlapping the cards slightly to preserve their order and to show them to everyone. If the full string is correct, Dealer says, “Right,” and they are added to the main line as normal. If any one card is wrong, Dealer says “Wrong” to the entire string, and deals out twice as many penalty cards as there are cards in the string. The below illustration shows an example of all the rules explained so far. The secret rule is: “If the last legal card is odd, play black, otherwise play red.”


(All rights belong to their owners. Images used here for review purposes only. Example New Eleusis game in progress.)

Players get better scores by getting rid of as many of their cards as possible, and it helps to guess the secret rule to do that. If a player thinks they know the rule but they don’t have any further cards to play, they can declare “No play” and show all their cards to everyone. If Dealer says, “Right” and the player has 4 or fewer cards left then the round ends. If the player has 5 or more cards and is right, their cards are returned to the deck and they are re-dealt 4 fewer cards than they’d been holding and the round continues. If the Dealer announces “Wrong,” Dealer takes one of the correct cards and puts it on the main line, and deals that player 5 more cards as a penalty. Therefore, if a player hasn’t figured out the rule but thinks they have no legal play, it’s better if they just play a card at random instead of saying “No Play.”

Alternatively, if the player thinks they know the secret rule, they can declare themselves a Prophet under the following conditions:
1) They have just played (correctly or incorrectly) and the next player hasn’t played yet.
2) There’s no Prophet yet.
3) At least two other players besides themselves and the dealer are still in the round.
4) They have not been a Prophet before in this round.

When a player declares themselves to be a Prophet, they put a marker on their last card played (a black chess king or queen). They keep their cards but stop playing them until they are overthrown. The play continues clockwise, skipping the Prophet. When a player plays a card, the Prophet says “Right” or “Wrong”, and Dealer validates or invalidates the call with “Correct” or “Incorrect.” If correct, the played cards are placed on the main or side lines as before. If the Dealer says “Incorrect,” the Prophet is immediately overthrown and declared a False Prophet. Dealer removes the False Prophet’s marker from the table, and deals out 5 extra penalty cards. The False Prophet cannot become a Prophet again in that round, but any other player can. Abbott has said there’s an amusing analogy with science here: “The Prophet is the scientist who publishes. The False Prophet is the scientist who publishes too early.” Martin adds “It is the fun of becoming a Prophet and overthrowing a False Prophet that is the most exciting feature of New Eleusis.”

After a Prophet fails, Dealer takes over as Dealer again, completing the play that overthrew the Prophet, placing the card or string on the main or side lines. If the play was wrong, Dealer does not give the last player any penalty cards. This exemption rewards players for taking daring plays to overthrow the Prophet. In the words of Karl Popper, it “encourages scientists to think of ways of “falsifying” a colleague’s doubtful theory.”

Things get a bit complicated if there is a Prophet and a “believer” declares “no play.” If the Prophet says “Right,” or the Prophet says “Wrong” and Dealer says “Incorrect,” play continues as described above. However, if the Prophet says “Wrong” and Dealer says “Correct,” then the Prophet has to select what they think is a correct card from the player’s hand. If they do this right, then they deal out 5 penalty cards to the current player and play continues as normal. If they pick the wrong card from the player’s hand, they’re overthrown, and Dealer takes over again as before.

If thirty cards have been played and there’s still no Prophet, players get expelled from the round if they make a wrong play. The expelled player still receives penalty cards for the wrong play, for scoring purposes. If there is a Prophet, then expulsions are delayed for at least 20 cards after the Prophet’s marker. Pawns are used to show that expulsion is possible; if there is no Prophet then white pawns are set down every 10 cards on the layout. If there is a Prophet, black pawns are placed every tenth card following the Prophet’s marker. When a Prophet is overthrown, the black pawns are removed with the Prophet’s marker.

For scoring:
1) The greatest number of cards held by anyone is called the “high count.” Each player (including the Prophet if there is one) subtracts the number of cards still held in their hand from the high count, and the difference is their score. Players with no cards get a bonus 4 points.
2) The Prophet, if there is one, gets a bonus of the number of main line cards that follow their marker, plus twice the number of sideline cards after their marker. I.e. – one point for each correct card, and two points for each incorrect one.
3) The dealer’s score is the highest score of any player. However, if there is a Prophet, count the number of cards (right and wrong) preceding the Prophet’s marker and double this number. If the number is smaller than the highest player score, use the smaller number.

If you have time for another round, then you choose a new dealer, and hopefully everyone at the table will get their turns. However, some rounds can take several hours, so when you finish playing, add up all the scores at the end of the rounds played and give 10 points to anyone that hadn’t been a dealer as compensation.


(Full sample round, left half.)


(Full sample round, right half.)

In the above game, we have the main line and 9 side lines. White pawns are used to mark every tenth card. This was a 5-player game. Martin’s example is: “Smith was the dealer. The round ended when Jones got rid of her cards. Brown was the Prophet and ended with 9 cards. Robinson was expelled when he incorrectly played the 10 of Spades; he had 14 cards. Adams had 17 cards at the end of the game. The high count is 17. Therefore Adam’s score is 17 minus 17, or 0. Robinson’s score is 17 minus 14, or 3. Jones receives 17 minus 0, or 17, plus a 4-point bonus for having no cards, so her score is 21. Brown gets 17 minus 9, or 8, plus the Prophet’s bonus of 34 (12 main line and 11 sideline cards following his marker), making a total score of 42. This is the highest score for the round. Twice the number of cards preceding the Prophet’s marker is 50. Smith, the dealer, receives 42 because it is the smaller of the two numbers 42 and 50.”

In the addendum, Martin mentions two new games that came after Eleusis and Delphi – Sid Sackson’s Patterns, and Robert Katz’s Pensari. Also, Robert Abbott has developed some Mad Mazes (1990, Bob Adams).

A simplified version of Eleusis, called Eleusis Express can be found at logicmazes.com.

Puzzle: What is Smith’s rule in the above game?

Penrose, Turing Machine 1


For being such a simple concept, trying to write my first Turing machine turned out to be more of a challenge than I’d expected. To recap, the basic Turing machine consists of a read/write head, an infinitely long tape, and a stepper motor for moving the tape under the head one position to the left or right. The data read from the tape will then cause the machine to do something based on its current state (i.e. – it’s a “state machine”). One example algorithm hard-coded into the machine could be:

Line 1: 00 -> 00R
Line 2: 01 -> 11R
Line 3: 10 -> 01STOP
Line 4: 11 -> 11R

In words, for line 1, if the machine is in “state 0”, and a “0” is read from the tape (i.e. – “00”), set the machine to state “0” again, write a “0” to the tape, and then move the head one position to the right.
For line 2, if the machine is in “state 0” and a “1” is read from the tape (“01”), set the machine to state “1”, write a “1” to the tape, and move the head one position to the right.
For line 3, if the machine is in “state 1”, and “0” is read from the tape (“10”), set the machine back to state “0”, write a “1” to the tape, move the head one position to the right, and then STOP the machine (AKA: R.Stop).
For line 4, if the machine is in “state 1”, and “1” is read from the tape (“11”), set the machine state to “1”, write a “1” to the tape, and then advance the head one position to the right.

Syntax:
for: state & ‘bit read’ -> ‘new state’ & ‘write bit’ & direction

The above algorithm reads a string of leading 0s on the tape, essentially ignoring them. When it hits the first 1, it changes state, then keeps reading 1s. When it hits the next zero (end of number marker), the machine writes a 1 to the tape, moves the head to the right one last time, then stops. The value generated by this machine is calculated by adding up all the 1s to the left of the head. This is a “unary” number, and the algorithm simply adds 1 to the starting number on the tape. If there were six 1s on the tape when we started, there will be seven 1s to the left of the head when we finish.

“0000111111000” – Starting data string
“00001111111” – What gets printed out before the Stop.

We can have two “stop” instructions – an R.Stop and an L.Stop. They indicate which way to move the read/write head before stopping. But, because we’re reading the output from the left of the head, there’s no point to using L.Stop, and R.Stop can then be simply abbreviated to “Stop”.

I use VBscript because it’s free, and I already know how to write in it. To emulate the tape, I just use a text string. If the read/write head reaches either end of the string, I append a “0” at that end and keep running the program. I could treat the algorithm as a series of if-statements, but for the moment I prefer to use Select Case. The main reason for this is that I’ll be changing the program structure soon anyway to make a universal Turing machine. And, it’s easier to adapt hard-coded algorithms as Case statements if I want to write a new machine.

The only real inconvenience was in having to write a function for emulating the write head, for changing characters in the middle of the string. Note that the formatting below sucks because wordpress strips out excess spaces.

‘ Turing Machine 1 – Unary Add 1
‘ Penrose program: UN+1

”””””’

tapeReel = “0000000111110000”
headPos = 1
machineState = “0”
RStop = false
tapeChr = 0

wscript.echo tapeReel & ” (” & countOnes(tapeReel) & “)”

while Not RStop
tapeChr = mid(tapeReel, headPos, 1)
fullStatement = machineState & tapeChr
action = “”

Select Case FullStatement
Case “00” action = “00R”
Case “01” action = “11R”
Case “10” action = “01STOP”
Case “11” action = “11R”
Case Else wscript.echo “No instruction provided for |” & fullStatement & “|”
End Select

if(instr(action, “STOP”) > 0) then
dummy = writeToTape(headPos, mid(action, len(action) – 4, 1))
headPos = moveHead(headPos, “R”)
RStop = true
else
machineState = left(action, len(action) – 2)
dummy = writeToTape(headPos, mid(action, len(action) – 1, 1))
headPos = moveHead(headPos, right(action, 1))
end if

wend

wscript.echo “Ping: ” & left(tapeReel, headPos – 1) & ” (” & countOnes(left(tapeReel, headPos – 1)) & “)”

Since I’m treating the tape as a text string, I need some way of marking where I am in the string (headPos), and then some function for “transporting” the head one position left or right (headPos +/- 1). Finally, I have to deal with boundary conditions. That is, what happens if I’m at the left end of the string (headPos = 1) and I have to move left, or I’m at the right end (headPos = len(tapeReel)) and I have to move right. I handle this by checking the boundaries first, and adding “0” to the end of the string as necessary to “go to the next part of the infinite tape.” I should check that I’m not exceeding VBscript’s limit on string length (64K), but that’s not a real concern for what I’m doing with this program. Either way, the tape head “moves” by incrementing or decrementing headPos.

Function moveHead(hp, dir)
ret = -1
if(hp = 1 AND dir = “L”) then
tapeReel = “0” & tapeReel
ret = 1
elseif (hp = len(tapeReel) AND dir = “R”) then
tapeReel = tapeReel & “0”
ret = hp + 1
elseif (dir = “L”) then
ret = hp – 1
elseif (dir = “R”) then
ret = hp + 1
else wscript.echo “Direction ” & dir & ” not recognized.”
end if
moveHead = ret
end Function

The more piddly part was in handling the “write to tape” section. If I was using an array (or, C++ and treating the string as a character array), I’d just overwrite the old value at wherever headPos is pointing in the string. However, VBScript doesn’t work that way, and doesn’t have a built-in function for this. So, I have to break the string in two, on either side of where headPos is pointing, then recreate the string as leftPart & newValue & rightPart. Again, though, I have to worry about the boundary conditions, where I’m at one end of the string, and if using the built-in left() or right() functions will bomb in an error.
Note that I’m using writeToTape as a procedure instead of a function. Unfortunately, VBScript requires a return value at the end, so I’m just forcing it to “true” and storing it to a dummy variable in the calling routine.

Function writeToTape(wttHP, wttVal)
lstr = “”
rstr = “”
if(wttHP = 1) then
rstr = right(tapeReel, len(tapeReel) – 1)
elseif (wttHP = len(tapeReel)) then
lstr = left(tapeReel, wttHP – 1)
else
lstr = left(tapeReel, wttHP – 1)
rstr = right(tapeReel, len(tapeReel) – wttHP)
end if
tapeReel = lstr & wttVal & rstr
writeToTape = true
end Function

I wrote countOnes() as a built-in function to the Turing machine. That is, I want the machine itself to tell me how many 1s are in a given strip of the infinite tape instead of making me count them manually. This is really useful if the input number is 138 digits long.

Function countOnes(coStr)
ret = 0
for i = 1 to len(coStr)
if(mid(coStr, i, 1) = “1”) then
ret = ret + 1
end if
next
countOnes = ret
end Function

Ticktacktoe Game Theory SMBC


I would like to propose a new law. Hoffmann’s Law says that if you go through Zack Weinersmith’s Saturday Morning Breakfast Cereal archives far enough, you will find a comic on whatever topic you are currently discussing.

 

Colossal Gardner, ch. 37


Who would have thought, that after the matchbox ticktacktoe computer that there’d still be enough material in the game leftover for another, completely dedicated chapter? But, that’s what we get in the Games and Decision Theory section, with Harary’s Generalized Ticktacktoe. Turns out that a much older variant of ticktacktoe used a 3×3 board and three counters each for the two players. The players took turns putting their stones on the board, and then moved the stones from cell to cell until one player got them in a straight line. According to Martin, “moving counter ticktacktoe is the basis for a number of modern commercial games, such as John Scarne’s Teeko, and a game called Touche.” He goes on to say that ticktacktoe can be generalized to larger fields, such as with Gomoku, or to play it on three or more boards for 3-, or higher, dimensions.

In 1977, Frank Harary (1921-2005), then mathematician at the University of Michigan, found a way to generalize ticktacktoe. He was known as “Mr. Graph Theory”, founder of the Journal of Combinatorial Theory and Journal of Graph Theory (yes, mentioned in the chapter on Ramsey Theory) and the author of the definitive book, Graph Theory. He wrote over 500 papers on the subject. Originally, Martin called the game Harary ticktacktoe, but Frank requested it to be named “animal ticktacktoe.” To start with, we can look at standard ticktacktoe as a two-color graph game, an “achievement game.” Use dots for the 9 cells, and connect them with lines as shown. You still have the two players, but they are each assigned a color, and they take turns coloring the points on the graph. First one to color a straight line of 3 points wins.


(All rights belong to their owners. Images used here for review purposes only. Graph theory approach to ticktacktoe.)

Now ask the question, “What’s the smallest square on which the first player can force a win by coloring a straight (non-diagonal) three-point path?” Answer, a square of two sides. Harary called this the board number, b, of the game, and it’s related to the Ramsey number in graph theory. After getting the board number, b, we can then ask, “In how few moves can the first player win?” Answer (try drawing this out yourself): three moves. This is the move number of the game, m. According to Gardner, “a player wins in standard ticktacktoe by taking cells that form a straight, order-3 polymino that is either edge- or corner-connected.” Below are the polyminoes of orders 1 through 4. Solomon Golomb developed the polymino terminology, but Harary preferred the usage of some of the earlier papers, and called them “animals.”


(Animal polyminoes of orders 1 through 4.)

Now comes Harary’s generalization: Pick an animal of any number of square cells (the order) and say that forming that animal is the goal of a ticktacktoe-like game. You don’t have to color the dots and lines shown above; using x’s and o’s is fine, or you can color the cells red and blue as you’d color the edges of a Ramsey graph game. The animal can be in any rotation or mirror image. Ok, now how we get the animal’s board number, or the length of the smallest square for which the first player can force a win? If the board number exists, that animal is considered to be a “winner,” if not, it’s a “loser.” If the animal IS a loser, the second player can force a draw, but can not win. Next, we want the value for m. If you have a one-cell animal, b and m are both 1. When b and m are the same value, the game is called “economical,” because the first player doesn’t have to waste a move to win it. For the domino, the only 2-cell animal, b and m are both 2. For the two 3-celled animals, the El is economical, and b = m = 3; the tic has b = 4 and m = 3, but this is for games that don’t allow diagonal lines.


(Order 5 polyminoes, grouped by winners and losers.)

The below illustration includes the proof that the Fatty of order 4 is a “loser” (games played rationally always result in a draw.) If you have the tiling at the top left, the first player first needs to draw a domino. To prevent this, the second player just has to take the other cell of the domino. If the first player can’t make a domino, they’ll never be able to draw a fatty, either. The rest of the illustrations show the other loser animals. Gardner adds that the proof that the straight 5-cell animal is a loser also bears on the game of Gomoku. On a 5-cell board, you want to draw a straight line. But, the second player can always force a draw if diagonals are not allowed. If diagonals ARE allowed, the first player can usually win.


(Visual proof that the fatty is a loser (second player can force a draw).)

Martin spends about a page talking about higher order animals, and then says that these variants can be fun ways to pass the time, if one or both players don’t know how to force the win. If you do try to select animals and then draw them ticktacktoe-like, it’s best to use a board that is b-1 (which is the smallest Ramsey graph where player 1 can’t force a win). You can also try misere versions, where the first player to draw the animal loses. These are “avoidance” games, and are actually harder to analyze. Martin spends some time giving examples. He also says that you can take the 2D forms and make them 3D or higher, as with polycubes or hypercubes.

In the addendum, Martin makes the statement, “if the first player always wins on a board of a certain size, he also wins on any larger board.” However, this is only true for square boards, not arbitrary graphs. The below graph was developed by A. K. Austin and C. J. Knight, mathematicians at the University of Sheffield, in England. On the left is a graph where 3-in-a-row wins. The first player wins by taking A. The second player has a choice of taking a point in either the larger or smaller triangle. No matter what B chooses, A counters by picking a corner in the other triangle. Player B has to block the threatened win, and A wins by taking the remaining corner of the same triangle. Ok, so expand the board by adding the two points shown on the right side below. The second player can get a draw by playing at B. If player one doesn’t start at A, player two can force the draw by taking A themselves.

No puzzles this week. Just a challenge to try playing these variants of the game yourself.

Penrose, Initial Comments (Part 1)


(All rights belong to their owners. Images used here for review purposes only.)

The third book I asked for as a Christmas present was Roger Penrose’s “The Emperor’s New Mind” (ENM). After seeing Penrose’s name show up so often in the Gardner book, and in reference to Penrose tiling, I figured I might as well see what he’s written himself. As I was surfing Amazon, I noticed that a lot of the customer comments on his books were that he’s very dense and difficult to understand as a writer and mathematician unless you’re at the grad student level. That seemed like an interesting challenge, and I finally settled on ENM because I did at one point want to write an SF novel involving AI.

Douglas Hofstadter’s book, “Godel, Escher, Bach,” (GEB) came out in 1979, and it placed him firmly in the “strong AI” camp (i.e. – as a proponent of the argument that we could eventually get computers that think like humans. Douglas has since moved on from that level of research into other things.) Penrose’s position is that there are various reasons why strong AI is impossible, and ENM (1989) was his first foray into explaining why. It generated a strong backlash from the strong AI people, including Marvin Minski, which resulted in two follow-up books: Shadows of the Mind (1996) and The Large, the Small and the Human Mind (2000). ENM was reprinted by Oxford University Press in 2016. One of the more controversial ideas is that quantum mechanics is involved in the human thought process, which doesn’t have much of a following yet.

Roger Penrose (Aug. 8, 1931 -) created the idea of the tribar, a 3D triangle with a twist at one end that turns it into an impossible object (kind of like a Mobius strip). He and his father (psychiatrist and mathematician Lionel) turned the idea into the “impossible staircase,” which M.C. Escher used for “Waterfall” and “Ascending and Descending.” Roger is an English mathematical physicist, mathematician and philosopher of science, Emeritus Rouse Ball Professor of Mathematics in the University of Oxford, and Emeritus Fellow of Wadham College, Oxford. He won the 1988 Wolf Prize for physics along with Stephen Hawking for their contributions to cosmology. So, he knows some stuff.

The problem with reviewing any science or math book written so long ago is that the material is going to be out of date, and you have to look at it strictly from the point of view of when it came out. So, naturally ENM is going to not have anything on strings or m-branes, and the quantum physics may be incomplete as we know it now. But, that’s kind of immaterial when looking at the history of AI research. Plus, there’s a lot on the historical side that’s still relevant and fun to learn about. I’m only 60 pages in, and the book is a full 440 pages. Right now, I’m on the chapter for the Turing machine, which is why I started writing this blog entry.

First, Roger talks about algorithms – what they are and how they’re used – and he gives Euclid’s process for finding the greatest common divisor as one of the earliest known algorithms. The process is simple (although I’d never seen this one before, which is why I like it). Take two numbers, call them x and y. Let z = abs(x – y). Then replace the largest of x and y with z. Repeat until x = y (if you go a couple more steps, both x and y go to 0) and then you have your GCD.

x = 144, y = 54, z = 90
x = 90,  y = 54, z = 36
x = 36,  y = 54, z = 18
x = 36,  y = 18, z = 18
x = 18,  y = 18, z =  0

It’s really easy to write this in vbscript, although you have to write your own functions for min() and max().

‘ Euclid’s Greatest Common Divisor algorithm

wscript.echo “Euclid’s GCD: ” & cstr(euclidGCD(144, 54))

function euclidGCD(x, y)
while (x <> y)
z = abs(x – y)
x = min(x, y)
y = z
wend
euclidGCD = x
end Function

function min(x, y)
ret = x
if (y < x) then
ret = y
end if
min = ret
end Function

The reason, though, for Roger to offer this algorithm is that he intends to implement it as a Turing machine. I’ve seen mentions of Turing machines before, but they never had examples of runnable code. And, for some reason, the computer science class pages I found on the net while preparing for this blog entry don’t seem to agree on why Alan Turing came up with his machine in the first place, which is why I like Penrose’s explanation. According to Roger, Turing wanted to work on a challenge first proposed by mathematician David Hilbert in 1901. Hilbert wanted to know if there was a purely mechanical, deterministic way to find all possible math theorems.

To do this, Turing proposed a simple machine. This machine would consist of a read-write head, infinite tape, and the ability to move the tape one position left or right. The tape would start with some string of 1’s and 0’s. This machine, called a “state machine,” would read the number on the tape directly under the head, and then make a decision for what to do next based on its current state. The starting state is “0”. For example, for state 0, if the number read is “0”, then write 0 back to the tape, keep the state at “0”, and move the tape one position to the right. If the number is “1”, write 0 to the tape, change the state to “2”, and move the tape one position to the right. and keep doing this until reaching a stopping condition.

There are a lot of issues to resolve before the machine can do anything useful, such as how to represent numerical values, and how to separate numbers. Since all we have are 1’s and 0’s, the easy way to represent numbers is as unary values – just a long string of 1’s, separated by a 0. 5 = five 1’s in a row; 100 = one hundred 1’s in a row. This makes for a long, slow program, but the tape is infinitely long, so we can hold any data we want. Alternatively, we can go binary, and use key values to represent separators, and other operators (that comes later).

Roger provides programs for adding 1 to a unary number, and for performing unary math to find Euclid’s greatest common divisor. He also has the binary algorithms for GCD and multiplying two binary numbers. And this is one reason I really like this book, so far – usable code.

Now, one point. At least one of the states is going to have a Stop instruction, and we can build the machine so that it pings, or gives some other indication that it’s hit the Stop. Then, to find out what the answer is from the machine, we read the number to the left of the head (by convention). This means that until we get the ping, the machine’s not done and the answer isn’t ready yet. One implication of this is that when people suggest using a Turing machine for calculating PI, e, or 1/3, we’re never going to get output out. These are infinitely long numbers, and there’s no “final” digit to output, so the machine never stops and we never get that ‘ping.’ On the other hand, we could rig the machine to pause when the next digit is calculated and to ping then. After reading the new digit, we could press the “continue” button and the machine would do the next set of calculations. But, there’d still never be a “final” digit for PI.

This then gets us to the halting problem. It’s easy to write a bad algorithm that never stops. But, how can we tell, from the outside, that the machine isn’t simply working on a really big number, or is in the middle of a really deep loop? In fact, this is kind of like working on the Mandelbrot fractal set; certain data points can generate incredibly small complex numbers without actually reaching zero. We can put a counter on the number of times we do the calculation and break out of the loop after 50 iterations, 100, 1,000, etc., but that’s a conscious decision we have to make in advance, and it’s completely arbitrary. With a Turing machine, reaching loop count = 1e^100 could either be because it entered an infinite loop, or simply because it’s not done generating the answer yet. From the outside, we can’t tell. And that’s the halting problem in a nutshell – is there a way to tell if any arbitrary algorithm will halt, or not, for any randomly selected range of input data (the algorithm for calculating the final digit of PI will never halt). If you know the answer, the Clay Mathematics Institute would like to talk to you.

Answer Sprouts


Puzzle: Why is Brussels Sprouts a joke?

Because the game must end in exactly 5n – 2 moves.
In standard form, the first player wins for an even number of starting crosses, the second player for an odd number. In misere play, it’s the opposite. If you introduce a beginner to Sprouts, you can then try talking them into betting money on the outcomes of Brussels Sprouts games.