(Stopping counts, from 1 to 5,000)

I was reading through the xkcd.com archives, and I found this one strip about the Collatz Conjecture. I’d never heard of this before, so I decided to whip together a quick and dirty (QnD) VBScript to generate the stopping counts for values 1 through 5,000 (actually, I went up to 100,000, but I didn’t like the way the plots came out) and threw the results into Excel to see what the scatter plots looked like. That was fun.

(Just the odd values of n)

(Just the even values of n)

‘ Collatz Conjecture
‘
””””””””””””

maxVal = 1

for i = 1 to 5000
x   = i
cnt = 0
while x <> 1
cnt = cnt + 1
if(x mod 2 = 0) then
x = x / 2
else
x = (x * 3) + 1
end if
wend
wscript.echo cstr(cnt)
next

(Ln() version of the graph)

It didn’t really prove anything, but it did lead me to develop the Inverse Collatz Conjecture:
Starting with 1, any number can be generated by rationally using a combination of just two operations: multiply by 2, and subtract 1 then divide by 3.

This is what got me started.

I mentioned the Monty Hall problem in Colossal Gardner, ch. 21, in the chapter on Probability and Ambiguity. I like Zach’s version that introduces the Trolley ethics conundrum.

Monty Hall Problem

But now, we learn what’s really behind these kinds of conundrums.

Math Goblins

We start out the section on Logic and Philosophy with The Unexpected Hanging. This chapter is an exploration into the pitfalls and hazards of addressing logic problems face on. The original paradox circulated by word of mouth in the early 1940’s, then appeared in print in an article in the July 1951 issue of the British philosophical journal, Mind, written by Michael Scriven. It usually took the form of a prisoner scheduled for hanging. The sentence was handed out on Saturday, with the judge saying, “The hanging will take place at noon on one of the seven days of the next week. But you will not know which day it is until you are so informed on the morning of the day of the hanging.” The judge was a man of his word, so when the condemned and his lawyer returned to the prisoner’s cell, the lawyer broke into a grin and exclaimed that the sentence can’t possibly be carried out.

He continued, “They can’t hang you next Saturday, because it’s the last day of the week. By Friday, you would still be alive and you’d know that the actual date would have to be Saturday, so if the judge keeps his word and you’re not going to know before Saturday morning, then Saturday’s out. This leaves Friday, but by extension, since they can’t hang you on Saturday, that by Thursday noon you’d know that the hanging would have to be on Friday, Friday is out, too.” The prisoner gets excited, and says, “I think I understand! By the same logic, they can’t hang me on Wednesday, Tuesday or Monday, either. That just leave tomorrow, and I now know that it can only be tomorrow, and therefore I can’t be hanged then, either!”

Gardner states that the judge’s statement appears to be self-refuting. There’s nothing logically contradictory between the two sentences, but in practice it can’t be carried out. Donald John O’Connor, a philosopher at the University of Exeter, the first person to discuss this paradox in print (Mind, July 1948), had a different version where the military released plans to have a Class A blackout some time in the next week. A “Class A blackout” is one “the participants could not know would take place until 6 P.M. on the day it was to occur.” This statement produces the same results as Scriven’s variant. Jonathan Cohen (Mind, Jan. 1950), Peter Alexander (Mind, Oct. 1950) and George Gamow and Marvin Stern (Puzzle Math, Viking Press, 1958) all viewed these events (the hanging and the blackout) as not being possible because they would violate the definitions of the situation.

However, Scriven thought that this is not a frivolous case, “for a reason that completely escaped” the other authors. So, there the prisoner is, sitting in his cell on Thursday, when the hangman shows up. He’s surprised because he wasn’t expecting the hangman, and therefore the judge’s statement is shown to be true after all. “I think this flavour of logic refuted by the world makes the paradox rather fascinating,” Scriven wrote. “The Logician goes pathologically through the motions that have always worked the spell before, but somehow the monster, Reality, has missed the point and advances still.”

Martin gives two more examples. In the first, your friend has ten boxes on a table, and an egg. They tell you to turn around while they put the egg in one of the boxes. You do so, then turn back. The friend tells you to open the boxes in serial order, one at a time, and you’ll be surprised when you open one of the boxes and find the egg. In the second case, your friend is sitting at a table, holding the 13 Spade cards from a playing deck. They shuffle the cards and deal one face down. You’re told to slowly name the cards one at a time, starting from the Ace and ending with the King. If the name you announce is not that of the face-down card, they will say “No.” If it is the right card, they’ll say “Yes.” Then, they offer to bet $1,000 to 10 cents that you will not be able to figure out what the face-down card is before they say “Yes.” In both cases, the logic is exactly the same, as are the results. When you find the box with the egg in it, you’ll be surprised. And, no matter how hard you stare at the back of the card, you’ll never be able to tell which one it is.

Even in the simplified cases of the hanging being in two days, there being 2 boxes for the egg, or your friend only choosing between two cards, there’s a problem. In the two card case, say your friend claims to be holding the Ace and deuce of Spades, and continues to bet $1,000 that you won’t know which card it is before they say “Yes.” They put one card on the table, you say “Ace of Spades,” and they say, “No.” According to the rules of the game, you now know that the face down card is the 2, and you’re guaranteed to win the $1,000. But, you ask yourself “is my friend that willing to give up $1,000 on a bet like this?” If that answer is, “No, they’re not,” then the face down card can’t be the Deuce. But, your friend had said that the only cards are the Ace and the Deuce, so it has to be one or the other, and they’re pretty sure that you can’t guess the card before they say “Yes.” Which brings us to the assumption that is at the heart of the paradox – that we can trust the person making the statement. Everything hinges on our believing that they’re not lying. If they have no logical basis for picking one card over the other, then your decision to pick the Deuce of Spades becomes more shaky.

All of this brings us to English mathematician P.E.B. Jourdain’s paradox card, first presented in 1913 – on the front of the card is, “The sentence on the other side of this card is true.” And on the back is, “The sentence on the other side of this card is false.” So, you may guess correctly which card your friend put on the table, but you will be completely unable to use iron-clad logic to make it a deduction.

Scottish mathematician Thomas O’Beirne wrote in Can the Unexpected Never Happen?, (The New Scientist, May 25, 1961)  “the key to resolving the paradox lies in recognizing that a statement about a future event can be known to be a true prediction by one person but not known to be true by another until after the event. It is easy to think of simple examples. Someone hands you a box and says: “Open it and you will find an egg inside.” He knows that his prediction is sound, but you do not know it until you open the box.”

In the addendum, Martin says that Kurt Godel mentioned a variant of the hanging prisoner paradox in a lecture in 1947, and Douglas Hofstadter (author of Godel, Escher, Bach) suggested that instead of the unexpected egg in a box, that it be an unexpected deadly snake. A full bibliography of papers on this subject can be generated at the page of Timothy Chow.

Challenge for this week:
“What you do not smell is called iocane powder.”
Complete the test.

I mentioned before that I’d asked for Roger Penrose’s “The Emperor’s New Mind” (ENM) as a Christmas present after seeing Penrose’s name show up so often in the Gardner book, and in reference to Penrose tiling. Many of the Amazon 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’d settled on ENM because I did at one point want to write an SF novel involving AI.

The Emperor’s New Mind (1989) was written as a rebuttal to the (at the time) prevalent belief in A.I. research that computers could be made to think if you understood how to write the right code. Douglas Hofstadter’s book, “Godel, Escher, Bach,” (GEB) came out in 1979, and it placed him firmly in the “strong A.I.” camp, as it became to be called. Penrose’s position is that there are various reasons why strong A.I. is impossible, and ENM (1989) was his first foray into explaining why. It generated a strong backlash from the strong A.I. people, including Marvin Minsky, which resulted in Penrose writing 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. As of right now, the definition of A.I. has evolved away from what Penrose was responding to, and his theories of how quantum mechanics relates to how the human brain works, and its role in the formation of “consciousness” has not been well received.

Repeating part of my first post: 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.

Again, 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 is incomplete as we know it now. But, that’s kind of immaterial when looking at the history of A.I. research. Plus, there’s a lot on the historical side that’s still relevant and fun to learn about.

Trying to summarize the main point of the book is a bit tricky. Roger’s contention in ENM is that proponents of strong A.I. believe that an algorithm (or program) can be formulated that will allow a machine to emulate human consciousness, and he then proceeds to try to set up a series of definitions for how computers work, how the human brain works, the differences between deterministic and computable, what a mathematical representation of “truth” is, how Godel’s Incompleteness Theorem complicates the search for mathematical “truth,” what consciousness is and where it can be found in the human brain, and what the roles of physics and quantum mechanics are in all this. It’s all very lofty.

I like the chapter on Turing machines, and it contains enough examples of working algorithms to make me very happy (as already covered in the previous blog VBScript entries). This chapter alone justifies the book. The real bulk of the book, though, concerns itself with classical Newtonian physics, the Theory of General Relativity, how the attempts to understand black holes led to a rethinking of the math for gravity, and the way quantum mechanics can lead to a theory of quantum gravity. While Penrose’s goal is to show that a deterministic machine approach is doomed to fail to recreate human consciousness, he spends much less time talking about how the brain works, and what consciousness “is” than he does on quantum mechanics.

Really, ENM works much better as an introductory primer to quantum mechanics than it does as a rebuttal of strong A.I. Roger is guilty of a lot of hand waving in defining consciousness, and the fact that his statements often start with “strong A.I. adherents seem to think” kind of undermines his point. He’s not so much rebutting the ability of computers to emulate human thought processes, as he is confronting something that he thinks the computer scientists think they can do. I may try reading his other two books on the subject at some point to see if he ends up strengthening his arguments over time.

But, he’s on much steadier ground when he keeps to what he does know. His discussions of Turing machines are solid. On the physics side, he starts out talking about how classical mechanics worked up to Newton, and then how the theory of gravity developed after Newton. We get Maxwell’s wave equations, the two-slit photon experiments, and how Einstein came up with both his Special and General Theories of Relativity. Additionally, Roger gets into quantum mechanics, entropy, and probability wave functions. He writes about the implications of both the Heisenberg Uncertainty Principle and Schrodinger’s equations in a much better and more comprehensible manner than I’ve encountered before. He continues with black holes, Hawking radiation and the Big Bang, again in a way I like much better than what other writers I’ve read had done. When he finally reaches quantum gravity, he gets much more speculative, but does give a nod to string theory and other at-the-time emerging concepts.

One impression I take away from this book is that Heisenberg’s Uncertainty Principle, and the entire Schrodinger’s cat experiment have been largely mistaught in American schools. It’s not so much that we’re trying to predict the outcome of chaotic systems where we don’t have a full accounting of what every single particle is doing, as it is that quantum theory treats wave states as energy distributions across a probability curve. That is, in a way, the probability of a specific outcome of an event represents the amount of energy in the system associated with that event. It’s NOT like the probability of a rolling ball falling into a specific slot on a roulette wheel – in this case, we assign probabilities for where the ball will stop, and when it does stop, the probability becomes 100%. Although, that is how I saw it, before reading ENM.

I don’t really buy Roger’s argument that human-like consciousness is non-computable, and must strictly be “by definition” algorithmic. We’ve gotten a lot better at facial and voice recognition, data mining, and other subjects that were supposedly things computers couldn’t do as well as humans. Machine translation is getting good enough that many professional translators are at least wondering if they should start looking for new work. Give everything a few more years, and the “singularity” may finally be within sight.

But, for me, the real value in this book is in the way it leads up through quantum mechanics, and attempts to describe what a theory of quantum gravity could be. It makes me wish a book like this had existed when I was still in university (’80-’83). Now, I’m curious just how much ENM has been updated for the 2016 reprint.

The section on Physics ends with Simplicity. Martin states “The concept of “simplicity,” in both science and mathematics, raises a host of deep, complicated, still unanswered questions. Are the basic laws of nature few in number, or many, or perhaps infinite, as Stanislaw Ulam and many others believe? Are the laws themselves simple or complex? Exactly what do we mean when we say one law or mathematical theorem is simpler than another? Is there any objective way to measure the simplicity of a law or a theory or a theorem?”

(All rights belong to their owners. Images used here for review purposes only. Finding a best fit curve.)

The rest of the chapter is then a tug of war between complexity (as seen in the behavior of the human brain by neurologists, and in the particles of quantum physics) and simplicity (as in the quest for a Grand Unified Theory, and statistics). In the above graph, we have potential data from a physics experiment. (b) represents one possible curve for those points, but the more likely function is (c).

This raises the questions: can simplicity be defined, and if so, can it be measured? Generally, scientists scoff at both questions, but if you have two competing theories, both of which may be right or wrong, and it costs $1 million to test each one, finding a way to determine their simplicity could help in deciding which theory to test first.

(Theoremizoring on quadrilaterals.)

Martin then talks about how the math equivalent to a law or theory is in the search for theorems. The mathematician makes empirical tests. One example is above, doodling with complex quadrilaterals. She may find that when drawing the squares outwards and connecting the centers to the opposite  squares, that the two lines are equal and intersect at 90 degrees. Trying again with different quadrilaterals, she gets the same results, and senses a theorem. She picks a hypothesis and keeps it simple (not that the lines have a ratio of 1 to 1.00007 and intersect with angles between 89 and 91 degrees), testing the simpler guess that the lines are always perpendicular and equal. (Known as Von Aubel’s theorem.)

(Cutting up circles.)

Martin ends with combinatorial theory, where the simplest guess is usually the best choice, but says that there are exceptions. This week’s problem was discovered by Leo Moser. “Two or more spots are placed anywhere on a circle’s circumference. Every pair is joined by a straight line. Given n spots, what is the maximum number of regions into which the circle can be divided? The above figure shows the answers for 2, 3 and 4 spots. Find the answers for 5 and 6 spots, and if possible, the general formula.”

As I’ve left the code standing so far, even the most simple Turing machine that actually does something useful is going to be assigned really big numbers, meaning running from 0 to the first working machine is going to take a long time. To get around that, Penrose suggests trimming some of the fat from the algorithms first.

Consider xn_times_2.txt:
00->00R
01->11R
10->00R
11->101L
100->00STOP
101->110R
110->101R
111->111R

As mentioned before, we strip out the numbers to the left of the arrow, and just rebuild that up in the Turing machine when we load the program. This is why the state numbers are in binary, and are paired with the 1s and 0s we read from the tape. It does mean, though, that we can’t have any missing state+bit read combinations. If there is a state+bit read combination not used in the algorithm, represent it with the dummy line “00R”. Also, strip out the arrows. And, don’t use commas to separate each line. Instead, we use “L”, “R” and “STOP” to mark the end of each statement.

00R
11R
00R
101L
00STOP
110R
101R
111R

Next, we can treat state “0” and read bit “0” (“00”) as “”. And treat state “0” and read bit “1” (“01”) as “1”. Also, the very first line, 00R is required in every algorithm to shift past leading 0 padding before reaching the start of data. We can cut the first line, and just automatically force it in the boot loader when we load the algorithm into the machine. That gives us:

11R
R
101L
STOP
110R
101R
111R

Notice that we tend to have more Rs than Ls, so in the binary coding, list R first.

0 = 0
1 = 10
R = 110
L = 1110
STOP = 11110

Substituting the expanded binary values;

1010110
110
100101110
11110
10100110
10010110
101010110

Finally, notice that R, L and STOP all end with the same last 3 digits. So, no matter what the last character is at the end of the last line, the last three digits will be 110. We can trim that off the end of the string, and append it again in the loader.

1010110
110
100101110
11110
10100110
10010110
101010

Make this all one line:
1010110110100101110111101010011010010110101010

The decimal value is now 47731979167146, which is a LOT smaller than the original 6.0109e16 we started with. This entire process can easily be automated, essentially as an “assembly language” compiler that creates “machine code.” The boot loader in the universal Turing machine would just reverse the process (see below).

Technically, Penrose indicates that there’s no need for an “end of program” marker, but I don’t see any way around it (see below). I’m using EOP = 111110. With this in place then, the binary representation of the algorithm and the data can easily coexist in the same textfile. Just read in everything to the boot loader as one long string, interpret the algorithm, and auto launch it when you’re done.

As one last note, Roger talks about the first few Turing machines you get for the numbers 0 to 13. Remembering the interpretation steps,

0 = 00->00R
1 = 00->00R, 01->01R
2 = 00->00R, 01->10R
…

These are not particularly well-formed, but they will run (and never, ever stop…)

Ok, changes to my VBScript. I know this is going to look ugly, and that I should add more comments to explain what’s going on, but WordPress screws up all the formatting anyway, and if anyone does have questions, you can always ask in the comments.

The contents of “universal.txt” are:
1010110110100101110111101010011010010110101010 ‘ compressed xn_times_2
111110 ‘ EOP
00000101010000101100000 ‘ The data: 113, plus 0 padding

First, in the main body of the script, I added an algoRaw() array to hold the full reconstructed algorithm, line-per-line. Then I make a call to readFile(“universal.txt”) (universal.txt contains the binary-encoded version of xn_times_2 plus the data). This loads algoRaw() with the same content as you can find in xn_times_2.txt in a previous blog entry. readFile() also returns the data portion of the binary-encoded string, which I save to tapeReel. I changed readAlgorithm() to procAlgorithm(), and stripped out the file handling code from that. Otherwise, the main body doesn’t change at all.

——
dim algo(100, 4), algoRaw(100)
algoMax = 0
algoRawMax = 1

tapeReel = readFile(“universal.txt”)
dummy = procAlgorithm()
——

procAlgorithm() originally opened up the desired file, read the algorithm, and parsed it into the algo() array. Since I’ve moved the file handling part into readFile(), all I had to change in this function was in getting the algorithm statements from the algoRaw() array. Everything else is the same.

Function procAlgorithm()
while(algoMax < algoRawMax)
str = algoRaw(algoMax)
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) – 4, 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

procAlgorithm = true
end Function

Ok, this is the new part, and is really ugly. I know this. But it works. Plus, it works in reconstructing the xn_times_2 algorithm exactly as described above. If you have difficulty figuring out what’s going on, reread the section on making the algorithm smaller by removing the fat. In readFile(), I’m just putting all the fat back in from where it came.

Function readFile(rAFN)
set fso = CreateObject(“Scripting.FileSystemObject”)
fIn = “D:\penrose\” & rAFN
wscript.echo “Reading file: ” & fIn
Set inData = fso.OpenTextFile(fIn, ForReading, True)
rFStr = “”
rFtemp = “”
rFBuild = “”

while(not inData.AtEndOfStream)
rFStr = rFStr & inData.readline
wend

inData.close

algoRaw(0) =”00-00R”
notEOP = true

while(notEOP)
rFChr = left(rFStr, 1)
rFStr = right(rFStr, len(rFStr) – 1)
rFTemp = rFTemp & rFChr

if(rFChr = “0”) then
if(strcomp(rFTemp, “111110”) = 0) then
notEOP = false
rFTemp = left(rFTemp, len(rFTemp) -6) & “110”
end if

rFToken = “”
rfEOL = false
if(strcomp(rFTemp, “0”) = 0) then
rFtoken = “0”
elseif(strcomp(rFTemp, “10”) = 0) then
rFtoken = “1”
elseif(strcomp(rFTemp, “110”) = 0) then
rFtoken = “R”
rFEOL = true
elseif(strcomp(rFTemp, “1110”) = 0) then
rFtoken = “L”
rFEOL = true
elseif(strcomp(rFTemp, “11110”) = 0) then
rFtoken = “STOP”
rFEOL = true
else
notEOP = false
wscript.echo “Problem with token : |” & rFTemp & “|”
end if

rFTemp = “”
rFBuild = rFBuild & rFToken
if(rFEOL) then
if((rFToken = “R” OR rFToken = “L”) and len(rFBuild) < 3) then
rFBuild = right(“000” & rFBuild, 3)
elseif(strComp(rFToken, “STOP”) = 0 and len(rFBuild) < 6) then
rFBuild = right(“000” & rFBuild, 6)
end if

rFNo = cstr(DecimalToBinary(algoRawMax))
if(len(rFNo) < 2) then
rFNo = “0” & rFNo
end if
algoRaw(algoRawMax) = rFNo & “-” & rFBuild
rFBuild = “”
algoRawMax = algoRawMax + 1
end if
end if
wend
readFile = rFStr
end Function

Finally, to convert the decimal line counter into the binary combination of “state” + “read bit” part that appears at the left of the “->” arrow, I needed the other half of the converter I found at the National Instruments forums.

Function DecimalToBinary(DecimalNum)
Dim tmp
Dim n

n = DecimalNum

tmp = Trim(cStr(n Mod 2))
n = n \ 2

Do While n <> 0
tmp = Trim(cStr(n Mod 2)) & tmp
n = n \ 2
Loop

DecimalToBinary = tmp
End Function

As a recap, universal.txt contains:
101011011010010111011110101001101001011010101011111000000010101000010110000

The reconstructed algorithm is:
00-00R
01-11R
10-00R
11-101L
100-00STOP
101-110R
110-101R
111-111R

And the program output for multiplying a number by 2 is:
Starting With 00000010101000010110000 = (1110001,)
Decimal = 113
Ping: Answer is: 000000101010000100110 (00000011100010,)
Decimal = 226

And, that’s a wrap for Turing Machines.

—

Actually, the thing about the end of program (EOP) marker. In compressing the algorithms down, we cut out the current state + bit read data to the left of the arrow, and the arrow itself. Then, we eliminate the first line, which is always 0->00R. Plus, we cut the leading zeroes for new state + write byte, like so:

0->00R
1->10R
10->11R
11->00STOP

Becomes

10R
11R
STOP

Represented as: 100110101011011110

Note that the lines always end with R, L or STOP, and they always start with a 1.
So, technically, if the algorithm is followed by 0s before we get to the data, we could simply say that if an R, L or STOP (110, 1110, 11110) is followed by another 0, that we’ve hit the end of the program and are now getting into the data.

Unfortunately, in order to shave off three more bits, we cut 110 off the right end, giving us:

100110101011011 + 000…

If we look at the lines

11R (1010110)
11L (10101110)
00STOP (11110)

Slicing 110 from the right of 11R and 11L , and appending data gives us:

1010 + 0000… = 1100000
10101 + 0000… = 1110000

Both of these could be mistaken for really long New State values, and the boot loader wouldn’t know where to stop loading.

Slicing 110 from STOP, plus data, gives

11 + 000000 = R00000

Assuming that R followed by a 0 is illegal, we COULD say, “this is the end of the program,” tack 110 back on to the 11 to get 11110000, and we’d be fine. But, this trick only works if STOP is the very last command in the algorithm, and that’s actually kind of rare.

It’s just easier to treat 111110 = EOP as an “algorithm/data” separator, and not include it when calculating the Turing machine number.

Puzzle:
A statistician eats at a restaurant that offers apple pie and cherry pie. He/she rates their satisfaction with each kind of pie with values 1 through 6. The apple pie is uniformly a 3 (spinner 1), and the cherry pie varies from night to night as based on spinner 3. From that point on, the statistician always picks the apple pie. The restaurant occasionally offers a blueberry pie (spinner 2). Which pie does he/she order that night?

The statistician is attempting to maximize their “best chance” of getting the most satisfying pie.

The conversation might go:
“W: Which pie will be better tonight, A or B?
S: The odds are on A.
W: What about A and C?
S: Again, A will probably win.
W: I see, you mean A will probably be the best of all.
S: No, actually C has the greatest chance of being the best.
W: Ok, cut the funny stuff. Which pie to you want to order, A or C?
S: Neither, I’ll take a slice of B please.”

——

I have recently gone through the full archives of both Saturday Morning Breakfast Cereal (GoComics incarnation) and xkcd. They’re both good if you like science and/or math, or/and if you don’t. Along the way, I found comics from one, the other and/or both sites that relate to subjects that I’ve written about here on this blog. So there. phttttht.

This wouldn’t work on me, because I always bring my own water.

Euthanize Mathematicians

Martin Gardner Puzzle

Induction and Probability revolves around how science works. You see events unfolding under various conditions, and you try to determine the rules for those events from the inside. If your rules fail to predict a related event, or the same event under new conditions, you have to tweak your rules. This is inductive reasoning. Most of Gardner’s commentary is on highlighting the thoughts of philosophers like John Stewart Mill, Bertrand Russell, R. B. Braithwaite, Max Black, Hans Reichenbach and Rudolf Carnap.

In Hempel’s raven paradox, we have 100 playing cards, some of which have pictures of ravens drawn on the back. If we say “all raven cards are black,” then as we turn over the shuffled cards, the more black raven cards we get, the more the hypothesis gets confirmed. After all 100 cards, the hypothesis may or may not be shown to be true. But if we say the functionally same thing as, “all non-black cards are not ravens,” then we’re looking for any card that is not black that is not a raven. After 100 cards, maybe this new hypothesis also gets confirmed. So far, so good. Then we move to the real world, and things get a lot more messy. We find a yellow object that turns out to be a canary. Does this confirm either “all ravens are black” or “all non-black objects are not ravens”? If it does, in a weak sense, then really all we can be sure of is that ravens are not yellow (they could still be white or any color other than yellow). The point is that induction is not a rigorous proof.

A confirmation could weaken a hypothesis or even falsify it. Say you have a deck of cards, and declare, “no card has green spots.” The first 10 cards are ordinary playing cards, but number 11 has blue spots. The hypothesis still holds, but your grounds for believing it gets shakier (if blue is a valid color, why isn’t green?) Or, you have ten cards with values ace through ten, shuffled and dealt face down. The guess is that no card with value n is in the nth position from the left. You turn over the first 9 cards, which proves the hypothesis. But if the 10 card hasn’t been turned over yet, the first nine cards taken together negate the hypothesis.

(All rights belong to their owners. Images used here for review purposes only. E. H. Simpson’s reversal paradox.)

The following problem was named Simpson’s paradox by Colin R. Blyth, who found it in a 1951 paper written by E. H. Simpson, but it’s actually older than that. Taking 41 poker chips and four hats, put 5 colored and 6 white chips in the first black hat, and 3 colored and 4 white chips in the gray hat beside it. On a second table, there is also a black and a gray hat. The black hat has 6 colored and 5 white chips, and the gray hat has 9 colored and 5 white chips. Going to table A, you want to pull out a colored chip – which hat should you try? The black hat has 5/11 odds and the gray hat has 3/7 odds. The best bet is to take the chip from the black hat. The black hat on table B is also your best choice (2/3 versus 9/14). Ok, fine. Now, combine all the chips in the black hats on tables A and B into the black hat on table C, and the same for the chips in the gray hats into the gray hat on table C. You might think that the black hat on table C is still the best choice, except the total probabilities are now 11/20 for the black hat and 12/21 for the gray hat – gray wins 0.57 to 0.55. So, a hypothesis confirmed by two separate cases is falsified by combining them. This paradox turned up in a sex bias study at the University of California at Berkley (Sex Bias in Graduate Admissions: Data from Berkeley, P. J. Bickel, E. A. Hammel and J. W. O’Connell.)

(Blyth’s spinner paradox.)

Blyth developed the next case. Spinner A is an undivided dial that always gives a value of 3. Spinner B gives values of 2, 4, and 6, with probability distributions of .56, .22 and .22. Spinner C is divided into 1 and 5, with probabilities of .51 and .49 respectively. You pick one spinner, your friend takes another. You both spin and highest number wins. Based on experience, which spinner do you take? When compared in pairs, A beats B with a probability of 1 * 0.56 = 0.56. A beats C: 1 * 0.51 = 0.51. B beats C: (1 * 0.22) + (0.22 * 0.51) + (0.56 * 0.51) = 0.6178. With two players, A is the obvious best choice, and C is the worst. But, with 3 players, A wins with 0.56 * 0.51 = 0.2856; B wins with 0.44 * 0.51 = 0.3322; C wins with a probability of 0.49 * 0.78 = 0.3822. C is best and A is worst. Conclusion: Induction has its pitfalls, and you have to be very careful when relying on it.

Puzzle:
A statistician eats at a restaurant that offers apple pie and cherry pie. He/she rates their satisfaction with each kind of pie with values 1 through 6. The apple pie is uniformly a 3 (spinner 1), and the cherry pie varies from night to night as based on spinner 3. From that point on, the statistician always picks the apple pie. The restaurant occasionally offers a blueberry pie (spinner 2). Which pie does he/she order that night?

Extended binary already allows for encoding “0”, “1”:
0 = 0
1 = 10

In order to rewrite algorithms in this format, we need to represent “L”, “R” and STOP.

R = 110
L = 1110
R.STOP = 11110

We can continue this process to include “+”, “-“, “*”, “/” if we like. I’m not going to, because we’re getting very close to the point of all of these exercises.

Say we want to convert “110 -> 1011R” and “1010 -> 01STOP” to the new format.

Recall that “110” is “for state 11, if we read 0”, then do the following.
“101” is the new state we’ll store to the machine.
“1” is value we’ll write to the tape.
“R” is the direction we’ll move the tape head (either left or right).
“STOP” is short for “R.STOP” = move the tape head one position to the right, and stop processing.

We could use an extended binary code for “->”, but that’s not really necessary. By convention, we’ll stop including the state + read bit information in the algorithm. Instead, we’ll just put all of the algorithm statements in sequence, and add dummy lines for state + read bit combinations that never occur in practice (i.e – dummy: 00R). This is why we’re using binary for the state values.

The corrected xn_times_2 algorithm:
00-00R
01-11R
10-00R
11-101L
100-00STOP
101-110R
110-101R
111-111R

becomes

00R
11R
00R
101L
00STOP
110R
101R
111R

becomes

00110
1010110
00110
100101110
0011110
10100110
10010110
101010110

Becomes
0011010101100011010010111000111101010011010010110101010110

Which, if you convert it to decimal as-is becomes a big number (6.0109e16) that actually encapsulates the entire algorithm. You can add this number to the tape to the left of your data, and then add a “boot loader” to your Universal Turing machine to start out by reading the tape to load the algorithm up to where you hit some kind of end-of-program marker. After that everything is data that the algorithm uses. (Alternatively, you can use two tape readers, one to read the algorithm, the other to read/write the data.)

Why go to all this work?

Well, recall that Alan Turing started all this out in order to answer David Hilbert’s question of whether there’s some way to apply a purely mechanical, deterministic approach to proving and/or finding all possible math theorems.

With a universal Turing machine, EVERY decimal number represents a theorem of some sort. 0, 1, 123, 567 – they’re all potential math theorems in this sense. If a “theorem” (AKA – algorithm) returns a valid answer, then that “theorem” has been proven. The problem is that most of the “theorems” produced this way will never stop (e.g. – “0” just writes a 0 to the tape and then sits there). To get around this, Turing suggested that we make a “box” that evaluates any given algorithm and returns “1” if it will ever stop, and “0” if it won’t stop.

Then, we make an m-n table, where m represents the numbers 0 to infinity, as Turing machine numbers, and n is the data we feed into the machine. If the halting box returns “1”, then we run the algorithm for that value of n, and plug the answer into the table. Otherwise, we don’t run the algorithm, and just put “0” in the table.

– 0 1 2 3 4 n
0 0 0 0 0 0
1 0 0 0 0 0
2 1 1 0 1 1
3 1 2 3 4 1
4 6 1 0 0 7
m

Because the tape is infinitely long, we can test every combination of machine “m”, and data input “n”. At some point, we will “prove” that “1 + 1 = 2”, that the sum of the angles of a triangle equals 180 degrees, and that the Riemann hypothesis is true.

This is great, except for two things. First, no one has ever been able to solve the halting problem. We can’t, simply by looking at any arbitrary algorithm, say if it will ever stop or not. If the algorithm is to calculate all digits of pi, e, or 1/3, it will never stop. And there’s going to be a LOT of combinations of m and n that will require just that.

The second thing is what happens when we apply Georg Cantor’s matrix diagonal function to the above table.
Pick the first value of the table from the first row, the second value from the second row, etc.

0 0 0 4 7…

And add 1 to each value to create a new number.

1 1 1 5 8…

This is Cantor’s proof that no set can include all of its subsets. This new number will be unique and does not already exist in the table, because if it did exist in the table, we’d just add 1 to one of its digits (where the diagonal crosses that line) and get yet another number, which we now know is NOT in the table.

The set of all algorithms and data (Aleph-Null) does NOT include the set of all subsets (Aleph-One). This, along with Godel’s Incompleteness Theorem, answers Hilbert’s question – No, there is no purely mechanical, deterministic way of churning out math proofs.

That’s a lot of work just to get to “no.”

Next time – one last VBScript.