Models of embedded computation; or, thoughts on computability

Thank you for your letter. How much have you thought about embedded computation and embedded agency? As Turing defined it, a computer takes a program and runs it and produces output, if the program terminates. But in our universe, we have matter that moves and changes across spacetime according to the laws of physics. These laws of physics are unchanging, but basically anything else can change. Is there a model of computation that’s more like that?

I’m pretty confused here and the question seems pretty silly but maybe it will lead to something. What is dual about a Turing machine? You have states in the head, an input string, and an output string. The universal Turing machine is one step closer to our reality: one general-purpose computation procedure which can in principle do almost any data transformation or computation or yes/no question. Of course you cannot write a program P that tells you which other programs will halt because then you could use that procedure as a subroutine in a program which does the opposite of whatever P computes. The answer is of course to have stochastic oracle machines which probabilistically output whether or not a program halts, which in the limit are almost always probably correct.

What’s missing here? Either a given program halts or it does not. I’ll say that a human staring at some code will eventually be able to figure out whether or not it terminates. What’s happening there? Whatever procedure we use in our minds to answer “does it halt?” – can it not be used as a subroutine? “Whatever you think I’ll do, I’ll really do the opposite.” Is that a meaningful sentence? If my determination procedure is explicit then you can copy-paste that and compute it and do the opposite. The first notion I see is resource constraints. If P has more computational resources than Q, then Q cannot compute P as a subroutine.

I feel something must be missing something here. The physics itself is extremely simple, and the outcome guaranteed. The outcome of the physics is computable by physics-simulators running inside the physics engine. How do I figure out whether or not a program halts? I stare at it for a while and decide. If I could write down all my steps, then you could just do the opposite outcome that my steps predict.

import does_it_halt
assert(length of does_it_halt is finite)
define wtf:
    if does_it_halt(wtf): loop()
    else: return 37

That seems like a perfectly fine way to do things. does_it_halt must be finite & specifiable, wtf seems finite & specifiable, and does_it_halt seems totally undefinable on that input.

I may be batting out of my league, mathematically here. What am I missing? A program can answer the halting problem for any program shorter than itself, ezpz. If I put a trillion random bits at the end of does_it_halt, does the procedure then work on any program under a trillion bits? The core functionality has not changed – why should it effect what can or cannot be computer by the function? Imposing arbitrary physical constraints on computation seems unnecessary but it also seems dumb that the simpler situation should be so confusing. I’m reminded of Löb’s theorem and diagnolization proofs.

As you know, a diagonalization proof goes like this: Suppose you could enumerate all of X; I can construct some x not on your list by taking the diagonal of your list and flipping the bits. If we only consider finite programs, then a diagonalization proof is not applicable, because the constructed program will be infinite. AFAIK, the incomputable programs are numberable.

Löb’s theorem states that in a proof system PS if “if P is provable in PS then P is true” is provable then P is provable in PS. If you can imply provability of P implies truth of P then P is provable. Is the universal Turing machine spec a proof system? I don’t think it really is but hmm let’s say it is. P – why not have it stand for program instead? What could go wrong? If "a program can show P halts" halts then P halts. Does that mean anything as a sentence? It doesn’t seem to show anything we already knew. What the hell is going on? I may be confused about nothing.

Let me try to lay out the classic situation from the top and see if I smell anything fishy.

All I can conclude is that the original model is not complete. Stochasticity or resource limitation are somehow fundamental to computation. Otherwise, we get ridiculous conclusions like “the halting problem is not decidable”. Fallenstein’s reflective oracles explore the stochastic situation. Many other researchers across time have also explored that situation. And many have explored the resource-constrained situation. What if I don’t read anything and just imagine what might happen with resource constraints?

Hmm I like Sean Carroll. I don’t really understand his ideas but I think he thinks the wave function and many-worlds are the big ideas. Entanglement propogates out in a sphere and there’s never any collapse – you just get entangled yourself. There is instantaneous action at a distance, subject to the constraint that you cannot send information at faster than the speed of light. This is to keep the universe computable I guess. How the eff does physics work and does it have a goddam thing to do with computation? Well I think one of the big ideas of computation is that the good math should be physically instantiable. So your computer needs to run inside a physics engine (which of course exists in another physics… oh geez). Ok how’s physics work? You have some particles with randomized interactions that never collapse and expand forever in a fragmenting computational mess which eventually stops when the universe runs out of usable energy / has a heat death. Hmm ok. Seems like a finite computation.

Build a computer inside this thing. No contradiction so far… Run multiplication or whatever you want. Uses some energy. Seems fine. Write a procedure with simple rules for deciding whether a program halts. Seems fine. Can your does_it_halt detect whether its being run as a subroutine and somehow break out and mess things up if it is? That seems like a pretty dumb idea to me but what is the alternative? Another program runs it and does the opposite. What are you going to do about it? Maybe this is true: