9 ms·
JPEG XL would be Turing-complete without the 1024×1024 pixel limitation
- tomxor 5y agoInteresting, sounds like a code golfing challenge to me... what interesting "programs" can you fit in a 1024*1024 cell 110 1d automata.
- slver 5y agoCode Golfing challenge: - Write an efficient Bitcoin miner that runs in a JPEG. - Steal the memory of a user using the Spectre vulnerability.
- tiborsaas 5y agoGenerative art is interesting in itself, so plenty of nice images can be encoded. I've checked JPEG-XL Discord channel and there's a small group of people creating these images for fun.
- doodpants 5y agoGenerate an image which is itself a fully functional program writen in the Piet esolang[1]. [1] https://www.dangermouse.net/esoteric/piet.html https://www.dangermouse.net/esoteric/piet.html
- yarg 5y agoI love it when my image formats suffer from the halting problem.
- dTal 5y agoThey don't - there is a maximum of 1024 steps. FTA: "To help with parallel decoding, JPEG XL decoders work on slices of images 1024 by 1024 pixels in size. So JPEG XL itself isn't Turing-complete; a version of it without the 1024×1024 pixel limitation would be."
- sonthonax 5y agoI mean, by that very very strict definition nothing is Turing complete since no machine has infinite memory.
- Dylan16807 5y agoNo, there is a big difference between "this runs a fixed number of steps" and "this runs until it halts with an upper bound of 2^enormous" "2^enormous" not actually being infinity will never matter. "fixed number of steps" doesn't even start to resemble infinity.
- dTal 5y agoTo expand on this - the practical difference is "can be executed hundreds of times over in a timespan imperceptible to humans" and "will not terminate in a trillion times the age of the universe."
- wizzwizz4 5y agoA trillion times the age of the universe? How quaint; you're using durations that humans can, in principle, conceive of. --- Edit: I'm being ridiculous; the below assumes a Turing machine with infinite tape, with the restriction that it must halt eventually, simulated by a PC. That's not real. Absent an infinite Turing tape, the number of states a computer can have is very finite; 2^(amount of memory). Assuming 16GiB of RAM and no hard drive, that's 2^2^30 states. Assuming a state transition happens every clock cycle (which it basically would be for a naïve counter – though obviously if you were designing a program to run as slowly as possible, you wouldn't do it this way), and assuming a massively-overclocked 10GHz chip (2^33 Hz or thereabouts), it'd run for 2^(2^30 - 33) seconds. The CMB will probably be undetectable in about 2^62 seconds, so it'd run for 2^(2^30 - 95) times that length of time. Vastly, vastly shorter than my below estimate!! --- https://waitbutwhy.com/2014/11/1000000-grahams-number.html https://waitbutwhy.com/2014/11/1000000-grahams-number.html Graham's number is g_64. Don't take g_1000; rather, take g_g_g_g_g_g_g_…g_g_64 Graham's number times, and then repeat that Graham's number times, and that's probably not an upper bound; the complete description of that number fits in your computer's memory. Whatever the limit of a computer program's execution time, it's definitely large enough that it doesn't really need a unit; it's practically irrelevant whether you measure it in yocto-Planck-times or yotta-heat-deaths, or even just count the digits.
- de6u99er 5y agoFrom linked article > Since Rule 110 is Turing-complete, this seems to prove that JPEG XL predictors are themselves Turing-complete — except they are not!
- jerryX 5y agoWhat virus can be implemented in that?
- jonsneyers 5y agoThe only 'virus' you could implement would be just a weird-looking image.
- slver 5y agoImagine I use a timing attack to visually encode some information about you in an image and trick you into sending a screenshot somewhere. Very quick take, but systems are very interconnected these days, so sandboxes tend to leak in very unintentional ways.
- jonsneyers 5y agoYes, that is true, but it isn't particularly related to JPEG XL specifically.
- KMag 5y agoHow do you read a timer from within the JPEG XL bitstream? I believe the decoding process is deterministic.
- slver 5y agoIt's a challenge, but I'd probably look into any decoders that parallelize the decoding and see if I can abuse this.
- ohazi 5y agoThis is not as suggestive as one might imagine given the title or the discussion here so far. It's not "Turing machine but the tape is limited to 1024 cells" - i.e. you don't get 1024 units of memory and a conditional branch instruction. You can't branch at all. In order to simulate the Turing machine, you need to run the Rule 110 automation, which necessarily implies expanding linearly into that 1024 cell space - i.e. your simulated program really isn't going to get very far. Edit: see comments by dTal and Dylan16807