Day: August 5, 2024

Proof That find + mkdir Are Turing-Complete

August 5, 2024 by 10 Comments

Data manipulation is at the heart of computation, and a system is said to be Turing-complete if it can be configured to manipulate data in a way that makes implementing arbitrary computation possible. [Keigo Oka] shared a proof that find and mkdir together are Turing-complete, which is to say, a system with only GNU’s find and mkdir has access to enough functionality to satisfy the requirements of Turing completeness, which ignores questions of efficiency or speed.

[Keigo Oka]’s first attempt at a proof worked to implement Rule 110, an elementary cellular automata configuration that has been shown to be Turing-complete, or ‘universal’, but has been updated to implement a tag system as it’s proof, and you can see it in action for yourself.

Seeing basic utilities leveraged in such a way illustrates how computation is all around us, and not always in expected places. We’ve also seen Turing-complete origami and computation in cellular automata.

At Last, Chumby Is Ready

August 5, 2024 by 14 Comments

It has been two years, but the slow and steady progress that [Doug Brown] has been making towards bringing a modern Linux kernel to the Chumby has approached the point that it could be called done. In his final blog post of the series, [Doug] walks through the highs and lows of the whole process.

Many of the changes [Doug] and others have made are already upstream in the Linux mainline. However, some will likely remain in private branches for a few reasons that [Doug] gets into. The blog post covers every commit needed to turn a Chumby or other Marvell ARMADA-powered widget into a working device. At the end of the day, what does [Doug] have to show? He can turn it on, see a boot logo, and then see an indefinite white screen. While underwhelming to most of the world, an X server is coming up, Wi-fi is online, the time syncs from an NTP server, and the touchscreen is ready to be tapped. A white screen, yes, but a white screen of potential. [Doug] has to decide what to launch after boot.

However, the future of the Chumby and other older devices is still on the chopping block of progress. Compiler writers want to drop support for platforms that nobody uses anymore, and the Chumby is ARMv5. With many changes destined to languish, [Doug] still considers it a huge success, and we do too. The whole series represents a journey with beautiful lessons about the power of the Linux device tree, making the dark and scary world of Linux kernel drivers seem a little more approachable.

We’ve covered the first post and when graphics started coming along. We salute the mighty Chumby and the idea it stood for. Of course, the idea of a handy screen displaying information is still alive and well. This handy e-paper HomeAssistant display is just one of many examples.