A Technique for Running Arbitrary Computations in One's Mind

(Note: This is a long post. If you want to skip the motivation and get to the technique right away, look for the paragraph starting with “now that the background is out of the way”)

For the last couple of years I’ve wanted to create some method for running arbitrary computations in one’s head. I don’t mean numerical calculations, I wanted to be able to run the kinds of algorithms that are utilized in functional and logical programming, as well as in type theoretic foundations for mathematics. These tend not to use numerical calculations, so techniques for such rapid calculation are niche at best for my purposes. Recently I created a technique that achieves my goal, and I’ve experimented with it, having some success.

Before I go into the details of the technique, I want to talk about some different models of computation. It’s inspired by a very specific model that would be obscure to anyone who’s not a computer scientist interested in the design of functional compilers.

One of the few serious attempts to accomplish what I’m talking about was in this paper.

It’s a very interesting paper that describes a technique that’s unrelated to what I’m going to propose here. The reason I bring it up is to quote this passage:

“[…] the recognition method can be applied much more broadly. Although I haven’t attempted this, it seems that the method could be readily used to mentally simulate general models of computation, such as Turing machines”

I’ve seen similar suggestions, that Turing machines are the foundation of computation, and so a simulation of one, if it can be made in the brain would be ideal. This is wrong. Real world computers are not based on Turing machines, but on Von-Neumann machines, so the argument isn’t even sound. Beyond that, simulating machines in one’s head has obvious problems. Firstly, the brain is massively parallel, while these abstract machines aren’t. If we are to fit a model of computation to the brain, it should be properly parallel as well. Beyond that, it’s well known that computations done on virtual machines have significant overhead on top of an algorithm ran directly on hardware. There are techniques for limiting this overhead, but it’s unlikely that such techniques will be usable on the brain.

What’s left are abstract models of computation. One example I’ve seen suggested is a cellular automata. It is a massively parallel model of computation, so it seems like a better fit. The big problem is that a cellular automata must be globally synchronized. That is, every square must be updated at the same time as everything else. At the very least this would require the entire system to be held on one’s attention, which rules this option out, on account of the magic number 7, etc.

Of the common models of computation, what’s left are the lambda and combinator calculi. The most common combinator calculus is the SK calculus. It has only two operators, S and K. They are defined like so;

K(a)(b) ==> a
S(f)(g)(x) ==> f(x)(g(x))

The important thing to understand about these operations is that K deletes a variable while S copies a variable. S’s extra structure is there to guarantee that the copied variables can be manipulated independently. Together, they form a Turing complete model of computation. You can define any function and even simulate a Turing machine with them, if you’re dedicated enough.

Notice the lack of a global update. A large expression can have these rules be applied anywhere a pattern matches, at any time. This means that, for a large expression, part of it can be memorized and shoved out of active memory, while only the small part of the program that needs to be manipulated is in active memory. This is an attribute shared with the lambda calculus.

The problem is the instantaneous copying of what might be arbitrarily large data. The entirety of what’s being copied by S (or substitution in the lambda calculus) must be in active memory at some point if the calculation is to take place entirely inside one’s head. This problem rules out combinator and lambda calculi for my purposes.

To summarize, a computational model that’s compatible with the mind must be;

  • (Potentially massively) parallel
  • locally manipulable/not requiring global updates
  • cannot require arbitrarily large data to be in active memory (e.g. by copying)

So that rules out anything that might be considered a standard model for computation. For a long while, I gave up on this project, but recently, I was introduced to a new (to me) model that satisfies all these constraints. It’s called the interaction combinator model. Here’s the original paper.

This is a two-dimensional graph manipulation calculus. The basic model I’ll start with has four main combinators.

  • A copy combinator with one input and two outputs (C)
  • An operator which implements function application, with one input and two outputs. The first input is the function being applied to, and the second is the input to the function. (A)
  • An operator implementing variable binding, with one input and two outputs. The first output indicates the variable being bound, similar to a lambda binding (B).
  • A deletion operator, with one input and no outputs. (D)

The main reduction rules are

  1. Delete Application
. ┌─┐ . . . . . . .
. │D│ . . . . . . .
. └┬┘ . . . ┌─┐ ┌─┐
.┌─┴─┐. ==> │D│.│D│
.│ A │. . . └┬┘ └┬┘
.└┬─┬┘. . . .│. .│.

2 & 3 (The same but with copy (C) and bind (B))

  1. Copy Application
. │ │ . . . ┌─┴─┐ ┌─┴─┐
.┌┴─┴┐. . . │ C │ │ C │
.│ A │. . . └┬─┬┘ └┬─┬┘
.└─┬─┘. ==> .│. ╲ ╱ .│
.┌─┴─┐. . . .│. .╳. .│
.│ C │. . . .│. ╱ ╲ .│
.└┬─┬┘. . . ┌┴─┴┐ ┌┴─┴┐
. │ │ . . . │ A │ │ A │
. │ │ . . . └─┬─┘ └─┬─┘

5 (The same, but with bind (B))

  1. Variable Substitution
. . ┌─┴─┐. . . . │
. . │ A │. . . ╭─┼─╮
. . └┬─┬┘. . . │ │ │
. . ╱ .│ . =>. │ │ │
.┌─┴─┐.│ . . . │ │ │
.│ B │.│ . . . │ │ │
.└┬─┬┘.│ . . . │ │ │

There are simpler rule sets that are Turing complete, but I think this is the most comprehensible system for its simplicity. Using these operators, we can construct numbers, booleans, control statements, pairs, proofs, etc using standard church encodings. In practice, it’s better to use stand-ins. Instead of using a church encoded true, or number 3, one should have nodes associated with them, and corresponding common sense rules, like;

.┌───┐. . . . . . . . .
.│ 3 │. . . ┌───┐ ┌───┐
.└─┬─┘. ==> │ 3 │ │ 3 │
.┌─┴─┐. . . └─┬─┘ └─┬─┘
.│ C │. . . . │ . . │ .
.└┬─┬┘. . . . │ . . │ .

The number of nodes and associated rules that a person is familiar with should grow over time.

Why is this model good for usage inside the mind? It’s completely parallel without requiring a global update rule. You can simplify different nodes of a graph independently at different times. It also doesn’t require arbitrarily large amounts of data to be in active memory. The way that duplication proceeds is by progressively passing over whatever’s being copied. This means that only the part of the graph that the copy operator is passing over, rather than everything that’s being copied, needs to be in active memory. In general, the maximum amount of information that needs to be in active memory is the size of whatever your largest reduction rule is.

Well, now that the background is out of the way, how do we instantiate this in the brain?

The basic idea is to use the graph as a memory palace. Each node in your program graph is a room, and each string is a doorway. You then manipulate the memory palace in accordance to the graph reduction rules, and eventually you’ll put the palace in a normal form that corresponds to the program’s output. Only your immediate surroundings are being manipulated, so you don’t need to have the entire program in active memory, just the local nodes/rooms. The inputs of the node are entrances, and the outputs are exits, doors that are next to each other. The graph can be thought of as a top-down map of the palace, and the strings are there to account for the inevitable impossible space that such a structure creates.

This is the core of my technique, and you could probably reinvent everything else I’ve come up with in an attempt to make this idea convenient to use. But here are some of my notes to save you some time.

Let’s consider this expression

app(app(times, 3), 7)

Which has this graph

. . ┌─┴─┐
. . │ A │
. . └┬─┬┘
. . ╱ .7.
.┌─┴─┐. .
.│ A │. .
.└┬─┬┘. .
. * 3 . .

The segment of the memory palace which corresponds to this multiplication will have at least five rooms. One room represents the multiplication itself. It will have an entrance and no exits. I usually imagine the multiplication room as a 50’s style milk-shake bar (since malt sounds like mult in multiplication). The entrance will lead to the exit of one of the two app rooms. All app rooms, in my mind, are blue hallways. From the entrance, it’s a straightaway that has the applicant through an exit door on the left wall, and the function being applied to through a door on the right wall. The left exit to this app hallway leads to the 3 room, which I’ve variously imagined as a room filled with trees, or monkeys, or mongooses, for reasons I think are obvious. The three room only has an entrance, and no exit. The exit of the app hallway leads to the right exit of the other app hallway. This will still be a blue hallway, but I may decorate it with different objects, often one’s I associate with blueness, to make it more distinct, making it easier to get my bearings. The right exit of this hall heads to the 7 room, which I imagine is filled with kangaroos or cats. The entrance of this last app hallway will lead to whatever superstructure this computation belongs to. If this is the only thing I’m doing, then the last room after going through all entrances will be a “root” room. I imagine it as being red-domed and dimly lit.

Often, I’ll imagine myself entering and exiting through the doors, as well as imagining looking through multiple doors. For example, in the room layout I sketched, if I’m standing at the 7 room, I can open the right exit of that app hallway. Looking through that door, I can look down that other hall to see the left and right exits, the left one being the 3 room, and the right one being the multiplication room. Standing in one room and looking around and through the appropriate door can solidify the palace in my memory.

It’s easier to make an iconic palace if n-ary functions and their applications are consolidated into one room. For example, multiplication can be represented as a single node being applied to other nodes. It’s more natural to represent this as

times(3, 7)

The multiplication room now has one entrance (going to the superstructure of your program) and two exits. The left exit goes to the 7 room, and the right goes to the 3 room. For multiplication, this ordering doesn’t matter, but it will in general. Often a function will be higher order, changing its arity depending on the circumstances. In that case, it doesn’t make sense to consolidate it and its applicants into a single room. You’ll find that, in practice, you’ll be unable to make a consistent set of reduction rules if you consolidate rooms willy-nilly. In those cases, we can consolidate applications, like so;

app(times, 3, 7)

This will still be a hallway, but now it has three exits. To make the interpretation consistent, it has two left exits (looking from the entrance), and one right exit. The right exit leads to the multiplication room. The nearest left exit leads to the 7 room, and the farthest, the back left exit leads to the 3 room. The last left exit always leads to the room/node being applied to the node through the right exit.

At this point we have a system which is capable of representing arbitrary formulas and equations. I think it’s a potentially easier to use alternative to something like this.

But, of course, the point is computation, so lets get onto that. When one sets out to perform a computation, one should have in their memory a concrete understanding for how different room configurations should evolve. One of the lessons I learned when experimenting with this technique is that you cannot wing the room transformations. At best, you’ll end up mentally exhausted with nothing to show for it. So, know what nodes you’re going to use, and know ALL the rules you’ll use.

A simple example can be seen in the multiplication example we had before. Let’s say we’re in a multiplication room. It has two exits. The left exit leads to a 3 room, the right, to a 5 room. I know how this configuration of rooms aught to reduce. I will this to happen, imagining a force that pushes me out of the multiplication room’s entrance, closing the door behind me. I quickly look around the room I’ve been pushed into to get my bearings. I then open the door to see a 15 room, with one entrance and no exit.

To establish this new configuration, it’s helpful to stand in an unaltered room, looking into the new, altered room. I then step through the door, and look at the unaltered room while standing in the altered one. Most transformations will be more complex than this, and it helps to go over the changes as they connect to unchanged rooms multiple times. I don’t know how important that ultimately is, but, as someone with only limited practice with these techniques, I found the redundancy helpful. Perhaps this solidification of the memory palace would be quicker and easier with practice.

I’ll look at the graph reductions I listed before to elaborate further. Take this transformation, for example;

. . ┌─┴─┐. . . . │
. . │ A │. . . ╭─┼─╮
. . └┬─┬┘. . . │ │ │
. . ╱ .│ . =>. │ │ │
.┌─┴─┐.│ . . . │ │ │
.│ B │.│ . . . │ │ │
.└┬─┬┘.│ . . . │ │ │

Let me set the scene. There are four rooms bordering this diagram. Let’s say our starting room is a bedroom, pink, and fancily decorated. This doesn’t represent anything, it’s just a room for this example. This room has at least one exit. It’s a doorway leading to a blue hallway (node A), decorated however you like. It represents function application. Walking to the end of this hallway, there are two doors, one on the left, and another on the right. The left door leads to a bathroom, painted baby blue. This bathroom has one entrance. Back in the hallway, the right door leads to a different, red hallway (node B), decorated however you like. It represents a variable binding/lambda abstraction. At the end of this red hallway are two doors, one on the left, the other on the right. The left door leads to a theater with a large screen, and many red seats. This theater has one entrance. Back in the red hallway, the right door leads to a garage, gray and stone. This garage has one entrance. Turning around, I walk up to the door of the bathroom. I look past the door leading to the red hallway. I see the theater door on the left, and the garage door on the right. Looking right, I see the entrance to the blue hallway, and the bedroom beyond. Based on the rule, I know how this should change. I “feel” a shift, and am pushed both to the bedroom and the bathroom. I open the bedroom door, seeing the garage. I open the bathroom door, seeing the theater. I walk back and forth between the door frames, and trace my way through the superstructure, understanding new roots for navigating between the previously close bathroom/theater and bedroom/garage.

Well, that was long. It doesn’t feel as long in your head, though. Let’s look at a more complicated rule;

. │ │ . . . ┌─┴─┐ ┌─┴─┐
.┌┴─┴┐. . . │ C │ │ C │
.│ A │. . . └┬─┬┘ └┬─┬┘
.└─┬─┘. ==> .│. ╲ ╱ .│
.┌─┴─┐. . . .│. .╳. .│
.│ C │. . . .│. ╱ ╲ .│
.└┬─┬┘. . . ┌┴─┴┐ ┌┴─┴┐
. │ │ . . . │ A │ │ A │
. │ │ . . . └─┬─┘ └─┬─┘

I’ll be a bit more brief on details, but one shouldn’t skimp on grounding yourself when performing a computation.

Again we have four rooms on our boarder. We start in a bedroom. The exit of the bedroom leads to the left exit of a blue hallway. The right exit of this hallway leads to a bathroom. The entrance to the blue hallway leads to the entrance of a green hallway. The left exit of the green hallway leads to a theater, the right exit leads to a garage. Seeing the pattern, and being familiar with its implications, I will the rule to run, and feel myself pushed into the four bordering rooms. From the bedroom, the exit now leads to the entrance of a green hallway with a cage in the middle (to make it distinct). The left exit of this hallway leads to the left exit of a blue hallway, decorated with angel statues. The right exit leads to the left exit of a different blue hallway, this one with beautiful fountains. The entrance to the blue hallway with angel statues leads to the theater, the entrance of the fountain hallway to the garage. The right exit of both blue hallways leads to the left and right exits of a green hallway, this one with dank, dripping walls. The entrance to this hallway leads to the bathroom. To solidify this structure in my mind, I should and do make circuits around and through the rooms, several times, looking back and forth whenever a doorway is traversed. I then travel around the rest of the superstructure that these rooms are in, refamiliarizing myself with the palace as a whole.

This is about as complicated as a rule should ever get.

I think at this stage everything is pretty well explained. I’ll finish with a complete example. This is one of the first computations I did. It was performed while I had earplugs and a sleeping mask on, as I was falling asleep.

To start, the computation was to calculate the factorial of 3. This is not hard to do in your head, its just 3 * 2 * 1 = 6, but this exercise was to see if a memory palace could be reliably manipulated in the way I wanted, and I succeeded at that. The computation proceeds with the definition of the factorial in terms of the Y combinator. Our starting problem has the graph;

. . ┌─┴─┐
. . │ A │
. . └┬─┬┘
. . ╱ .│
.┌─┴─┐.│
.│ Y │.│
.└─┬─┘.│
. .F. .3

The way this palace is initially set up, we have a root room, red and domed. It has one exit, leading to a nondescript blue hallway. The left exit of this leads to a 3 room (which, at the time, I imagined as a room filled with trees). The right exit leads to the upper floor of an expensive yacht. I imagine wood finishes, champagne, and windows looking at the see. This yacht room has one entrance and one exit. The entrance leads to the right exit of the blue hallway. The exit of the yacht room leads to a room filled with lava. This lava room is the F on the graph. It’s not a pun or anything, I just couldn’t think of anything good at the time, so lava room it was.

F is the factorial generator. It’s a function which is defined like so;

\f n . if n == 0 then 1 else n * f (n-1)

So, it has two rules. Given a graph of the form

. . ┌─┴─┐
. . │ A │
. . └┬─┬┘
. . ╱ .│
.┌─┴─┐.│
.│ A │.│
.└┬─┬┘.│
. F │ .y

We would imagine it as a hallway with three exits, two on the left, one on the right. The right one leads to the lava room. From the lava room, we can look through its single entrance and see the two other hallway exits. The nearest one leads somewhere, and the farthest leads to y. F looks at the number y. If y is 0, this graph becomes

. │ .
. 1 .
. . .
.┌─┐.
.│D│.
.└┬┘.

That is to say, that nearest hallway door gets destroyed. The way I imagine it is that I get pushed out of the hallway’s entrance, and the door closes behind me. When I open it, I see the 1 room (which is one I imagined was filled to the waist with chopped onions). This onion room has one entrance, and no exits. So wherever that other hallway exit lead is now inaccessible. If it’s accessible from elsewhere in the superstructure, then it should be reexplored from that direction. The deletion room should be evaluated from there as well. I imagine the deletion room as a petrified and permanently closed door that will push me out of a room before deleting it by petrifying the door I was just pushed through. If the area’s inaccessible anyway, then everything it leads to will be destroyed, and it can safely be forgotten. To reiterate, one should remember to explore one’s surroundings. The hallway entrance is now the entrance to the 1/onion room, and going back and forth between the two can be helpful in solidifying the new layout.

If y is not 0, we get;

.┌─┴─┐
.│ * │
.└┬─┬┘
. y │
. ┌─┴─┐
. │ A │
. └┬─┬┘
. .│.y-1

Back in the hallway, we are in the lava room, and can see the two left-(blue hallway) exits. The furthest exit from me is y. With this observed, I feel myself pushed out of the hallway entrance, the door closing behind me. Reopening that door, I see the milkshake bar from before, representing multiplication. From the entrance, I can see two exits. The right exit is y. The left leads to the same blue hallway as before, but now it has two doors. The left door leads to the y-1 room, the right to wherever the previously-nearest exit lead.

The Y combinator has a special evaluation. It has the property that;

Y(f) = f(Y(f))

Graphically, if we have a configuration of;

. │
.┌┴┐
.│Y│
.└┬┘
. │

Then this turns into

.┌─┴─┐
.│ A │
.└┬─┬┘
. │┌┴┐
. ││Y│
. │└┬┘
.┌┴─┴┐
.│ C │
.└─┬─┘

From the perspective of the yacht room, I feel the memory palace shift. the entrance to the yacht room now leads to the left exit of a new blue hallway. The exit of the yacht room leads to the right exit of a new green hallway. The left door of the green hallway leads to the right door of the blue hallway. The entrance to the blue hallway is the previous entrance to the yacht room. The entrance of the green hallway leads to the previous exit of the yacht room.

Those are all the rules. To reiterate, all the rules you plan to use should be firmly planted in your mind. The best case scenario is that the shift happens smoothly in a natural feeling way, so you barely have to think about it, you just observe the results.

Now I can start detailing the computation I actually did. To recall, the room started out like so:

I start at the root room, red and domed. It has one exit, leading to a nondescript blue hallway. I walk through the door. This nondescript blue hallway has one entrance and two exits. The entrance leads to a root room, red and domed. I go through the left exit to a 3 room, full of trees. The 3 room is full of trees and has only an entrance. This entrance leads to a nondescript blue hallway. The right hallway exit leads to a yacht room. I go through the right exit, to the yacht room. This room has one entrance and one exit. The entrance leads to a nondescript blue hallway. The exit leads to a room, hot and full of lava. I enter the lava room. It has only an entrance, leading to the yacht room.

At each doorway entrance, I look around, grounding myself. By the end of this process, the memory palace is pretty thoroughly stuck in my mind.

I stand in the yacht room. I feel the shift which alters the layout of the palace. I open the door to the entrance of the yacht room. It’s a nondescript blue hallway. It has three exits, I just entered through the furthest from the entrance. The nearest left exit opens to the 3 room. The right exit goes into a green hallway. I enter it. This green hallway has two exits. I just entered through the left exit. The right exit leads to the exit of the yacht room. With all the doors open, I can see past the yacht room, into the blue hall, back into the green hall, where I’m standing. I can see me from here. The entrance to the green hall leads to the lava room.

I go back into the yacht room, shutting all the doors. I feel the next shift. I open the exit of the yacht room, and see a lava room. I go back into the blue hallway. There are still three doors, but the right exit now leads to a separate lava room. Three doors, a lava room, a farthest yacht room, and a three room. The doors all close, and I feel a shift. I see the right exit recedes into the ground, and the farthest left door shifts along the wall to take its place. I open it, seeing the yacht room. From here I can see the exit of the yacht room, leading to the lava room. The left exit now leads to a 2 room, filled with gnats, buzzing in a dense, gross, loud cloud. I shut that door. I go through the entrance of the blue hallway. I’m in a milkshake bar. This bar has one entrance, and two exits. I just entered through the left exit. The right exit leads to the 3 room. The entrance leads to the root room.

I go back to the yacht room. I feel it shift again. I can see where this is going, and open all the doors. Once again, the blue hallway now has three doors. The right one leads to a green hallway, entered through a lava room. In a straight line, I can see the yacht room, the blue hallway, and me in the green hallway. All the doors close, and the same shift as before happens. The right blue hallway door leads to a new lava room. The exit to the yacht room now leads to a separate lava room. I go back into the blue hallway, and the same shift as before happens. The right exit recedes, and is replaced by the farthest left exit. The left exit now leads to a 1 room, filled with chopped onions. The right exit leads to the yacht, lava room past its exit. I go through the entrance of the blue hallway. I see a milkshake bar. Now there’s three exits. The right-most exit leads to a 3 room. The middle exit leads to a 2 room. The left-most exit leads into the blue hallway. I close all doors, and see the right two exits merge. The right exit leads to a 6 room. The left exit leads to a blue hallway.

(One more round later)

The palace has the same basic layout, except the factorial generator/lava room has reduced the 1 room to a 0 room. The milkshake bar’s right exit is still a 6 room, since it was multiplied by a 1 room, not changing anything. The blue hallway now has three exits. The nearest left exit is a 0 room, filled with zebras. The farthest left room leads to the yacht, lava room still past its exit. The right exit leads to a lava room. I feel myself be pushed out into the milkshake bar, the door closing behind me. I open the door back up, and see a 1 room, filled with onions.

The milkshake bar now has two exits. The left exit leads to a 1 room, and the right exit leads to a 6 room. I feel myself be pushed out into the root room, the door closing behind me. Opening the entrance, I see a 6 room.

And that’s the end of the computation.

I’d like to end with some comments on where this technique could go. It’s an odd use of the loci technique, especially since nothing is put in any of the rooms. The rooms have a theme which encodes information, but the objects in the room don’t. Ideally, I’d like to incorporate something that aids computation that takes advantage of item storage, but I don’t have any ideas how. If nothing else, the items in a room might be able to encode typing information, and maybe this system could be turned into a formal foundation of mathematics a la the calculus of constructions. It’s an interesting idea, at any rate.

Hopefully some of the people here can help me improve this, adding your own insights and tests. My hope is that this can be the first of a series of techniques that get better over time.

4 Likes

Hi Anthony,

This looks amazing. Give me some time to read it and reflect on it.

Cheers,
Kinma

1 Like

Any suggestions on where else this should be posted? I’m not too familiar with this communities online space, but I’m sure there’s somewhere else that has people who’d be interested in this.

Hi. Can you abstract this method to applied in lets say studying the russian alphabet

I have no idea how…

Just to clarify, you wrote that A has 1 input and 2 outputs. Did you mean the opposite, or am I missing something?