My first (and last?) computer science paper

Some years back I was searching for a better method to play lightgun games like Duck Hunt under emulation by using a Wii remote as a light gun.

The standard Wii remote way of pointing at a TV with a sensor bar underneath is not precise enough. The Wii remote has an infrared camera that tracks the LEDs in the sensor bar, and uses that to estimate where the remote is pointing. But since all the LEDs in the sensor bars lie in a single line, there is no way to determine from the camera image exactly how the Wii remote points. (It’s easy to visualize how rotating the Wii remote about the axis defined by the sensor bar won’t change the camera image in it.) The Wii just guesses, but that’s not good enough for lightgun games.

I already had a way that involved putting four infrared LEDs around my TV, but I was wondering if one could do this with a standard sensor bar by leveraging the additional information from the accelerometer in the Wii remote. A web search came up with a paper by d’Alfonso et al. on determining camera pose using two landmarks and accelerometer. The paper claimed a theorem that, except in certain singular cases, one could determine the pose up to a two-option ambiguity—i.e., there will be two camera orientation/position setups that would result in the same landmark images and accelerometer data.

After thinking about the paper, I realized that the claimed theorem was incorrect: there were singular cases the authors didn’t know about, but more interestingly I discovered cases where one could determine camera pose from two landmark images and accelerometer data without any ambiguity. Moreover, one of these cases was precisely the one relevant to me: the two landmarks are on the same horizontal line (the Wii sensor bar supplies precisely that) and the camera is above or below the plane of that line (easy to arrange). Sadly, experiments showed that Wii remote accelerometer precision was insufficient to determine camera pose in this way.

Anyway, I don’t like the idea of there being a published “theorem” that is incorrect. At some point I worked out all the details with trigonometry, and found a precise characterization of the exact conditions under which in theory (i.e., given a sufficiently precise accelerometer, unlike the one in the Wii remote) one could determine camera pose from two landmark images and gravity data with no ambiguity, with an ambiguity of two, or with an ambiguity of infinity (in some singular cases).

I just got a paper with all the details published.

Sadly, as noted, the Wii remote application didn’t pan out. However, I did write some proof of concept code for my Pixel 7 Pro, and found that it worked pretty decently with its accelerometer. Here’s a screenshot where the accelerometer data plus the screen positions of the (centers of) the bottom two Aruco markers, together with data about the camera and the dimensions of my display board, is used to calculate the screen positions of the upper two Aruco markers (the calculated positions are marked in red).

I kind of suspect that the accelerometer in the right-hand Nintendo Switch joycon might be sufficiently precise for use as a lightgun with two infrared LEDs for positioning, but I haven’t had time to implement this. (Part of the problem is that the infrared LEDs that I have at home are the wrong wavelength for the joycon.)

While this may be my last computer science paper, if some computer science grad student or the like is interested in working with me, we could do some empirical work on seeing how applicable the algorithm is.

Probably most people you know are more social than you

You might observe:

1. Most of the people I know are more social than me.

And then you might beat up on yourself, concluding:

2. I am less social than most people.

But the inference from (1) to (2) is obviously fallacious.

For whether you know a person is a function of how social you are and how social they are. Thus, the sample of people in (1) suffers from an evident sampling bias: it is skewed towards people who are more likely to be social.

How strong is this bias? Well, here is a model. There are N people. Each person has a sociality score between 0 and 1. Each person knows themselves. For each pair of distinct people, we independently decide if they know each other, with a probability equal to the average of their sociality scores. Then we calculate the fraction of people who have the property that most people they know have a higher sociality score.

Computer simulation gives us about 59% for N = 1000 or N = 1500 with sociality scores uniformly distributed from 0 to 1. I haven’t bothered to come up with a closed form solution.

So the bias isn’t that strong, but indeed most people are such that most people they know are more social than they are.

I just saw this more thorough related study.

Ontology and duck typing

Some computer languages (notably Python) favor duck-typing: instead of relying on checking whether an object officially falls under a type like duck, one checks whether it quacks, i.e., whether it has the capabilities of a duck object. You can have a dog object that behaves like a vector, and a vector object that behaves like a dog.

It would be useful to explore how well one could develop an ontology based on duck-typing rather than on categories. For instance, instead of some kind of categorical distinction between particulars and universals, one simply distinguishes between objects that have the capability to instantiate and objects that have the capability to be instantiated, without any prior insistence that if you can be instantiated, then you are abstract, non-spatiotemporal, etc. Now it may turn out that either contingently or necessarily none of the things that are spatiotemporal can be instantiated, but on the paradigm I am suggesting, the explanation of this would not lie in a categorical difference between spatiotemporal entities and entities that have the capability of being instantiated. It may lie in some incompatibility between the capabilities of being instantiated and occupying spacetime (though it’s hard to see what that incompatibility would be) or it may just be a contingent fact that there is no object has both capabilities.

As a theist, I think there is a limit to the duck typing. There will, at least, need to be a categorical difference between God and creature. But what if that’s the only categorical difference?

Chinese Room thought experiments

Thought experiments like Searle’s Chinese Room are supposed to show that understanding and consciousness are not reducible to computation. For if they are, then a bored monolingual English-speaking clerk who moves around pieces of paper with Chinese letters letters—or photographic memories of them in his head—according to a fixed set of rules counts as understanding Chinese and having the consciousness that goes with that.

I used to find this an extremely convincing argument. But I am finding it less so over time. Anybody who thinks that computers could have understanding and consciousness will think that a computer can run two different simultaneous processes of understanding and consciousness sandboxed apart from one another. Neither process will have the understanding and consciousness of what is going on in the other process. And that’s very much what the functionalist should say about the Chinese Room. We have two processes running in the clerk’s head. One process is English-based and the other is a Chinese-based process running in an emulation layer. There is limited communication between the two, and hence understanding and consciousness do not leak between them.

If we accept the possibility of strong Artificial Intelligence, we have two choices of what to say about sandboxed intelligent processes running on the same hardware. We can say that there is one person with two centers of consciousness/understanding or that there are two persons each with one center. On the one person with two mental centers view, we can say that the clerk does understand Chinese and does have the corresponding consciousness, but that understanding is sandboxed away from the English-based processing, and in particular the clerk will not talk about it (much as in the computer case, we could imagine the two processes communicating with a user through different on-screen windows). On the two person view, we would say that the clerk does not understand Chinese, but that a new person comes into existence who does understand Chinese.

I am not saying that the proponent of strong AI is home free. I think both the one-person-two-centers and two-person views have problems. But these are problems that arise purely in the computer case, without any Chinese room kind of stuff going on.

The one-person-two-centers view of multiple intelligent processes running on one piece of hardware gives rise to insoluble questions of the unity of a piece of hardware. (If each process runs on a different processor core, do we count as having one piece of hardware or not? If not, what if they are constantly switching between cores? If yes, what if the separate the cores to separate pieces of silicon that are glued along an edge?) The two-persons view, on the other hand, is incompatible with animalism in our own case. Moreover, it ends up identifying persons with software processes, which leads to the unfortunate conclusion that when the processes are put to sleep, the persons temporarily cease to exist—and hence that we do not exist when sufficiently deeply asleep.

These are real problems, but no additional difficulty comes from the Chinese room case that I can see.

Against digital phenomenology

Suppose a digital computer can have phenomenal states in virtue of its computational states. Now, in a digital computer, many possible physical states can realize one computational state. Typically, removing a single atom from a computer will not change the computational state, so both the physical state with the atom and the one without the atom realize the same computational state, and in particular they both have the same precise phenomenal state.

Now suppose a digital computer has a maximally precise phenomenal state M. We can suppose there is an atom we can remove that will not change the precise phenomenal state it is in. And then another. And so on. But then eventually we reach a point where any atom we remove will change the precise phenomenal state. For if we could continue arbitrarily long, eventually our computer would have no atoms, and then surely it wouldn’t have a phenomenal state.

So, we get a sequence of physical states, each differing from the previous by a single atom. For a number of initial states in the sequence, we have the phenomenal state M. But then eventually a single atom difference destroys M, replacing it by some other phenomenal state or by no phenomenal state at all.

The point at which M is destroyed cannot be vague. For while it might be vague whether one is seeing blue (rather than, say, purple) or whether one is having a pain (rather than, say, an itch), whether one has the precise phenomenal state M is not subject to vagueness. So there must be a sharp transition. Prior to the transition, we have M, and after it we don’t have M.

The exact physical point at which the transition happens, however, seems like it will have to be implausibly arbitrary.

This line of argument suggests to me that perhaps functionalists should require phenomenal states to depend on analog computational states, so that an arbitrarily small of the underlying physical state can still change the computational state and hence the phenomenal state.

Mice

It feels like I am constantly fixing computer mice. The most common issue is the wires breaking near the mouse, requiring me to shorten the cable and resolder it to the PCB. I usually also add some glue or heat shrink tubing as strain relief if I haven’t done so already. Switching the household to wireless mice would solve the problem, at the expense of having yet more batteries to deal with.

I started off today with a new fix: the plastic axle from a mouse wheel broke off. I drilled through the mouse wheel and put a toothpick in instead. We’ll see how long that holds up. If it doesn’t, I’ll have to see if I can find a screw or nail of the right diameter instead.

Likely near future task: my daughter complains of a mouse double clicking. When it earlier had that problem, it seemed to me that it was generating an extra click on release, which sounds to me like a debouncing failure. But then I took it apart and put it back together and the problem disappeared, so I didn’t have a chance to fix it. Apparently the problem has come back, but I can’t duplicate it. If and when I duplicate it, I plan to hook it up to an oscilloscope, and play around with capacitors to debounce the release.

I wonder if problems would decrease if we bought more expensive mice.

Reading a Game Boy Tetris cartridge

I saw a small rectangular PCB on the sidewalk not far from my house. It looked interesting. I left it for a couple of days in case someone lost it and returned for it. A web search showed it was the PCB from a Game Boy cartridge. Eventually, I took the PCB home, and made it a challenge to extract the data from it with only the tools I had at home and without harming the PCB (so, no soldering).

This PCB was from a ROM-only cartridge, 32K in size (I was able to identify it from the part number and photos online as likely to be Tetris), so it should have been particularly easy to read. The protocol is described here.

While the Game Boy cartridges run at 5V, the only microcontroller I had available with enough GPIOs  and ready to use was an stm32f103c "black pill" which runs at 3.3V. Fortunately, it has a number of 5V-tolerant GPIOs, so there was some hope that I could run the cartridge at 5V and read it with the microcontroller.

The Game Boy I didn't have a cartridge connector, but fortunately the PCB had plated through-holes on all but two of the lines, and they fit my breadboard jumper wires very nicely. I used test clips for the remaining two lines (VCC and A0). After some detours due to connection mistakes and a possibly faulty breadboard or GPIO, I ended up with this simple setup (what a mess on the breadboard!).

1. Connect D0-D7 on the cartridge to 5V-tolerant inputs, connect A0-A14 on the cartridge to outputs, ground GND, A15 and RD (CS and RS were not connected to anything on the cartridge), and connect VCC to a power supply (it turned out that all my worries about 3.3V/5V were unnecessary: supplying 3.3V, 4.5V or 5V all worked equally well). 

2. Write a 15-bit address to A0-A14. Wait a microsecond (this could be shaved down, but why bother?). Read the byte from D0-D7. Increment address. Repeat. Check the header and ROM checksums when done. Arduino code is here.  (I just copied and pasted the output of that into a text file which I then processed with a simple Python script.)

It works! I now have a working Tetris in an emulator, dumped from a random PCB that had been lying on the sidewalk through torrential rains!

I've played many versions of Tetris. This one plays very nicely.

Some technical notes:

• I got advice from someone to set pulldown on the D0-D7 lines. Turns out that makes no difference.
• Cartridges that are more than 32K would need some bank switching code.

Android Shogi app with Bonanza engine

I updated an old Android Shogi (Japanese chess) app that uses the Bonanza engine to work better with newer devices (and I also simplified it a bit). I also added optional animal-themed pieces (like in Dobutsu Shogi in the Greenwood) as that's what I'm more used to from playing with my kids.

Google Play: https://play.google.com/store/apps/details?id=mobi.omegacentauri.shogi

APK: https://github.com/arpruss/AndroidShogi/tree/main/app/release

Source Code: https://github.com/arpruss/AndroidShogi

[Note: the Bonanza engine is for non-commercial use only]

Synchronization and the unity of consciousness

The problem of the unity of consciousness for materialists is what makes activity in different areas of the physical mind come together into a single phenomenally unified state rather than multiple disconnected phenomenal states. If my auditory center active in the perception of a middle C and my visual center is active in the perception of red, what makes it be the case that there is a single entity that both hears a middle C and sees red?

We can imagine a solution to this problem in a computer. Let’s say that one part of the computer has and representation of red in one part (of the right sort for consciousness) and a representation of middle C in another part. We could unify the two by means of a periodic synchronizing clock signal sent to all the parts of the computer. And we could then say that what it is for the computer to perceive red and middle C at the same time is for an electrical signal originating in the same tick of the clock to reach a part that is representing red (in the way needed for consciousness) and to reach a part that is representing middle C.

On this view, there is no separate consciousness of red (say), because the conscious state is constituted not just by the representation of red (say) in the computer’s “visual system”, but by everything that is reached by the signals emanating from the clock tick. And that includes the representation of middle C in the “auditory system”.

The unification of consciousness, then, would be the product of the synchronization system, which of course could be more complex than just a clock signal.

This line of thought shows that in principle the problem of the unity of consciousness is soluble for materialists if the problem of consciousness is (which I doubt). This will, of course, only be a Pyrrhic victory if it turns out that no similar pervasive synchronization system is found in the brain. The neuroscience literature talks of synchronization in the brain. Whether that synchronization is sufficient for solving the unity problem may be an empirical question.

The above line of thought also strongly suggests that if materialism is true, then our internal phenomenal timeline is not the same as objective physical time, but rather is constructed out of the synchronization processes. It need not be the case for this that the representation of red and the representation of middle C happen at the same physical time. A part further from the clock will receive the synchronizing signal later than a part closer to the clock, and so the synchronization process may make two events that are not simultaneous in physical time be simultaneous in computer time. I suspect that a similar divide between mental time and physical time is true even if dualism is (as I think) true, but for other reasons.

Swapping ones and zeroes

Decimal addition can be done by a computer using infinitely many algorithms. Here are two:

1. Convert decimal to binary. Add the binary. Convert binary to decimal.

2. Convert decimal to inverted binary. Inv-add the binary. Convert inverted binary to decimal.

By conversion between decimal and inverted binary, I mean this conversion (in the 8-bit case):

• 0↔11111111, 1↔11111110, 2↔11111101, …, 255↔00000000.

By inv-add, I mean an odd operation that is equivalent to bitwise inverting, adding, and bitwise inverting again.

You probably thought (or would have thought had you thought about it) that your computer does decimal addition using algorithm (1).

Now, here’s the fun. We can reinterpret all the physical functioning of a digital computer in a way that reverses the 0s and 1s. Let’s say that normally 0.63V or less counts as zero and 1.17V or higher counts as one. But “zero” or “one” are our interpretation of analog physical states that in themselves do not have such meanings. So, we could deem 0.63V or less to be one and 1.17V or higher to be zero. With such a reinterpretation, logic gates change their semantics: OR and AND swap, NAND and NOR swap, while NOT remains NOT. Arithmetical operations change more weirdly: for instance, the circuit that we thought of as implementing an add should now be thought of as implementing what I earlier called an inv-add. (I am inspired here by Gerry Massey’s variant on Putnam reinterpretation arguments.)

And if before the reinterpretation your computer counted as doing decimal addition using algorithm (1), after the reinterpretation your computer uses algorithm (2).

So which algorithm is being used by a computer depends on the interpretation of the computer’s functioning. This is a kind of flip side to multiple realizability: multiple realizability talks of how the same algorithm can be implemented in physically very different ways; here, the same physical system implements many algorithms.

There is nothing really new here, though I think much of the time in the past when people have discussed the interpretation problem for a computer’s functioning, they talked of how the inputs and outputs can be variously interpreted. But the above example shows that we can keep fixed our interpretation of the inputs and outputs, and still have a lot of flexibility as to what algorithm is running “below the hood”.

Note that normally in practice we resolve the question of which algorithm is running by adverting to the programmers’ intentions. But we can imagine a case where an eccentric engineer builds a simple calculator without ever settling in her own mind how to interpret the voltages and whether the relevant circuit is an add or an inv-add, and hence without settling in her own mind whether algorithm (1) or (2) is used, knowing well that either one (as well as many others!) is a possible interpretation of the system’s functioning.

Digital and analog states, consciousness and clock skew

In a computer, we have multiple layers of abstraction. There is an underlying analog hardware level (which itself may be an approximation to a discrete quantum world, for all we know)—all our electronic hardware is, technically, analog hardware. Then there is a digital hardware level which abstracts from the analog hardware level, by counting voltages above a certain threshold as a one, below another—lower—threshold as a zero. And then there are higher layers defined by the software. But it is interesting that there is already semantics present at the digital level: three volts (say) means a one while half a volt (say) means a zero.

At the (single-threaded) software level, we think of the computer as being in a sequence of well-defined discrete states. This sequence unfolds in time. However, it is interesting to note that the time with respect to which this sequence unfolds is not actually real physical time. One reason is this. At the analog hardware level, during state transitions there will be times when the voltage levels are in an area that does not define a digital state. For instance, in 3.3V TTL logic, a voltage below 0.8V is considered a zero, a voltage above 2.0V is considered a one, but in between what we have is “undefined and results in an invalid state”. Since physical changes at the analog hardware level are continuous, whenever there is a change between a zero and a one, there will be a period of physical time at which the voltage is in the “undefined” range.

It seems then that the well-defined software state thus can only occur at a proper subset of the physical times. Between these physical times are physical times at which the digital states, and hence the software states that are abstractions from them, are undefined. This is interesting to think about in connection with the hypothesis of a conscious computer. Would a conscious computer be conscious “all the time” or only during the times when software states are well defined?

But things are more complicated than that. The technical means by which undefined states are dealt with is the system clock, which sends a periodic signal to the various parts of the processor. The system is normally so designed that when the clock signal reaches a component of the processor (say, a flip-flop), that component’s electrical states have a well-defined digital value (i.e., are not in the undefined range). There is thus an official time at which a given component’s digital values are defined. But at the analog hardware level, that official time is slightly different for different components, because of “clock skew”, the physical phenomenon that clock signals reach different components at different times. Thus, when we say that component A is in state 1 and component B is in state 0 at the same time, the “at the same time” is not technically defined by a single physical time, but rather by the (normally) different times at which the same clock signal reaches A and B.

In other words, it may not be technically correct to say that the well-defined software state occurs at a proper subset of the physical times. For the software state is defined by the digital state of multiple components, and the physical times at which these digital state “count” is going to be different for different components because of clock skew. In fact, I assume that the following can and does sometimes happen: component B is designed so that the clock signal reaches it after it has reached component A, and by the time component B is reached by the clock signal, component A has started processing new data and no longer has a well-defined digital state. Thus at least in principle (and I don’t know enough about the engineering to know if this happens in practice) it could be that there is no single physical time at which all the digital states that correspond to a software state are defined.

If this is right, then when we go back to our thought experiment of conscious computer, we should say this: The times of the flow of consciousness in that computer are not even a subset of the physical times. They are, rather, an abstraction, what we might call “software time”. If this is right, the question of whether the computer is presently conscious will be literally nonsense. The computer’s software time, which its consciousness is strung out along, has a rather complex relationship to real time.

So what?

I don’t know exactly. But I think there are a few directions one could take this line of thought:

1. Consciousness has to be strung out in a well-defined way along real time, and so computers cannot be conscious.

2. It is likely that similar phenomena occur in our brains, and so either our consciousness is not based on our brains or else it is not strung out along real time. The latter makes the A-theory of time less plausible, because the main motive for the A-theory is to do justice to our experience of temporality. But if our experience of temporality is tied to an abstracted software time rather than real time, then doing justice to our experience of temporality is unlikely to reach the truth about real time. This in turn suggests to me the conditional: If the A-theory of time is true, then some sort of dualism is true.

3. The problem that transitions between meaningful states (say, the ones and zeros of the digital hardware level) involve non-meaningful states between them is likely to afflict any plausible theory on which our mental functioning supervenes on a physical system. In digital computers, the way a sequence of meaningful states is reconstructed is by means of a clock signal. This leads to an empirical prediction: If the mental supervenes on the physical, then our brains have something analogous to a clock signal. Otherwise, the well-defined unity of our consciousness cannot be saved.

Group "belief"

Even though nobody thinks Strong AI has been achieved, we attribute beliefs to computer systems and software:

• Microsoft Word thinks that I mistyped that word.

• Google knows where I’ve been shopping.

The attribution is communicatively useful and natural, but is not literal.

It seems to me, however, that the difference in kind between the beliefs of computers and the beliefs of persons is no greater than the difference in kind between the beliefs of groups and the beliefs of persons.

Given this, the attribution of beliefs to groups should also not be taken to be literal.

Provability and numerical experiments

A tempting view of mathematics is that mathematicians are discovering not facts about what is true, but about what is provable from what.

But proof is not the only way mathematicians have of getting at truth. Numerical experiment is another. For instance, while we don’t have a proof of Goldbach’s Conjecture (each even number bigger than two is the sum of two primes), it has been checked to hold for numbers up to 4 ⋅ 10¹⁸. This seems to give significant inductive evidence that Goldbach’s Conjecture is true. But it does not seem to give significant evidence that Goldbach’s Conjecture can be proved.

Here’s why. Admittedly, when we learned that that the conjecture holds for some particular number n, say 13, we also learned that the conjecture can be proved for that specific number n (e.g., 13 = 11 + 2 and 11 and 2 are prime, etc.). Inductively, then, this gives us significant evidence that for each particular number n, Goldbach’s conjecture for n is provable (to simplify notation, stipulate Goldbach’s Conjecture to hold trivially for odd n or n < 4). But one cannot move from ∀n Provable(G(n)) to Provable(∀n G(n)) (to abuse notation a little).

The issue is that the inductive evidence we have gathered strongly supports the claim that Goldbach’s Conjecture is true, but gives much less evidence for the further claim that Goldbach’s Conjecture is provable.

The argument above is a parallel to the standard argument in the philosophy of science that the success of the practice of induction is best explained by scientific realism.

Conscious computers and reliability

Suppose the ACME AI company manufactures an intelligent, conscious and perfectly reliable computer, C₀. (I assume that the computers in this post are mere computers, rather than objects endowed with soul.) But then a clone company manufactures a clone of C₁ out of slightly less reliable components. And another clone company makes a slightly less reliable clone of C₂. And so on. At some point in the cloning sequence, say at C₁₀₀₀₀, we reach a point where the components produce completely random outputs.

Now, imagine that all the devices from C₀ through C₁₀₀₀₀ happen to get the same inputs over a certain day, and that all their components do the same things. In the case of C₁₀₀₀₀, this is astronomically unlikely, as the super-unreliable components of the C₁₀₀₀₀ produce completely random outputs.

Now, C₁₀₀₀₀ is not computing. Its outputs are no more the results of intelligence than the copy of Hamlet typed by the monkeys is the result of intelligent authorship. By the same token, C₁₀₀₀₀ is not conscious on computational theories of consciousness.

On the other hand, C₀’s outputs are the results of intelligence and C₀ is conscious. The same is true for C₁, since if intelligence or consciousness required complete reliability, we wouldn’t be intelligent and conscious. So somewhere in the sequence from C₀ to C₁₀₀₀₀ there must be a transition from intelligence to lack thereof and somewhere (perhaps somewhere else) a transition from consciousness to lack thereof.

Now, intelligence could plausibly be a vague property. But it is not plausible that consciousness is a vague property. So, there must be some precise transition point in reliability needed for computation to yield consciousness, so that a slight decrease in reliability—even when the actual functioning is unchanged (remember that the C_i are all functioning in the same way)—will remove consciousness.

More generally, this means that given functionalism about mind, there must be a dividing line in measures of reliability between cases of consciousness and ones of unconsciousness.

I wonder if this is a problem. I suppose if the dividing line is somehow natural, it’s not a problem. I wonder if a natural dividing line of reliability can in fact be specified, though.

Life, thought and artificial intelligence

I have an empirical hypothesis that one of the main reasons why a lot of ordinary people think a machine can’t be conscious is that they think life is a necessary condition for consciousness and machines can’t be alive.

The thesis that life is a necessary condition for consciousness generalizes to the thesis that life is a necessary condition for mental activity. And while the latter thesis is logically stronger, it seems to have exactly the same plausibility.

Now, the claim that life is a necessary condition for mental activity (I keep on wanting to say that life is a necessary condition for mental life, but that introduces the confusing false appearance of tautology!) can be understood in two ways:

1. Life is a prerequisite for mental activity.

2. Mental activity is in itself a form of life.

On 1, I think we have an argument that computers can’t have mental activity. For imagine that we’re setting up a computer that has mental activity, but we stop short of making it engage in the computations that would make it engage in mental activity. I think it’s very plausible that the resulting computer doesn’t have any life. The only thing that would make us think that a computer has life is the computational activity that underlies supposed mental activity. But that would be a case of 2, rather than 1: life wouldn’t be a prerequisite for mental activity, but mental activity would constitute life.

All that said, while I find the thesis that life is a necessary condition for mental activity, I am more drawn to 2 than to 1. It seems intuitively correct to say that angels are alive, but it is not clear that we need anything more than mental activity on the part of angels to make them be alive. And from 2, it is much harder to argue that computers can’t think.

The Probabilistic Counterexampler

Every so often someone asks me if some piece of probabilistic reasoning works. For instance, today I got a query from a grad student whether

1. P(A|C)>P(A|B) implies P(A|B ∨ C)>P(A|B).

Of course, I could think about it each time somebody asks me something. But why think when a computer can solve a problem by brute force?

So, last spring I wrote a quick and dirty python program that looks for counterexamples to questions like that simply by considering situations with three dice, and iterating over all the possible combinations of subsets A, B and C of the state space (with some reduction due to symmetries).

The program is still quick and dirty, but at least I made the premises and conclusions not be hardcoded. You can get it here.

For instance, for the query above, you can run:

python probab-reasoning.py "P(a,c)>P(a,b)" "P(a,b|c)>P(a,b)" 

(The vertical bars are disjunction, not conditional probability. Conditional probability uses commas.) The result is:

a={1}, b={1, 2}, c={1}
a={1}, b={1, 2, 3}, c={1}
a={1}, b={1, 2, 3}, c={1, 2}
a={1}, b={1, 2, 3}, c={1, 3}
a={1}, b={1, 2, 3}, c={1, 4}
...

So, lots of counterexamples. On the other hand, you can do this:

python probab-reasoning.py "P(a)*P(b)==P(a&b)" "P(b)>0" "P(a,b)==P(a)" 

and it will tell you no counterexamples were found. Of course, that doesn’t prove that the result is true, but in this case it is.

The general operation is that you install python (either 2.7 or 3.x) and use a commandline to run:

python probab-reason.py premise1 premise2 ... conclusions

You can use any single letter variables for events, other than P, and the operations & (conjunction), | (disjunction) and ~ (negation) between the events. You can use conditional probability P(a,b) and unconditional probability P(a). You can use standard arithmetical and comparison operators on probabilities. Make sure that you use python’s operators. For instance, equality is ==, not =. You should also use python’s boolean operations when you are not working with events: e.g., “P(a)==1 and P(b)==0.5”.

Any premise or conclusion that requires conditionalization on a probability zero event to evaluate automatically counts as false.

You can use up to five single-letter variables and you can also specify the number of sides the die has prior to listing the premises. E.g.:

python probab-reasoning.py 8 "P(a)*P(b)==P(a&b)" "P(b)>0" "P(a,b)==P(a)" 

Numerical experimentation and truth in mathematics

Is mathematics about proof or truth?

Sometimes mathematicians perform numerical experiments with computers. Goldbach’s Conjecture says that every even integer n greater than two is the sum of two primes. Numerical experiments have been performed that verified that this is true for every even integer from 4 to 4 × 10¹⁸.

Let G(n) be the statement that n is the sum of two primes, and let’s restrict ourselves to talking about even n greater than two. So, we have evidence that:

1. For an impressive sample of values of n, G(n) is true.

This gives one very good inductive evidence that:

2. For all n, G(n) is true.

And hence:

3. It is true that: for all n, G(n). I.e., Goldbach’s Conjecture is true.

Can we say a similar thing about provability? The numerical experiments do indeed yield a provability analogue of (1):

4. For an impressive sample of values of n, G(n) is provable.

For if G(n) is true, then G(n) is provable. The proof would proceed by exhibiting the two primes that add up to n, checking their primeness and proving that they add up to n, all of which can be done. We can now inductively conclude the analogue of (2):

5. For all n, G(n) is provable.

But here is something interesting. While we can swap the order of the “For all n” and the “is true” operator in (2) and obtain (3), it is logically invalid to swap the order of the “For all n” and the “is provable” operator (5) to obtain:

6. It is provable that: for all n, G(n). I.e., Goldbach’s Conjecture is provable.

It is quite possible to have a statement such that (a) for every individual n it is provable, but (b) it is not provable that it holds for every n. (Take a Goedel sentence g that basically says “I am not provable”. For each positive integer n, let H(n) be the statement that n isn’t the Goedel number of a proof of g. Then if g is in fact true, then for each n, H(n) is provably true, since whether n encodes a proof of g is a matter of simple formal verification, but it is not provable that for all n, H(n) is true, since then g would be provable.)

Now, it is the case that (5) is evidence for (6). For there is a decent chance that if Goldbach’s conjecture is true, then it is provable. But we really don’t have much of a handle on how big that “decent chance” is, so we lose a lot of probability when we go from the inductively verified (5) to (6).

In other words, if we take the numerical experiments to give us lots of confidence in something about Goldbach’s conjecture, then that something is truth, not provability.

Furthermore, even if we are willing to tolerate the loss of probability in going from (5) to (6), the most compelling probabilistic route from (5) to (6) seems to take a detour through truth: if G(n) is provable for each n, then Goldbach’s Conjecture is true, and if it’s true, it’s probably provable.

So the practice of numerical experimentation supports the idea that mathematics is after truth. This is reminiscent to me of some arguments for scientific realism.

Computer languages

It is valuable, especially for philosophers, to learn languages in order to learn to see things from a different point of view, to think differently.

This is usually promoted with respect to natural languages. But the goal of learning to think differently is also furthered by learning logical languages and computer languages. In regard to computer languages, it seems that what is particularly valuable is learning languages representing opposed paradigms: low-level vs. high-level, imperative vs. functional, procedural vs. object-oriented, data-code-separating vs. not, etc. These make for differences in how one sees things that are if anything greater than the differences in how one sees things across natural human languages.

To be honest, though, I’ve only ever tried to learn one language expressly for the above purpose, and I didn’t persevere: it was Haskell, which I wanted to learn as an example of functional programming. I ended up, however, learning OpenSCAD which is a special-purpose functional language for describing 3D solids, though I didn’t do that to change how I think, but simply to make stuff my 3D printer can print. Still, I guess, I learned a bit about functional programming.

My next computer language task will probably be to learn a bit of Verilog and/or VHDL, which should be fun. I don’t know whether it will lead to thinking differently, but it might, in that thinking of an algorithm as something that is implemented in often concurrent digital logic rather than in a series of sequential instructions might lead to a shift in how I think at least about algorithms. I’ve ordered a cheap Cyclone II FPGA from AliExpress ($17 including the USB Blaster for programming it) to use with the code, which should make the fun even greater.

All that said, I don’t know that I can identify any specific philosophical insights I had as a result of knowing computer languages. Maybe it’s a subtler shift in how I think. Or maybe the goal of thinking philosophically differently just isn’t furthered in these ways. But it’s fun to learn computer languages anyway.

Super-simple fractal terrain generator

Here's a very simple algorithm for generating random terrains: Start with a equilateral triangle in the x-y plane. Add a uniformly and symmetrically distributed random z-offset to each vertex. Bisect each resulting edge and add a random z-offset at the newly added point, half of the magnitude of the random offsets earlier. Repeat several times.

The algorithm is no doubt known, but some quick searches for terrain generation algorithms didn't turn it up, so I am posting for people's convenience.

There are some artifacts at internal triangle boundaries that better algorithms presumably don't have, but the algorithm is super simple to implement, and because it is based on triangles it directly makes a triangular mesh. Here is some code which does this, starting with a hexagon divided into six equilateral triangles, and putting out an STL file.

The Tammes problem

I wanted to 3D print a ball with dimples like a golf ball, so I got to looking up how to evenly distribute points over the surface of a sphere. Thinking about this problem leads to a very natural optimization problem: given a natural number n, place n points on the surface of a sphere in a way that maximizes the shortest distance between any two points. This problem has a name: it is the Tammes problem. Of course, for my purposes, it really doesn't matter whether I have an exact solution to the problem--an approximate one will do.

A natural way to try to approximately solve the problem is to pretend that the points are particles that have repulsive forces between them, and then run a computer simulation of initially randomly distributed particles moving under the influence of these forces, with some frictional damping.

Inspired by this paper, I initially worked with a repulsive force inversely proportional to d^p, where d is the distance between the points and p is an exponent that is ramped up as the simulation progresses.

Experimenting with various parameters, I found it was helpful to start with p=1 and go up to p=4.5 and then stay at p=4.5 for a while before finishing the simulation. Velocity-dependent friction seems to work a little better than velocity-independent friction. The physical precision of the simulation, of course, doesn't matter at all, except as a means to getting a large minimum spacing. For 500 points, with 1000 steps of Euler-Cromer simulation and carefully tuned parameters (friction, dynamic step size, ramping schedule), I was able to get a minimum spacing of about 0.153 in one run. There is a theorem by Fejes-Tóth that implies one can't do better than 0.1702, so it's pretty close.

A hint from the above-linked paper helped along the way: one can arrange the initial positions of the particles to be symmetric around the origin (i.e., if we place one particle is at x, we place another at −x). Then we only need to simulate the motions of half of the particles, since the movements of the other half are just a reflection about the origin. Of course, this optimization only works if n is even (though if n is odd, it still may be worth arranging all but one particles symmetrically initially).

Then I had another idea. At each simulation time, we already calculate the current distance d_min between the two particles closest together, and what we want to do is to particularly strongly push apart those particles whose distance is close to that. After a fair amount of fine-tuning, I ended up modifying the repulsive force to (d−cd_min)^p, where now we ramp p from 1 to 4.5, and c from 0 to 0.9. The result was noticeably better: my best answer for n=500 went from 0.153 to about 0.162, and typical runs give me about 0.161 after only 500 steps.

In the videos, the diameters of the red ball are equal to d_min, so the point is to maximize the size of the balls without allowing them to collide. The code is written in C. It's been some time since I've programmed in C, so it was fun to go back to C. And it was also fun to go back to programming a numerical simulation, which I did a lot of back when I was a teenager. Since my teenage years, things have changed. Computers are so much faster that my ordinary laptop has no difficulty with handling n-body interaction for n around 500 or 1000: back as a teenager, the most I worked with was about n=64. Moreover, my laptop has multiple cores, and OpenMP makes it super easy to split n-body problems between cores. My Dell laptop does a 500 step calculation with 500 particles in 1.4 seconds (but for even n, we have a symmetry optimization that cuts computation time in about a half; 499 particles takes 2.6 seconds).

Enjoy the code. It's in messy but portable C, and there is a a 32-bit Windows binary that uses all the cores you have. Just give tammes one argument: the number of particles. Visualization is done by feeding an -animate option and piping to a Classic VPython script.

You can can generate an OpenSCAD golfball from the code by using a -scad option instead. Unfortunately, OpenSCAD is really slow in processing the output of tammes. The golfball on the right has n=336. I seem to have read that that's a pretty normal n for golfballs.