JPEG XL

with regard to bit depth, a modular stream is a method of encoding one or more channels, each of which is a rectangle of integers of a specific size those integers can be negative, they can be large, they can be lots of things after decoding a modular JXL stream, if the values are pixel values they will be clamped, so negative values are clamped to zero and values greater than 2^depth will be clamped to 2^depth

Each pixel is a computation iteration from previously generated pixels. So you can loop until you run out of pixels.

sure, but each channel's size is fixed in advance

Yep. So is my computer.

I can't download more RAM

no, but modular is limited mathematically to declaring how many iterations the loop will have before the calculation starts

and then is limited by that declaration

a computer program can just be something like ```python while True: pass ``` which theoretically will not stop

With infinite image size you get infinite loops.

except you can't have infinite image size

Yes, jxl doesn't support that. But my computer will eventually die. It has finite computation in time as well....

that doesn't make JXL more turing complete

it just means your computer is also not ideal

Yes, that was my argument.

sure, but "my computer is not an ideal turing machine because hardware has limits" doesn't have anything to do with the statement of whether or not modular mode of JXL is a programming language

modular mode of JXL isn't a programming language because you declare the number of iterations in advance and run exactly that many times which makes it strictly weaker than programming languages, from a computability standpoint

> I'm not convinced it isn't a programming language. It seems like it could even be turing complete. This is what you said, and I'm giving you a specific reason why it's a weaker form of computation, as an explanation for why it's not a turing-complete programming language. "real-life hardware is not ideal" is not a counterargument to this

the size of a jxl image has limits, just like my computer hardware. Neither is an ideal turing computer. If jxl supports arbitrarily large size (it doesn't) then I can set a number that guarantees it will outlive the universe. I think a fixed runtime is about as limiting as fixed memory. Both my computer and jxl images will run for a finite time with finite memory already set (I just don't know the number of CPU cycles that my computer will last).

fixed size that outlives the universe has nothing to do with turing completeness

turing machines are mathematical constructions decoupled with physics

a lot of the theorems on computability stop being interesting if you put a finite cap on runtimes

Well when I say my computer is turing complete I'm not saying that it is strictly equivalent to the mathematical ideal turing machine, because of course that is impossible

it's not comparable though, because modular images declare their size in advance and run for exactly that time

this means a lot of interesting questions like "will this program halt on this input" (aka the halting problem) have trivial answers in modular mode JXL streams

yes, all MA trees halt on all inputs

next question

so it's fundamentally different

You can run programs in jxl images. The fact that the jxl image ends doesn't mean the mathematical program that was running in it halted. It just means you shut the hardware off.

I mean what you're really asking then is not "are modular streams programming languages" but rather "is the MA tree model as powerful a method of computation as turing machines" but the answer is *also* no. For example, an MA tree can't output a 1 every 8 pixels, and a 0 for the other 7 using only the tree

MA trees are stateless - you walk down the tree for each pixel, but the tree itself does not change for each pixel. So only the predictors that are described in JXL can be used, and "the pixel that was 8 pixels to the left of this one" is not one of those predictors

this can be done with turing machines by having 8 states that you rotate between

**Qon** _“cellular automaton rule 110”_ 2024 image/jxl 44 bytes https://jxl-art.surma.technology/?zcode=C89MKclQMDQwMODySM1MzyiBsJ0yS1JSC0AyXEHOIQoGXFyZaQqVCnZAloICkOkHZUI44bogvq4hWAAipOvnClcCAroKwalAs9H4BiTrMESzFNMEXVyWoBtJohag8gqgWktLSy50hXApCy5sFsGUAgA%3D

"Rule 110 has the perhaps surprising property that it is Turing complete, and thus capable of universal computation."

It can't do it "per pixel". But it can compute arbitrary functions (which can be computed in finite time and memory) if given enough time (height) and memory (width).

I get "e is undefined" when I try to generate larger images.

except forthe fact that the width has to be declared in advance

also rule 110 requires a specific repeating background pattern for Cook's theorem to hold

which is a pattern that MA trees cannot generate

Why not?

because it's too wide

Define "too wide"

the repeating pattern looks like this

MA tree predictors can't generate that top row because they don't have properties that look back far enough

this pattern of "glider guns" is required for Cook's proof regarding rule 110

if you limit the time and memory, you can just hard code every output of the function?

The pattern is just a single pixel high. 110 never looks back (up) more than 1 pixel, the row above.

Yes, but Cook's proof requires you to start with that pattern

and the MA tree can't generate it

I can start with the pattern...

you can't generate it with an MA tree

Can you point to the precise technical limitation which forbids it?

Because I know how to encode arbitrary patterns. Is the tree depth limited or what?

I already explained, it's the same reason you can't have an MA output a pixel value of 1 every eight pixels and 0 otherwise

there is no property to look eight pixels to the left

I don't need it, I can write the pixels in manually

that's called residuals

at that point you're not computing anything, you're just putting data already there and calling it a day

That is what a program is, data.

what

programs are finite

what you're proposing would require you to hardcode in infinitely many residuals

The first line of pixels is the setup pattern, program and data. The lines below are generated by pxl

again, programs are finite

Well, `Width` many pixels

yes and cook's proof requires an infinite canvas

so if you're arguing that "rule 110 is turing complete" you need to look at the conditions for that proof you need an infinite canvas with an infinitely repeating background pattern laid out in advance

You can read his paper yourself if you'd like

https://wpmedia.wolfram.com/sites/13/2018/02/15-1-1.pdf

Look, I'm not claiming that turing machines according to the strict definition can actually exist.

that's not what I'm saying

I'm saying the MA tree model cannot generate the conditions laid out in that proof

and programs are finite

so being able to encode rule 110 doesn't actually mean much

My computer can't simulate a turing machine either....

also irrelevant

As a model of computation, MA trees are weaker than turing machines. That's all there is to it. There's things that an MA tree cannot do.

I listed one of them already.

This feels like if you tried to argue that you can program with discrete finite automata, and I pointed out a thing they can't compute and you went "well my computer isn't a turing machine"

so?

MA trees are expressive but there's many things they cannot do

No, 110 can encode a turing machine.

*with an infinite canvas and a specific repeating setup pattern*

a specific repeating setup pattern that, I remind you, MA trees cannot generate

per my last message

you can always hardcode in the pattern on a *finite* canvas, but not on an *infinite* canvas that would require you to *generate* it

I can't generate the pattern by describing it once, but I can write out the whole pattern by describing each pixel. The tree can grow without limits

no, the MA tree does not change

and you can't hardcode the pattern on an infinite canvas

only on a finite one

if you hardcoded the pattern on an infinite canvas, that would make your program inifnite in size. but programs are finite

I didn't say the tree could change

then what does "the tree can grow without limits" mean

And yes I can only encode finite trees

It means it can be arbitrarily large.

no, the tree is fixed in size

it will never be bigger than it started

I'm not saying it is grown by pxl, I'm saying a computer program can generate the pattern for the first row

not for an infinite canvas it can't

exactly

this matters because the canvas has to be infinite for Cook's theorem on rule 110 to hold

I've never said otherwise

you kept citing cook's theorem on rule 110

which require the canvas to be infinite

it's one of the hypotheses of the theorem

if the width is finite, then cook's theorem doesn't apply

You say that like all programs require infinite memory and time to run....

Cook's theorem about rule 110 specifically is a statement about an infinite canvas with a specific repeating pattern

so yes when I cite mathematical theorems that have hypotheses I don't try to apply them to situations where those hypotheses do not hold

MA trees cannot generate that repeating pattern (I already explained why) so you'd need to hardcode it, which doesn't work because programs are finite

and thus Cook's theorem can't be used

That's not really relevant since pxl images have finite size anyways.

indeed, and since their canvas sizes are *finite* we can't use Cook's theorem

So what is your point? pxl isn't programming because programming requires infinite memory?

no, it's not programming because *there's things it can't do*

being able to encode the rule for 110 *doesn't change this* because *rule 110 is not turing-complete on a finite canvas*

Well there's things C can't do either, so it isn't programming?

<:thonkery:853085697408499752>

I presented a specific thing it can't do, algorithmically, that turing machines can do

what else do you want me to say

it's not a turing-complete language because there's algorithmic deficiencies in it that cannot be overcome by better hardware or larger finite program sizes

it can't generate repeating patterns with large repeat distances

as one example

Like C then?

I don't see what you're getting at by bringing up C

Are you trolling me?

do you normally join random discords and ask technical mathematical questions and then when you don't like the answer you get accuse the person of trolling you

or is this your first time doing so

C is also not turing complete because integers in C are capped in size

but it has literally nothing to do with whether or not MA trees can compute specific things

it was never a competition with C

MA trees can't do these specific things that turing machines can do

that is all

some *fairly basic tasks* mind you, like determining if x is a multiple of 7

C lacking arbitrary-sized integers doesn't change this

"In colloquial usage, the terms "Turing-complete" and "Turing-equivalent" are used to mean that any real-world general-purpose computer or computer language can approximately simulate the computational aspects of any other real-world general-purpose computer or computer language."

yes, and MA trees are not able to do some very basic tasks like determine if x is a multiple of 7

that are pretty easily done on a turing machine or C or things accepted as turing-equivalent

I'm not being weirdly semantical here. I'm saying that some relaively ordinary tasks you'd want to do in computation can't be done with MA trees

like determine if x is a multiple of y, etc.

I agree that it isn't practically possible, if that is your whole point

my whole point is that MA trees are a weaker form of computation and some taks are simply impossible

relatively basic tasks

"is x a multiple of y" is not a question MA trees can answer

can C do it?

easily

Can 110 do it?

for arbitarily large input X?

with an infinite canvas and a specific repeating input pattern that MA trees can't generate

Can 110 do it with finite memory?

no

110 can't do much interesting if you don't give it an infinite canvas to work with

Ok then either you or I don't understand rule 110.

To me it sounds like the problem here is that you both cannot agree on a defiition of being roughly turing equivalent

well, no, not really

C can't handle arbitrarily large input for any problem because it's got fixed integer size but for anything that fits inside its integers, you can just do `y && (x / y) * y == x`

No, I would say the problem of C is not fied integer size, but fixed pointer size

You can represent the input as a string

pointers are integers

If 110 requires infinite pattern then it also requires infinite time. And then it will never give a return value...

And go well beyong the integer max

more specifically, it requires at least as much memory as runtime

if runtime is uncapped then memory is also uncapped

Your program will not look like y && (x / y) * y == x though

sure, I've laready pointed out that the limitation of C is that integers have finite size. this includes the fact that `sizeof(void *)` is a compile-time constant

pointer size being capped is the same problem

And similarily, whatever JXL thing you guys are talking about is also limited right?

well, no

How is that limitation different than the pointer size limitation of C?

wdym?

So 110 can do x % 7 with finite memory then....

except it can't

as I already mentioned

When X is `int` sized?

sure, but you can just hardcode that for all 2^32 values of that

my whole point is that MA trees are a weaker form of computation and some tasks are simply impossible relatively basic tasks If your point is that "well normal programming languages aren't turing-complete either" then sure they aren't but there's a real, pragmatic difference between the MA tree model and languages that are commonly accepted as turing-equivalent that is not pathological

How does that change things? Any function can be hardcoded if the input is limited

Well for me in C it is "close to turing complete" in that you can probably just modify a few lines to the spec to get true turing completeness

But it soundsl ike you could do the same for JXL right?

no

because MA trees lack the properties required

they can't backreference far enough

Like, if "X" flag is s, give me the infinite canvas or whatever you need for the rule 110 proof tow ork

the problem here is that the infinite canvas *also* requires a specific repeating pattern that the MA tree can't generate

it's like asking your C program to not only have infinite memory but a specifc (noncomputable) initial memory layout in that infinite space

sure if the initial layout is computable, you can always generate it on demand

but in this case the tool you use is not able to generate that initial memory layout

Yeah well X flag can do that too

X flag is not part of MA tree

it's a hypothetical pxl extension

in order for MA trees to be able to compute anything you'd need to start with an initial configuration that the method of computation cannot populate

Like, X flag can be spec'd to tell the decoder to execute as if the needed initial configuration is there

the problem is the initial memory space layout is not computable by the method of computation

Not by the tree, but pxl isn't just the tree

but like, in C even with infinite memory you couldn't compute busy beaver

you'd need it to be loaded into memory beforehand

which sorta defeats the point

I'm not trying to compute things C can't

that was addressed at kk

Well admittedly I don't know much about this rule 110 proof, but I'm assuming asking to load busy before into memory is not really the same as getting the decoder to start with whatever initial pattern is needed

it is equivalent if the computation method can't compute the initial pattern

an initial pattern that is incomputable by the method of computation without that pattern

Yes I agree I am adding to the computation method. But how is that different from giving C infinitely large pointers?

I can set `Width 1000` and I can write a tree that gives me any pattern I want for the top pixel row containing background pattern of width 1000, X, Y and an program for computing X % Y.

Though 1000 isn't actually enough.

I think there's no "Real" line you can draw for what is a reasonable addition

it's different because if you gave C infinite address space, it could conceivably compute anything a turing machine could, with a finite program but you can't make MA trees compute anything a turing machine can compute unless you populate the infinite address space with a precalculated initial pattern that the MA tree itself is not able to generate

that's the primary difference - it requires infinite input data that is not computable without it, with respect to the method of computation

wikipedia says "Repeating "patches" like text, dots, or sprites." are a feature of pxl

you keep saying pxl, I assume you mean JXL

and patches are frames that are overlaid

with a specific list of coordinates

they're not actually repeating

I mean jxl, yes 😸

they don't actually repeat, and they also don't affect MA prediction

or MA trees

I am not giving it infinite input data though. I am augmenting the computational model itself. I think that is the same as augmenting the address space of C

they're overlaid during frame composition after modular channels have been decoded

I'm not talking about jus the trees, I'm talking about JPEG XL

yes, but the computational model is *unable* to do everything a turing machine can do *unless* you populate its initial memory with something it can't compute

that's the difference

if you allow infinite memory but populate with zeroes, you can't compute certain things

such as "is x a multiple of y"

in that sense the model of computation is weaker than turing machines

I think you both are using the term *turing completeness* in somewhat different senses

But how do you even apply this rule in the example of C getting infinite memory? Why do the rules that get added have to do anything with the existing capabiltiies?

if you wanted to modify MA trees in a way that they could compute anything in a proper sense you'd need to add some feature that would allow them to populate repeating patterns across large distances

atm the only way to do that is by using lz77 on entropy residuals, which is outside the scope of the MA tree model

there is a dedicated term *bounded storage machine* that describes a FSM with limited storage but the storage can be arbitrarily extended to make it turing-complete in its limit

yes, and C is turing complete in this sense but MA trees are not

so JPEG XL can encode a (very inefficient) BSM, normal computer is a (good) BSM, C is also a (good) BSM

well JPEG XL can't encode a BSM because modular channels are fixed in width and height

that can be said to C as well, where it does have tons of other limits 🙂

I think the "limit" model of BSM will necessarily have to disregard such things

yes, but even if MA trees were extended to have infinite channel sizes you still don't get a turing complete machine in the limit

because you can't populate the initial memory required to make that work

you could if you rely on Lz77 of residuals

indeed, MA trees *themselves* are not enough to make it TM

but again that's outside the scope of the MA tree model

I carefully said "JPEG XL" above to avoid that pitfall

So have I, over and over

even then lz77 still wouldn't allow infinite repeats of the residuals

at best you increase the encoded size proportional to the log of the width

so you'll still end up with infinite program data required to generate that initial repeating pattern

I can do it explicitly, pixel by pixel.

which would constitute an infinite program

it will eventually depend on how you would generalize JPEG XL into arbitrary size

and programs are finite, as I have continued to remind you

Wrong. I have finite width, so the explicit descriptions of top row pixels is finite

for example, some scheme is considered a BSM even though itself doesn't have any looping mechanism (like JPEG XL here)

sure, but my point is that you'd still have residuals encoded scale with the log of the memory allocated which means that the limit of the bounded state machine creates infinite programs in the limit contrast with C where in the limit the program size stays finite

rigorously speaking the scheme *plus a trivial looping mechanism* is a BSM, but you know what you are saying

so it can be argued that JPEG XL plus a trivial extension would make a proper BSM

yea, you'd have to modify it in some way

being a file format there are tons of other issues to extend them, but that's to be expected and accounted for the BSM argument anyway

essentially if you modified lz77 to have a special wildcard to indicate infinite-length lz77 match then

that's what would be required

after all, the term bounded storage machine was invented by esolang community where a pure TM is not always achievable for wacky reasons

(I think there is a rigorous definition as well, but I never saw the term being that rigorously used anyway)

so there is a catch-all term for you all

Ok, but I think you are really depending right now on what is definition of something being "in the computational model" and what isn't. I would say that changing the rules of C to no longer have limited size pointers is as much as an addition as giving JXL a way of initializing with a repeating pattern. In neither case could the rule have been "simulated" but the original model... otherwise we would not be talking about them at all

As far as BSMs go, I think there is a point to be made that probably you could add a variable to the C spec N, and like yurume said, as N -> infinity, you get turing completeness, and perhaps this is not possible with the JXL spec

indeed, even as channel sizes grow without bound, program sizes would also have to grow without bound unless you added a way to loop inputs infinitely

you need a certain something else

just increasing channel size by itself isn't enough

"channel" means patterns from trees that can be at most 1024x1024?

Though I think the decision that there needs to be some variable you can pick out in the spec to call it a "Reasonable extension to turing completeness" is sort of arbitrary

channel in this case refers to one matrix of integers encoded by the modular stream

in practice, you have red, then green, then blue one after another

but that's not really important for this specific discussion

one-channel modular and N-channel modular is functionally equivalent for this purpose

basically the big thing you'd need is a special lz77 length

it would allow you to loop an entropy-coded stream infinitely many times with finite size

currently you can only do that if the stream has one symbol

if you could do that, then you could have an infinitely looping residual with a finite program size

which would solve all of the issues listed above

e.g. you could encode 0, 0, 0, 0, 0, 0, 0, 1 and then a "length = inf, distance = 8" lz77 pair

which atm you can't do

well I guess the technical details are sorted out then... but I guess you still think this is not a fair comparison to giving C an infinite pointer size?

(thanks, I don't know nearly enough about jxl to come up with that)

the reason I think it's not equivalent is one is adding a specific feature that is not present in any iterations of the bounded-state-machine and one is just a natural consequence of taking a limit as the size of the bounded-state-machine gets larger

Well, I can probably agree that in the current way JXL is specified, there is no "natural" value you could bind to "storage_size" in the definition of BSM to give turing completeness in the limit. But I guess that to me that is just a bit unsatisfactory as a guideline for what can be considered turing complete enough

Does https://jxl-art.surma.technology/ support images larger than 1024x1024?

the natural value is channel width and height

channel width being effectively "memory" and "height" being computation time

yes ...

The examples I see all seem to be 1024x1024 or smaller. Do you havea link for a larger image?

nope

Seems I'm not the first to make cellular automatons in jxl :)

What is the repeating bitstring for the top row for that pattern?

I'd have to dig deeper into the paper to find the generator

it is in the paper above, you can check though

I can't find that image in the paper

Unless that is part of figure 11?

page 22

according to wikipedia's article on rule 110 it's `00010011011111`

That doesn't include the gliders

I think if you start with that and repeat it does produce a form of glider

It produces the static between the gliders

https://jxl-art.surma.technology/?zcode=ldq9jhtHEATg_J6CL3DATv_M7CYODAhwpMSBXkBn6zIHF9hvb55PkOzzN4EYkctiEc1usKqm99Pz55cvt3FEPfzy9Pz7l5e35z8_v3x--uP1nYfn325_3X66HQ-32_3px69P3158enx9_Tj-ufB26fHjh2-Q18fj7denO-m718cPf2K8-9L_MzzuvuQ95Q995A7-8468_yqv2O-ob9fHfPj3F3y_3ht8bvA7_sP4Yxl_xAZP_uu6BL-uZfQ0Ook-T6JPc59t9IabZV7rInqV0eZeg-hp7ukqZxvNdl5t7l5Gm7tdZbvz5V6WuSuN3nC7ynTn071Mc4cnNswdrjLc-eFeDnMPT-zYcLvKw50_3MvD3Acn9rzIfV6n0W00e3me5j6X0eY-y2h2_lzs5bnMvdLoDbernOz8OcNoczcn9mxzt6tsdv4s97LMXW30httVpjuf7mWaOz2xYe5wleHOh3s5zD08sdbvc7hKq_d5uJeHuQ9P7LHhZpXLyr2uMJrc6-TELiv3OqfR7Pxa7OVa5l5t9IbbVVq51yyjzT05scvKvdpVWrlXu5dl7lpGm7tcpZV7pXuZ5s40esPtKq3cK9xL-_A1PLFW7mXTvqzc63Av7cDX4Yk9Ntysclq551VGp9Gc2Gnlnnbr08o9T_Zy2n_PtYw2t936tHLPyV5O--850-gNt6u0cs92L-2_Z3Fip5V72q1PK_dM99L-e2YbveF2lVbuGe6l_fcMT6yVe9qtTyv3dJCe9t_z8MRauafd-rRyt1N023_3lUZvuFllW7nbKbrtv3txYtvK3XbrbeVup-i2_-7ZRm-4XaWVu52i2_67mxPbVu62W28rdztFt_135zLa3HbrbeVup-i2_-7wxMaG21Vaudspuu2_-_DEWrnbbr2t3OUUXfbfdbXRG25WWVbucoou--86ObFl5S679bJyl1N02X_XXEab2269rNzlFF3239Vp9IbbVVq5yym67L8rObFl5S679bJyl1N02X9XeGJjw-0qrdzlFF323zU8sVbuslsvK3c5Raf9d17L6Da6jGbn0yk67b_zTKM33K7Syp1O0Wn_nZMTm1butFtPK3c6Raf9d3YbveF2lVbudIpO--8sTmxaudNuPa3c6RSd9t8Znlgrd9qtp5U7naLT_ju9-Mqx4XaVVu50ik777_DOK6zcYbceVu5wig777_DOK84NN6sMK3c4RYf9d3jnFVbusFsPK3c4RYf9d3jnFVbusFsPK3c4RYf9d3jnFbXhdpVW7nCKDvvv8M4rrNxhtx5W7nCKDvvv8M4rxobbVVq5wyk67L_DO69h5R5268PKPZyih_338M5rWLmH3fqwcg-n6GH_PbzzGmvD7Sqt3MMpeth_D--8hpV72K0PK_dwih7238M7r1Ebbldp5R5O0cP-e3jnNazcw259WLmHU_Sw_x7eeY3NPSt262N3x8rmhpjN_TC722E2d7f4Pg6v_r2d95Lbu2Ivf73n9GrM2ysvgbxL8XLEewAfHft014ekPmv04aHPyXy04tMPHyI4iztcO0c6ejgd2GTbq9p82mdZmq2eFiH_l_vP2f9DnF-OGbvGH4F1_Qf59e2_AQ

From `00010011011111`

The pattern is too short to contain the gliders

Rule 110 with a single 1 produces a triangle with a similar (but slightly different and noticeably shorter) pattern that grows to the left. Maybe the background pattern can also be grown in a similar way?

the tree or jxl doesn't need to be able to produce arbitrary repeating patterns in channels if a 1D cellular automaton (like 110 itself) can generate just the (a) correct pattern.

Actually, I think I solved how to make a pattern that repeats infinitely.

If you allow using an invisible extra channel (which you RCT-permute to the front), you could use it to record state and do things like that, since you can access values from previous channels from the MA tree. So you could have an "auxiliary computation" in one channel that produces sample values that cycle every N pixels, and in the next channel you can do conditional stuff based on that...

how do you actually get the cyclic values though

you could have it be fixed-width, sure, but how do you make it cycle

``` if x > 0 if W > 7 - Set 0 - W + 1 - Set 0 ```

Something like that will do

sure, but how does that make it repeat

like, that would make an increasing staircase

but you couldn't use that strategy to make an arbitrary specific pattern repeat

like, 0, 0, 0, 0, 0, 0, 0, 1

I believe to do that, you have to make the residuals repeat. the MA tree itself can't

Then in the next channel do ``` if Prev > 6 - Set 1 - Set 0 ```

ah, yea, you could do *that*

but how would you make an arbitrary pattern repeat

something, like, say, 00010011011111

Just a longer tree that hardcodes the whole pattern

But at some point you're better off just using lz77 🙂

ye, but lz77 can't infinitely repeat

that's the key

there's no special length value for "forever"

Infinitely enough, just set the length to the image dimension

well the thought experiment involved infinite-ly wide and infintely deep images

since you'd need that to try computation

you could always populate the tree upper-left out diagonally so it would still be able to be done

or rather, any pixel with finite coordinates would be reachable in finite time even if it's not in the first row

the fact that you have to declare the channel width and height in advance of the modular stream makes arbitrary computation not possible, so the thought experiment was what if you used the MA tree model on an infinite canvas

Anyway, about Turing completeness: no, jxl is by design not Turing complete (everything decodes in finite time so the halting problem is trivial). It's expressive though, and some kinds of generalizations would be TC.

ye, the idea was that on an infinite canvas with a specific repeating pattern populated in, rule 110 could simulate arbitrary turing machines (cook, 2004)

and since you can encode rule110 with MA trees fairly easily, you'd just need to be able to make that periodic initial state

the easiest way to do that is with periodic residuals, but the only way to have actual zero bpp (after initial overhead) is to have a single symbol with frequency 1.0

at least in the current entropy stream declaration

otherwise you're locked to something that scales with the log of the image width

which is still unbounded

Periodic initial state could be done with a first row that is just counting modulo the length of the pattern, and then a second row that fills in the pattern based on the value of N. And then the actual cellular automaton starts at row 3...

huh, I guess you could do that

requires you to leave the realm of binary

though I suppose that does work

But of course an infinite width image is not allowed by the spec. Largest you can do is via a palette metachannel (where the width is the number of palette colors), anything else is limited to the max group size of 1024.

ye, it was more of a thought experiment

in theory you could do an unbounded width and you could still populate each pixel in finite time, and populate all pixels in countable time

Yes, that was my idea. Doesn't have to be invisible but it's a bonus :)

So are you convinced now, now that I (and wb) solved arbitrarily repeating patterns?

JXL as it is is not Turing complete, by design, unlike some other formats that basically allow a full programming language with loops and all to be executed (like PostScript or SVG), which means security trouble since decoding an image might not terminate (so you need to sandbox it, with a timeout etc).

But the modular bitstream is very expressive and can represent a lot of things in asymptotically zero bits, including many types of cellular automata.

Yep. But the resulting image is, if given unbounded channel size. :D

**Qon** _“cellular automaton rule 110 repeating glider pattern for TM”_ 2024 image/jxl 355 bytes https://jxl-art.surma.technology/?zcode=ldixbttAEIThXk%2FBPiDA3bvjkU0KAwFSuUmhF7ATq0uhJm8fygqcgM5HwKqOooa%2FuNobzfJ8ebq%2BDDFlPX19vvx4ud7XD5fr0%2FPP25nT5fvwa%2Fi8LYZhWz5uy2lb3g%2FO4%2B14jNc37m%2BNj1%2FePnJ7jcO35%2BsQu%2BPpw4rYQd9fYRRkf8kPSv4U4O9dbwe11NP%2FvtvrqXLaX%2FDt1ERVrlRlt6pZ5W%2BYQVXMVIVZUaw6YLkaU6dqSqvIKusqVVm7VbNV%2FJXLslC1mLU0qw5YrEbp7KjSq1Vm9aBqNmt2NeZmFXujNLNat8qs5mo0d1R1b1SzarHqgOVqFHdUcW8Us9I7Jc1KVyPdUeHeCLPCOyUOWK7G5I6a3BuTWRN3Sq5k5bpY1axib%2BRi1jJbZdZilt0me7fKLHtUdnZvzr4vu03OxaoDlqvR2L3Z0iqzKndlVrPsUVnZvVnch3abLM2qA5ar4USUzjZpt8n0rgyz7FHpRJTONmm3yck7ZTLLHpVOROFsE3abWItVByxWI5yIwtkmFrM6d0p0s7qr4UQUzjYxmzU3qw5YroYTUTjbRDOrcadENau6Gk5EUX1fTkRhj4piluevsNuE56%2Fw%2FBX2qPD8FZ6%2Fwm4Tnr8iDliuhuev8PwVdhuPX56%2BbFCevTx62Wc8eHnusjU5BznQ2GE8cnnisik5ATnK2Fs8bHnWsh05%2BzjE2FXqwQMJP1nwUOy5x6OIE7uDrbOmw5X%2FP%2F2XZue3rdrpuE9ZalaNkHeK3YfO%2FzyV2z%2FNG7ezn4b4DQ%3D%3D

The pattern is 436 pixels wide so it doesn't repeat many times in an image with Width 1024 though.

The repeating pattern contains 3 gliders

The extra channel is not needed.

Arbitrarily wide and deep, infinite is not needed.

It works with `Bitdepth 1`, because the pixels can apparently hold larger values for computation until rendered.

**Qon** _“cellular automaton rule 110 with 00010011011111 repeating”_ 2024 image/jxl 56 bytes https://jxl-art.surma.technology/?zcode=C89MKclQMDQwMuHySM1MzyhRMDPhcsosSUktAIlzZaYpVCrYARkKCkCmH5BpAGRCOOG6IL6uIVgAIqTr5wpXAgK6CsGpJQqGaHwDknUYolmKaYIuLkvQjSRRCzQAEL4Gciy4sLkMKGHOhW4YVMIUlw5jXDqMMHSgKQoHRYsRFzb36wIltRUMAQ%3D%3D

`00010011011111` repeating

FramePos 0 -1 if you really don't like the top row not being part of the CA pattern below

The pattern starts with the leftmost pixel sliced off. Since it's a repeating pattern that doesn't really matter, the rightmost end will get sliced off if it's not a multiple of pattern width anyways.

And any repeating pattern can be rotated, it doesn't really have a true beginning or end.

it would have to be infinitely wide in the limit, because the "rule 110 computer" stops being a thing when it collides with the side of the image

unbounded runtime would requires unbounded menory

<@794205442175402004> Is FLIF and FUIF better for elementary cellular automata than JPEG XL? From your article it seems like they support larger images than 1024x1024, which is beyond the jxl channels. Or can you compose channels side by side have them interact in jxl?

FLIF/FUIF cannot do 0 bits per symbol, every symbol has a minimum cost of some small fraction of a bit (corresponding to a 4095/4096 chance). And their MA trees don't contain predictors in the leaf nodes so expressivity is much lower.

It just has to be wide enough. If the function requires infinite memory and never returns it doesn't actually perform an algorithm to compute a function.

1024x1024 is not a JXL restriction

But yes, FLIF/FUIF doesn't have tiling so you can do arbitrarily large CAs while in JXL you can only do 1024x1024 at a time (meaning the next row/column doesn't get predicted)

it's just the group size, yea

Like you can do it

but it's a practical format limitation

like having fixed size streams

That if you just want to talk about modular as a computation model, isn't that relevant

Groups are independent though, so e.g. for a cellular automaton every 1024th row will not see what's above it so it wouldn't compress well.

Ok. Why this limit? It seems to be for parallelization, but the encoder could just choose 1024 as channel W and H in that case. Would be nice for CA have arbitrarily large channels.

Sure, but that's a practical format restriction

not a restriction of the computation model

if you allow arbitrarily large image sizes as a thought experiment there's no reason the groupsize couldn't be tweaked

We wanted to keep a reasonably small limit so it is possible to make a chunked decoder that uses limited memory. 1 megapixel seemed a reasonable max chunk size.

Also to basically guarantee that for typical camera-sized photos, lossless decode can use at least a few cores even when using the biggest group size.

But of course this is something that could be generalized/relaxed to "no limit"

(well there's still the max image/frame dimension of 2^30 x 2^30, would have to relax that too I guess)

The decoder could decode rows with similar memory with 1M width, you would lose arbitrary chunk loading order and get sequential, but only for images that chose channels with large size.

I guess the format is frozen so there's not really any point to ask for features though q:

I mean, images of CA output will still compress insanely well even if one row and one column of 1024 pixels each per megapixel is not predicted. Still 99.8% of the pixels can be encoded using literally 0 bits per pixel.

(provided the tree learning figures out the CA rule)

Yeah sure, but I want to set Width to 2^20 at jxl-art.surma.technology and then have it just work :)

For generating jxl art. Sure the 1 Mpxl square chunks are good enough for image encoding from pixel data. But I'm not doing that, I'm just writing trees.

which is a big if 😛

Can it learn the rotation and flip as well? Or do ECA images growing up or left take orders of magnitude more space because the tree rules aren't aligned with the rules used to generate the images?

The encoding itself is always top to bottom, and libjxl isn't going to try different orientations. But if you have such an image, you can manually rotate/flip it so it becomes top-to-bottom, and then add some Exif orientation to the PNG input you give to cjxl to make it look the way you want again...

**silly goober** _“double flag”_ 2024 image/jxl 119 bytes https://jxl-art.surma.technology/?zcode=jVTLTsMwELz7K%2FZcCdW7ifO4cKCqxIkDIPVcaNJagqYSloC%2FJ6SO68em6S07k33NTvKgza45mQPk4nn1ClJs9K6PSOaVeGz0%2FmAAJeViuYBV9%2Fmmj1ujuyN0LZjvDtqP7f4LFkshdAu%2FcN%2FnA9hHhdgHLizqYgg9oLSAg8oSHeSB5IEOrggD2CMoIgDu4Gk9zJZk%2FPQZWNcJNZDvdqNJElnyv99LYyC7ylZimuOasjswoF2K8lpwpVHNlYgAWy%2FrTTCzv22A4gYZeYXS7YNhvMAem6QMXUUSY1eRkqmrSCHnqowU76qMCs5Vm2lXpaWuHGGyHAOOB1ZS3GhK9jAzHp%2B2MG%2FRZNAIGKeW4TuJGkGaC2z2GfcHiDY4UxREmI9%2Fp%2BEX5AygfCOVRRUaqabLB5qMySjNaMyqy%2BkaKhp0izpFXZIOcfVL5bHqHw%3D%3D

I'm gonna learn to jxl art, something might show up here soon

gosh, this is unintuitive

you mean what you get as you change the tree?

yeah

yup the long range effects can be pretty hard to predict

**Lonnie** _“Flag of Sweden”_ 2024 image/jxl 81 bytes https://jxl-art.surma.technology/?zcode=tZExDsIwDEV3n%2BJfAMmx2kIXBliYAYkD0ECzMWSA21OiNgpOQIDElv8i%2FbzYK%2Bc7e%2FE9FrRd78F0cN0jMdPGunPvUQ9HcifcsIRpWwLGICGEeI13CZAIAjoOiCOIyCQImGFnPUwzL1FuSDP%2B8QUpMa6yfqkretFfaC%2FZ5%2B6puWrNOrWtNk0t1R6yLfznB9%2F0Cr2b%2BfPEP5tMaqo9J8s7

Now the question, did I do anything non-optimal, so that this same result could be gotten from a smaller file?

it may be cheaper to do this with patches, but I don't know

Patches will be a lot cheaper once I want to do USA's flag, all those stars...

**\_wb\_** _“Flag of Sweden, 10 bytes shorter”_ 2024 image/jxl 71 bytes https://jxl-art.surma.technology/?zcode=tZCxDsIwDER3f8X9QCUnohVdGGBhYgAkPoAGmo0hA%2Fx9owiZJM4AA1vuObqzb%2BvD5B5hxoqOuzOYLn6Kas1Me%2Bfvc0Afn%2BRveGEDM44EvIVNIsmnzDJgBSR0jYgFCDIZAjqcXIDhBhyoJp9fHQ6iVFQjqBFTh%2BQRlaUy1Oske0uF7El1pZr6w%2FK%2FmGpPOaI449tKTN3JQGXcAg%3D%3D

nice! 77 bytes if you only change the tree structure, not the bit depth. The change in the the yellow is imperceptible, but the blue is different enough that I can tell even without putting the colors right next to each other.

hm, jxl_from_tree doesn't have any sort of patch support, does it?

nope — feel free to propose a PR to add that 🙂

Back when I was working on my later cancelled JXL decoder, I didn't get to the point where I had to figure out how patches work, so I guess I have some learning to do now.

<@794205442175402004> did you run it through libjxl or did you handcraft to optimize? And why?

handcraft, libjxl is unlikely to figure out trees like that

Can the answer for "why?" be "for the glory of Kingdom of Sweden of course"?

I'm gonna have fun making many flags in JXL, started with Sweden because that is where I am from :)

Because it is written to figure out local rules, like those in an ECA, instead of finding regions?

the current tree learning algorithm finds a single split decision at a time. Probably x/y coords aren't even considered as split properties until e9. The thing with greedy search is that it doesn't find a global optimum

the libjxl tree learning uses a greedy algorithm, it's not going to find trees as good as these ones 😄

like in that image: a single test on x or y is not really going to segment the pixels in a very useful way from the pov of entropy coding

this is one of the reasons why there is still significant potential in encoder improvements: less greedy tree learning could be quite beneficial also in the general case (I assume mostly for nonphoto though)

Would it find some regions though? Like a grid of 3x3 cells with borders on the color change?

Looking in the standard... Since jxl_from_tree already has support for multiple frames, I guess the first thing to add would be another header option to say that the current frame should be for reference only, and presumably something to say that a frame is cropped? And to use patches you'd have a new repeatable option with all the attributes a patch has. I think that data then needs to be entropy coded when put into a jxl file? And finally, it would be good to have some way of adding non-tree image data to a frame, in case the thing you want to use as a patch a hundred times doesn't work well as a tree.

it will likely figure out some useful rules that help a lot with entropy coding, with some special debug build you can make it output the tree if you really want to know what it does with a specific image (that's how I found a tree to reproduce the XOR pattern, I let libjxl find a tree and then simplified it because the greedy tree was not optimal and not fully zero-residual)

Yes — jxl_from_tree basically calls internal encoder functions directly so the way to do it would be to add some way to pass patch coords to the encoder (via some vector in cparams or something) and then override patch detection to just pretend it detected the passed patches so it writes them to the bitstream. It's a bit of a tricky code plumbing exercise though

I've never used C++ for anything ever, so that will be fun.

So it's pretty simple to create vertical, horizontal, or diagonal boundaries with the N, NW, W, etc, predictors, but is there a simple way of doing other angles?

https://jxl-art.surma.technology/?zcode=c8osSUktKMlQMOTKTFOoVLBTMOBSUNBV8ANiQwgzXEFbwRAA

I haven't figured out layering yet, but I think it can be done?

I suppose it should be possible to do at least angles in between of the form ``` 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 ``` or ``` 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 ``` with some suitable test involving WW or NN or something

My method allows any angle

But needs more on top to make it useful

yes that kind of thing works too, cannot really do a sharp line between two arbitrary colors that way though

Thought I could use Prev for that, but those are on color channels not frames

although I guess you could use that in the alpha channel and use layers with clamped alpha, or something

Exactly

I haven't figured out layering, but if layers can be read than you can test and filter with those angled sheets

for the sharp lines

Splines should be able to do arbitrary lines as well, or are they missing some feature to be useful for this?

**Qon** _“arbitrary angles + repetition”_ 2024 image/jxl 34 bytes https://jxl-art.surma.technology/?zcode=c8osSUktKMlQMOTKTFOoVLBTMOBSUNBV8ANiCwMIAAuEK2grGEMFAA%3D%3D

neato

the belgian flag is a testcase in the ffmpeg fate suite

png? My browser does not yet support .jxl <:SadOrange:806131742636507177>

I'm looking at the code now and I'm seeing that there are a lot of options not explained on Surma's jxl-art site's help page

ye, documentation could be improved

this is creating an interesting optical illusion

I keep seeing rainbows that aren't there

perpendicular to the diagonal lines

https://jxl-art.surma.technology/?zcode=c8osSUktKMlQMOEKz0wB0hYGBlweqZnpGSUKpkCmY05BRiKXX36JT2JxCRdXZppCsoKdghGXgoKuQnBqiYKhKZAJFTUEMuHiBmAOVAbCgcmZofAMUEyvBJluacmFkAUbAhI2BAvDzTRCMQXsDiRZQygX2RwUBQgBuBFGmEKmXMhGALVWYHdfxaBwHwA Fläg öf Sweden, 14 bytes longer I just wanted to try layers.

Ah, cool

background color is specified once, each yellow line is specified once

Yeah it kind of messes with your eyes a bit

A bit hard to focus on as well

And going closer/farther from my display and it looks like it compresses and expands.

As a Belgian, I approve.

I did it cause it was a random piece of JXL art I had on file at the time <:kek:857018203640561677>

Also I keep being amazed at how our flag is just the French flag with the blue channel removed.

... I hate that

that's so accurate

We're basically just a smaller, warmer "night shift color theme" version of France, I guess.

**Qon** _“Flag of USA w/o stars”_ 2024 image/jxl 100 bytes https://jxl-art.surma.technology/?zcode=ZVBBDsIgELzvK%2FYDJkChlIuJnjyYxsSD58aikJi0UWL091JCpdADYWdmZ2dhb12vR2ewgYvt%2FU0J43DQ9m4cikrB7jGaDtrBHbuXA7A3vOIWGSBu8KwdMiF8HWnqy1moeQBRIQHMGpU5bGiW8I2GRVgAp6d%2BTzhEJnuJSdyi9UdQqbhQNSRxSvj4MZwoWFpiMFMEylnZIuvY7PWpQck%2FUfxC6uFiRVU%2F

Making stars is tricky...

hopefully I'll get patches working soon :p

If I could read previous frames and have more access to blend modes I might be able to write the tree equations...

It uses the stripes trick to keep bytes down

looking at the code, blendmodes can be accessed, even though it isn't documented (and the surma site appears to be using a new enough version) ```c++ } else if (t == "BlendMode") { t = tok(); if (t == "kAdd") { io.frames[0].blendmode = BlendMode::kAdd; } else if (t == "kReplace") { io.frames[0].blendmode = BlendMode::kReplace; } else if (t == "kBlend") { io.frames[0].blendmode = BlendMode::kBlend; } else if (t == "kAlphaWeightedAdd") { io.frames[0].blendmode = BlendMode::kAlphaWeightedAdd; } else if (t == "kMul") { io.frames[0].blendmode = BlendMode::kMul; } else { fprintf(stderr, "Invalid BlendMode: %s\n", t.c_str()); return false; } } ```

<@265247121261854722> I noticed your thinking reaction. Here is an example showing how to set blendmodes: https://jxl-art.surma.technology/?zcode=ZVDLDoIwELzvV-wPmLSlBXoxkZMHISYePBNbhUiEaDX695amUB6Hpjs7uzOTzWqjdGcqTOFcK_tTwjjsdX2rDIpIwq7pqhKK1hzKlwGor3jBLTJA3OBJG2RC2Nq3qS0HIuYOeIY4MHA0mcOUjg5Zox8qb5XGe_5uer-fX59YO3B86k-PXYAgtsTEZyrsEzSRXMgYAjnxc2Xv-LWynEiYSvggTBJYas-CrWPMbhMGZDI2FjcKM1ysWtEf

Thanks! <:FeelsReadingMan:808827102278451241> <:BlobYay:806132268186861619>

It seems that if you set a blend mode on a frame, all later frames get that blend mode unless you set a new one.

I'm a bit confused by something. These tree files behave opposite of what I would expect: ``` Bitdepth 2 RCT 0 NotLast - Set 1 - Set 3 ``` ``` Bitdepth 2 RCT 0 NotLast - Set 3 - Set 1 ``` my expectation is that the first tree goes into the first frame, and that then the second tree goes into the second frame which gets drawn on top of the first frame. So the first example should have a gray first frame, and a white second frame, and the final image should be white. And I expect the second example to have a white first frame, a gray second frame, and a grey final image. But I observe the opposite of this. If I add `Alpha`, the second example continues to be pure white, and the first examples becomes a lighter gray, further making it seem like the first tree is the second frame.

the documentation makes it seem like its behaving backwards 🤔 > NotLast: This is not the last frame/layer (not enabled by default). This flag can be used to do multi-layer images. After encoding this layer, another layer will be encoded, which gets alpha-blended over the first layer

yeah, no matter how I set the alpha values in this one, it never outputs a red image. Only blue or white. ``` Bitdepth 1 RCT 0 NotLast Alpha if c > 2 - Set 1 if c > 1 - Set 1 - Set 0 if c > 2 - Set 1 if c > 0 - Set 0 - Set 1 ``` is there something obvious I'm missing?

On Surma's website, it works as I would expect...

that uses v0.7 so I guess I'm in for another bisection

it's also red on https://embed.moe/jxl_from_tree end of 2022

I can at least confirm that a version of libjxl from the middle of 2022 worked correctly

the streaming encode refactoring probably messed up jxl_from_tree in more than one way

This problem was caused by an older change, in November

When tests and jxl_from_tree were changed to use cparams instead of PassesEncoderState

Is there a (mathematical and/or text) description for each blend mode. kMul is easy enough to understand from name, but not all have the same as a blend mode in other software. And not many modes to choose from.

there's the code and the spec, I guess

https://github.com/libjxl/libjxl/blob/6c0b3106a8a1ef65ba36c24bfcd9402c3140ae2d/lib/jxl/blending.cc#L32 code

Thanks. Is there a link to spec also?

unfortunately nothing I can share 😦

Ooh this pic shows kAdd, which wasn't in the previous snippet and didn't see it at first in source. And kMulAdd isn't in source. But kAdd seems to work so that's something

kMulAdd has to be somewhere in the source xD

It's called kAlphaWeightedAdd in the source

ah, right, we might have renamed it at some point, presumably to make things clearer

the spec must be from before the rename

**Qon** _“BW Star”_ 2024 image/jxl 410 bytes https://jxl-art.surma.technology/?zcode=zZVLT8MwDMfv%2BRS%2Bo0h5OskFaZy3CYkD54kWgag2BB2Cb0%2B6PvJoVXpBa0%2F5O67tn%2By6m%2Br95UD2p3p7%2BKwJeX2GJ7gFQQAoPJQ1CK2HM0v8vr2f5tzfevHjhdTGi%2BDcnLurVlxkH34w3H%2BUX43tkqh%2F4uSpjZGg93ADVGiMwrdVicjp0TsZa5GkcSSziLNogsQ51wbJMkQ6wagYWsFwxCYlm2LThl%2BBbQEatygzNGoVWmmXoyU4Pen1muWYy4gEMmeFSzqwcCgHthhlGmSMkUJkPcnqb6uP2tE1QxgtjeLz%2B%2BHfqwzf%2FXhuukK5cU6ZuZWGTq5mbNCpfJFNzI3LN9IUWih%2FldOjHIbpuavKY7E7FSW87c7VHz8l2ojojU1REBLcfgE%3D

Wow, nice one!

it makes for a good frame blending exercise for jxl-oxide <:kek:857018203640561677>

jxlatte and jxl-oxide both decode this in ~1.6s on my machine

jxlatte is very much not optimized so I'd expect jxloxide to do better

Might not be a valid bitstream though, technically speaking. Seems to use more than the int16 range which a containerless jxl is allowed to use (not that anyone checks that)

it takes advantage of 32-bit wraparound

however all three decoders decode it to the same PNG

**Qon** _“BW 5 point Star, inverted blend shown”_ 2024 image/jxl 445 bytes https://jxl-art.surma.technology/?zcode=zZU9T8MwEIZ3%2FwrvKNL562wvSGWmFRIDc0WCQEQUQUDw73GbOP6IG2VBTSaffbLfJ%2B%2F5vGnfn%2Fdkd%2Bhu958dIS9P9JFeU04oreh901Gu1DiGJO%2FH5SnG3KoLfl0glHZBSD6Oh6U%2BOIV%2B%2B3Hi7qP5Ps6dDvJffHg6ByTEO3pFK64w2r5XxaOkB5ekjUGS7iPAIM6icRKfuTZIyBCrAqMENBxwwiYElNiUZhdgW4DGDIoMrTISjTDL0RIcT3o5syzYjIgjWMNt4sDCohzZYpQyyBQjhcg8yfT36iM7BjO4VkJLNt8f%2Fl1luPfTuhmEMm2t1HMtDa1YTdmglXkjK9SNzTtSCS3IX2X1SIuhem7a5q3eHuqGvm6%2F2tEZzfJnyd95xmKXdFQGqVzfwxmLfUuNnLOsOv8vQhSp39R1UT0s1g7nlc974cd%2F

^ I made the star by making the outside white and then inverting, so I made another image where the inverted region doesn't cover the whole image to show that

The multi-line images (american flag, BW arbitrary angle + repeat demo) use int overflow. The star doesn't go that high for any pixel to wrap around.

oh, I must have miscounted digits then

in either case it's still strictly speaking noncompliant because it goes above 16-bit buffer sizes

which you can't do without level10

but all the decoders work with it just fine

I need larg~ish numbers to get rid of gradients at the borders. I want to go from 0 or less to hit at least 255 from one pixel to next