Thanks for the essay! As you say, not quite what I was looking for, but still interesting (though mostly saying things I already know/agree with).
My question is more in line with the recent post about the smallest possible button and my own about the cost of unlocking optimization from observation. The very idea not of what problems computation can solve, but of how far can problem-solving carry you in actually affecting the world. The limit would be I guess “suppose you have an oracle that given the relevant information can instantly return the optimal strategy to achieve your goal, how well does that oracle perform?”. So, like, is tech so advanced that it truly looks like magic even to us possible at all? I assume some things (deadly enough in their own right) like nanotech and artificial life are, but wonder about even more exotic stuff.
suppose you have an oracle that given the relevant information can instantly return the optimal strategy to achieve your goal, how well does that oracle perform?
I guess CT experts (e.g. not me) would say it either depends on boring details or belong to one of three possibilities:
if you only care about « probably approximately correct » solutions, then it’s probably in BPP
if you care about « unrealistically powerfull but still mathematically checkable » solutions, then it’s as large as PSPACE (see interactive proofs)
if you only care about convincing yourself and don’t need formal proof, then it’s among Turing degrees, because one could show it’s better than you for compressing most strings without actually proving it’s performing hypercomputation.
My point is that there have to be straight up impossibilities in there. For example, if you had a constraint to only use 3 atoms to build a molecule, there are only so many stable combinations. When one considers for example nanomachines it is reasonable to imagine that there is a minimum physical size that can embed a given program, and that size also puts limitations on effectiveness, lifetime, and sensory abilities. Like e.g. you lose resolution on movement because the smaller you are the stronger the effect of Brownian forces, stuff like that, at the crossroads between complexity theory and thermodynamics.
Thanks for the essay! As you say, not quite what I was looking for, but still interesting (though mostly saying things I already know/agree with).
My question is more in line with the recent post about the smallest possible button and my own about the cost of unlocking optimization from observation. The very idea not of what problems computation can solve, but of how far can problem-solving carry you in actually affecting the world. The limit would be I guess “suppose you have an oracle that given the relevant information can instantly return the optimal strategy to achieve your goal, how well does that oracle perform?”. So, like, is tech so advanced that it truly looks like magic even to us possible at all? I assume some things (deadly enough in their own right) like nanotech and artificial life are, but wonder about even more exotic stuff.
I guess CT experts (e.g. not me) would say it either depends on boring details or belong to one of three possibilities:
if you only care about « probably approximately correct » solutions, then it’s probably in BPP
if you care about « unrealistically powerfull but still mathematically checkable » solutions, then it’s as large as PSPACE (see interactive proofs)
if you only care about convincing yourself and don’t need formal proof, then it’s among Turing degrees, because one could show it’s better than you for compressing most strings without actually proving it’s performing hypercomputation.
My point is that there have to be straight up impossibilities in there. For example, if you had a constraint to only use 3 atoms to build a molecule, there are only so many stable combinations. When one considers for example nanomachines it is reasonable to imagine that there is a minimum physical size that can embed a given program, and that size also puts limitations on effectiveness, lifetime, and sensory abilities. Like e.g. you lose resolution on movement because the smaller you are the stronger the effect of Brownian forces, stuff like that, at the crossroads between complexity theory and thermodynamics.
I see, thanks for clarifying.