<story><title>JPEG XL would be Turing-complete without the 1024×1024 pixel limitation</title><url>https://dbohdan.com/wiki/jpeg-xl?</url></story><parent_chain></parent_chain><comment><author>ohazi</author><text>This is not as suggestive as one might imagine given the title or the discussion here so far.&lt;p&gt;It&amp;#x27;s not &amp;quot;Turing machine but the tape is limited to 1024 cells&amp;quot; - i.e. you don&amp;#x27;t get 1024 units of memory and a conditional branch instruction. You can&amp;#x27;t branch at all.&lt;p&gt;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 &lt;i&gt;really&lt;/i&gt; isn&amp;#x27;t going to get very far.&lt;p&gt;Edit: see comments by dTal and Dylan16807</text></comment>
<story><title>JPEG XL would be Turing-complete without the 1024×1024 pixel limitation</title><url>https://dbohdan.com/wiki/jpeg-xl?</url></story><parent_chain></parent_chain><comment><author>yarg</author><text>I love it when my image formats suffer from the halting problem.</text></comment>