What is Computation? (I have no idea)

It’s kind of ironic how, when developing my understanding of subjective metaphysics, one of the major holdouts that I haven’t been able to crack is “computation”.

What is the nature of computation? I have no idea. In particular, why does any computation take longer than linear time at all? What is the computer doing metaphysically? Well… proving lower bounds of time complexity is notoriously difficult, and is one of the reasons why nobody has been able to prove P != NP, and for more mundane problems there are no general methods for proving lower bounds.

[[While researching this topic I came across a relatively recent result where “3sum” was shown to have sub-quadratic (sub-n^2) algorithms despite being widely assumed to be quadratic… if theorists could be “wrong” in something as “simple” as this, who knows what else we might have missed when making assumptions about time complexity lower bounds…]]

Scott Aaronson’s early writings were quite fun in this regard. He mused about solving NP complete problems in P time by time travel (through closed timelike curves) or by unaliving oneself if you don’t guess the right answer (an extreme form of the anthropic principle).

It’s not common for people to think about computation as having made many assumptions about the underlying physical reality, but when we’re talking about metaphysics and the nature of computation we really should review the assumptions we’re making here. And not only the assumptions acceptable to mainstream physics, but also other unacceptable kinds of assumptions too.

Like… magic.

I mean, this is an unconventional take, but I know telepathy and ESP is real in at least some forms, but I really don’t know about closed timelike curves…. (sidenote: Alan Turing did give substantial attention to the possibility of ESP being real in his paper on the Turing Test)

Once you open up all possibilities, some funny observations are trivial but metaphysically important, like, “P=NP if God tells you the answer”. In this sense anyone who proves P!=NP would probably inadvertently prove a lot more than they originally intended. (I mean, at least their model of computation would have to exclude the possibility of a benevolent God…) I don’t know why nobody ever mentioned this as a reason why proving P!=NP is hard, but now you know…

This doesn’t just apply to P!=NP (which is not my focus), but also applies to computation in general. If god tells you the result you don’t have to compute the answer. Even if you don’t always trust it, all computational complexity would still be reduced to checking the answer. (Here’s another riddle: if you know the answer you don’t have to ask; if you ask you will get an answer; if you trust the answer, you don’t have to check, and if you never check the answer, you’ll never know the answer was “objectively” wrong… wait what were we trying to do in the first place?)

Anyway the best theory I have so far about computation is that it’s a technological ritual to explain why the answer is correct. In other words, Math Magic! Note that we’re taking the subjective perspective of the present moment, and we do not posit that the past actually exists aside of what is already encoded in the present. So we do not posit that computation actually happened (it may or may not have, doesn’t matter) – what we have (at the present) is a computer with a purported answer, and some evidence that it has gone through a process of computation (eg. we remember [in our brain!] writing the program and executing it). I’m starting to think that the “parallel” memory (eg. in the brain of the computer operator) of the context and history of the computing process might be important metaphysically. Otherwise, if you just happen to come across a program that emits a result, it doesn’t mean anything at all. (eg. “42”)

Many years ago I proposed an interesting thought experiment that highlights this aspect of computation, where you can imagine people start losing confidence in the process because so much time has passed: Imagine there was a computational problem that was so important to humanity that they built a super computer and have it calculate the answer for 1000 years. 1000 years later the result came out. Assume the answer cannot be checked (unless you run it again for 1000 years to check). Do you really trust the answer? Do you really know that it was calculating the thing you thought it was calculating? Nobody witnessed the start of the computation, everyone alive is born after the computation already started. Do you trust the history books and records? What if people made a mistake in the records? How do you know? How do you verify? How much do you trust the results then?

And thus, computation on a macro(?) scale of hundreds of years is probably a different kind of thing than the computation we perform in seconds. I still think I’m missing something important though. It’s probably something to do with how we “value” some patterns more than others. Braindumping here to all yous rubber ducks in hopes that something will come up eventually.