5 ms·

I love it when my image formats suffer from the halting problem.

by yarg 5y ago

dTal 5y ago
They 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 ago
  I mean, by that very very strict definition nothing is Turing complete since no machine has infinite memory.
  - Dylan16807 5y ago
    No, 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 ago
      To 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 ago
        A 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.
        dTal 5y ago
        > How quaint; you're using durations that humans can, in principle, conceive of. You'll have to forgive me I'm afraid - I was writing for an audience of mostly humans :)
  - dTal 5y ago
    "Always halts after 1024 steps or fewer" is a rather stricter constraint than "halts after BB(2^10^12) steps". https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver
  - penteract 5y ago
    Turing completeness is a property of a language, not an implementation. There are programming languages where a bound on memory is not part of the spec. Those are Turing complete even if there can be no perfect implementation of them.
- MaxBarraclough 5y ago
  <pedantry-mode> Isn't that like saying C++ templates aren't Turing complete on account of recursion depth limits? </pedantry-mode> edit sonthonax beat me to it
- jonsneyers 5y ago
  Even without that limitation, it wouldn't really be Turing complete since images need to have a finite dimension, which makes the halting problem trivial (everything halts when all finitely many pixels are decoded). Then again, no real computer is Turing complete because they all have finite memory so they're strictly speaking only big finite state machines (though we do typically consider them Turing complete anyway). I think the main point here is that the context/prediction model of JPEG XL's modular mode is expressive enough to consider it a kind of mini-programming language which is 'Turing-complete' (with some asterisks like requiring infinite images). It's not a security risk though: the decode computation per pixel is still bounded, so there is no way to make the decoder go into an infinite loop or anything like that. In that respect it's (intentionally) not Turing complete, unlike some other image formats like PostScript and SVG that do have actual programming languages in them that can cause a decoder/interpreter to go into an infinite loop (safe handling of such files does require sandboxing and time-outs).
  - SuchAnonMuchWow 5y ago
    > Then again, no real computer is Turing complete because they all have finite memory so they're strictly speaking only big finite state machines Interestingly, cloud computing made this limitation less obvious: one can imagine a program running on the cloud that bill the cloud provider when it runs out of disk space. And the cloud provider will buy more hard drives for its servers when needed. There is still obviously a limit somewhere, but its much farther ahead, because its more limited by factors such as how much hard drives we can build.
    - deleted 5y ago
      [deleted]
    - jonsneyers 5y ago
      Let me rephrase: the observable universe is strictly speaking not Turing-complete :)
      - strbean 5y ago

I love it when my image formats suffer from the halting problem.

by yarg 5y ago

I love it when my image formats suffer from the halting problem.

dTal 5y ago

They 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 ago
I mean, by that very very strict definition nothing is Turing complete since no machine has infinite memory.
- Dylan16807 5y ago
  No, 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 ago
    To 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 ago
      A 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.
      - dTal 5y ago
        > How quaint; you're using durations that humans can, in principle, conceive of. You'll have to forgive me I'm afraid - I was writing for an audience of mostly humans :)
- dTal 5y ago
  "Always halts after 1024 steps or fewer" is a rather stricter constraint than "halts after BB(2^10^12) steps". https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver
- penteract 5y ago
  Turing completeness is a property of a language, not an implementation. There are programming languages where a bound on memory is not part of the spec. Those are Turing complete even if there can be no perfect implementation of them.
MaxBarraclough 5y ago
<pedantry-mode> Isn't that like saying C++ templates aren't Turing complete on account of recursion depth limits? </pedantry-mode> edit sonthonax beat me to it
jonsneyers 5y ago
Even without that limitation, it wouldn't really be Turing complete since images need to have a finite dimension, which makes the halting problem trivial (everything halts when all finitely many pixels are decoded). Then again, no real computer is Turing complete because they all have finite memory so they're strictly speaking only big finite state machines (though we do typically consider them Turing complete anyway). I think the main point here is that the context/prediction model of JPEG XL's modular mode is expressive enough to consider it a kind of mini-programming language which is 'Turing-complete' (with some asterisks like requiring infinite images). It's not a security risk though: the decode computation per pixel is still bounded, so there is no way to make the decoder go into an infinite loop or anything like that. In that respect it's (intentionally) not Turing complete, unlike some other image formats like PostScript and SVG that do have actual programming languages in them that can cause a decoder/interpreter to go into an infinite loop (safe handling of such files does require sandboxing and time-outs).
- SuchAnonMuchWow 5y ago
  > Then again, no real computer is Turing complete because they all have finite memory so they're strictly speaking only big finite state machines Interestingly, cloud computing made this limitation less obvious: one can imagine a program running on the cloud that bill the cloud provider when it runs out of disk space. And the cloud provider will buy more hard drives for its servers when needed. There is still obviously a limit somewhere, but its much farther ahead, because its more limited by factors such as how much hard drives we can build.
  - deleted 5y ago
    [deleted]
  - jonsneyers 5y ago
    Let me rephrase: the observable universe is strictly speaking not Turing-complete :)
    - strbean 5y ago