3 ms·

The answer in general may be uncomputable. https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity

by Y_Y 2y ago

Lerc 2y ago
AHH but in practice you are limited to 50 characters. https://c50.fingswotidun.com/ https://c50.fingswotidun.com/ Which gives you a finite problem. The VM cannot loop or define functions (yet, anyway) so it doesn't go all busy beaver on you.
- Y_Y 2y ago
  I thought it would be possible to use the (undocumented?) T instruction and use the time variable as persistent memory, but it seems to reset each step. It would be nice if there were a way to store things across time steps!
  - Lerc 2y ago
    ooh, hadn't thought about persistence. I always considered all executions running in isolation (and not necessarily in-order). Persistence would have to decide if it was localized to the same pixel, next frame or pass between pixels. A possibility for that is an instruction that sets a value in a buffer at the same resolution of the output and a paired instruction that reads the buffer generated the previous frame (with location popped from stack) so if { was write to buffer, it writes the top stack value to the buffer at the same location as the pixel output. using } to read would mean if you started a program with "xy}" would place the value from the buffer on the stack. It would also allow fade and blur effects. In a similar vein I had wondered about a kernel function that read from a buffer with a 3x3 kernel on the stack. Perhaps I should revisit the idea. Using a stack with multiple lanes of floats would potentially richer operations, colors, complex numbers, quaternions? 4 lanes could potentially Even storing the top value of the stack at the base for the next frame. Or, (new idea) a cyclic buffer stack of a fixed length. That wouldn't require any memory management at render time, and could persist multiple values just by popping them off. I'm not sure how that would impact the speed. At the moment the stack expressions are converted into JavaScript expressions for the JIT to make fast. I'd have to go back to requiring an actual stack again.
nwallin 2y ago
Kolmogorov complexity is uncomputable because it admits Turing complete languages, and reduces to the halting problem. If the language you admit isn't Turing complete, then the Kolmogorov complexity of the thing is computable. It looks like OP's language is not Turing complete. It always terminates. You can just do a breadth first search on the program space. The first program you get that outputs the number you want is the shortest program. If it were Turing complete, you can't do this, because eventually you'll find a program that just keeps running for like a really long time. Is it running because the program never halts? Or is will it halt eventually and output the number you want? You can't know for sure.
- deleted 2y ago
  [deleted]

The answer in general may be uncomputable. https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity

by Y_Y 2y ago

The answer in general may be uncomputable. https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity

Lerc 2y ago

AHH but in practice you are limited to 50 characters. https://c50.fingswotidun.com/ https://c50.fingswotidun.com/ Which gives you a finite problem. The VM cannot loop or define functions (yet, anyway) so it doesn't go all busy beaver on you.

Y_Y 2y ago
I thought it would be possible to use the (undocumented?) T instruction and use the time variable as persistent memory, but it seems to reset each step. It would be nice if there were a way to store things across time steps!
- Lerc 2y ago
  ooh, hadn't thought about persistence. I always considered all executions running in isolation (and not necessarily in-order). Persistence would have to decide if it was localized to the same pixel, next frame or pass between pixels. A possibility for that is an instruction that sets a value in a buffer at the same resolution of the output and a paired instruction that reads the buffer generated the previous frame (with location popped from stack) so if { was write to buffer, it writes the top stack value to the buffer at the same location as the pixel output. using } to read would mean if you started a program with "xy}" would place the value from the buffer on the stack. It would also allow fade and blur effects. In a similar vein I had wondered about a kernel function that read from a buffer with a 3x3 kernel on the stack. Perhaps I should revisit the idea. Using a stack with multiple lanes of floats would potentially richer operations, colors, complex numbers, quaternions? 4 lanes could potentially Even storing the top value of the stack at the base for the next frame. Or, (new idea) a cyclic buffer stack of a fixed length. That wouldn't require any memory management at render time, and could persist multiple values just by popping them off. I'm not sure how that would impact the speed. At the moment the stack expressions are converted into JavaScript expressions for the JIT to make fast. I'd have to go back to requiring an actual stack again.

nwallin 2y ago

Kolmogorov complexity is uncomputable because it admits Turing complete languages, and reduces to the halting problem. If the language you admit isn't Turing complete, then the Kolmogorov complexity of the thing is computable. It looks like OP's language is not Turing complete. It always terminates. You can just do a breadth first search on the program space. The first program you get that outputs the number you want is the shortest program. If it were Turing complete, you can't do this, because eventually you'll find a program that just keeps running for like a really long time. Is it running because the program never halts? Or is will it halt eventually and output the number you want? You can't know for sure.

deleted 2y ago
[deleted]