A program-like data structure is natural for representing locality + symmetry
Didn’t quite get this from the lecture. For one, every rookie programmer has probably experienced that programs can work in ways with mysterious interactions that sure don’t seem very local… but maybe in your case you’d still say that at the end of the day it would all just be unpackable into a graph of function calls, respecting locality at each step?
Question: what’s an example of a data structure very similar to program-like ones, while failing to respect locality + symmetry?
maybe in your case you’d still say that at the end of the day it would all just be unpackable into a graph of function calls, respecting locality at each step?
We typically implement highly nonlocal functions using very local computations. For instance, a hash function is typically very nonlocal with respect to its input and output bits—everything effects everything else. But the “internals” of that function represent it by repeatedly using symmetric, local parts (e.g. logic gates etc).
It’s usually computations (including e.g. the computation performed by a physical chunk of spacetime) which are local + symmetric. The I/O behavior of those computations (once we identify part of the computation as “input” and another as “output”) is not necessarily local + symmetric.
Question: what’s an example of a data structure very similar to program-like ones, while failing to respect locality + symmetry?
First, I’ll answer a slightly different question: what’s an example of a computation which doesn’t respect locality + symmetry? For that, imagine a gridworld in which the state at each gridpoint-time is some big function of the state of all the other gridpoint-times before it chronologically. That’s nonlocal, and if the functions differ at each gridpoint-time then it’s also nonsymmetric. Space and time wouldn’t have much meaning at all to beings living in that world (assuming that it’s even possible for minds to live in that world, which I’d weakly guess it isn’t).
Now back to data structures. Even to represent that nonlocal, nonsymmetric world we’d probably still use a data structure which depends on locality + symmetry internally; that’s built in to our intuitive notion of a “data structure” to a large extent. (For instance, a data structure is supposed to interact with the rest of a program via a defined API; that implies some degree of locality, since the data structures internals mostly don’t directly interact with all the stuff going on outside.) Data structures can generally be represented as programs; specific data structures add additional structure on top of a generic program. That’s part of why I called programs a “natural” representation for locality + symmetry: roughly speaking, they’re the “most general”/”least constrained” data structure for representing locality + symmetry, while other data structures add additional structure/constraints.
Malbolge? Or something even nastier in a similar vein, since it seems like people actually figured out (with great effort) how to write programs in Malbolge. Maybe encrypt all the memory after every instruction, and use a real encryption algorithm, not a lookup table.
Didn’t quite get this from the lecture. For one, every rookie programmer has probably experienced that programs can work in ways with mysterious interactions that sure don’t seem very local… but maybe in your case you’d still say that at the end of the day it would all just be unpackable into a graph of function calls, respecting locality at each step?
Question: what’s an example of a data structure very similar to program-like ones, while failing to respect locality + symmetry?
We typically implement highly nonlocal functions using very local computations. For instance, a hash function is typically very nonlocal with respect to its input and output bits—everything effects everything else. But the “internals” of that function represent it by repeatedly using symmetric, local parts (e.g. logic gates etc).
It’s usually computations (including e.g. the computation performed by a physical chunk of spacetime) which are local + symmetric. The I/O behavior of those computations (once we identify part of the computation as “input” and another as “output”) is not necessarily local + symmetric.
First, I’ll answer a slightly different question: what’s an example of a computation which doesn’t respect locality + symmetry? For that, imagine a gridworld in which the state at each gridpoint-time is some big function of the state of all the other gridpoint-times before it chronologically. That’s nonlocal, and if the functions differ at each gridpoint-time then it’s also nonsymmetric. Space and time wouldn’t have much meaning at all to beings living in that world (assuming that it’s even possible for minds to live in that world, which I’d weakly guess it isn’t).
Now back to data structures. Even to represent that nonlocal, nonsymmetric world we’d probably still use a data structure which depends on locality + symmetry internally; that’s built in to our intuitive notion of a “data structure” to a large extent. (For instance, a data structure is supposed to interact with the rest of a program via a defined API; that implies some degree of locality, since the data structures internals mostly don’t directly interact with all the stuff going on outside.) Data structures can generally be represented as programs; specific data structures add additional structure on top of a generic program. That’s part of why I called programs a “natural” representation for locality + symmetry: roughly speaking, they’re the “most general”/”least constrained” data structure for representing locality + symmetry, while other data structures add additional structure/constraints.
Malbolge? Or something even nastier in a similar vein, since it seems like people actually figured out (with great effort) how to write programs in Malbolge. Maybe encrypt all the memory after every instruction, and use a real encryption algorithm, not a lookup table.