Proof That find + mkdir Are Turing-Complete

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.

Even More Firmware In Your Firmware

There are many ways to update an embedded system in the field. Images can fly through the air one a time, travel by sneaker or hitch a ride on other passing data. OK, maybe that’s a stretch, but there are certainly a plethora of ways to get those sweet update bytes into a target system. How are those bytes assembled, and what are the tools that do the assembly? This is the problem I needed to solve.

Recall, my system wasn’t a particularly novel one (see the block diagram below). Just a few computers asking each other for an update over some serial busses. I had chosen to bundle the payload firmware images into the binary for the intermediate microcontroller which was to carry out the update process. The additional constraint was that the blending of the three firmware images (one carrier and two payload) needed to happen long after compile time, on a different system with a separate toolchain. There were ultimately two options that fit the bill.

The system thirsty for an update

Continue reading “Even More Firmware In Your Firmware”

Putting The Firmware In Your Firmware

Performing over-the-air updates of devices in the field can be a tricky business. Reliability and recovery is of course key, but even getting the right bits to the right storage sectors can be a challenge. Recently I’ve been working on a project which called for the design of a new pathway to update some small microcontrollers which were decidedly inconvenient.

There are many pieces to a project like this; a bootloader to perform the actual updating, a robust communication protocol, recovery pathways, a file transfer mechanism, and more. What made these micros particularly inconvenient was that they weren’t network-connected themselves, but required a hop through another intermediate controller, which itself was also not connected to the network. Predictably, the otherwise simple “file transfer” step quickly ballooned out into a complex onion of tasks to complete before the rest of the project could continue. As they say, it’s micros all the way down.

The system de jour

Continue reading “Putting The Firmware In Your Firmware”

Will The Real UNIX Please Stand Up?

Ken Thompson and Dennis Ritchie at a PDP-11. Peter Hamer [CC BY-SA 2.0]
Ken Thompson and Dennis Ritchie at a PDP-11. Peter Hamer [CC BY-SA 2.0]
Last week the computing world celebrated an important anniversary: the UNIX operating system turned 50 years old. What was originally developed in 1969 as a lighter weight timesharing system for a DEC minicomputer at Bell Labs has exerted a huge influence over every place that we encounter computing, from our personal and embedded devices to the unseen servers in the cloud. But in a story that has seen countless twists and turns over those five decades just what is UNIX these days?

The official answer to that question is simple. UNIX® is any operating system descended from that original Bell Labs software developed by Thompson, Ritchie et al in 1969 and bearing a licence from Bell Labs or its successor organisations in ownership of the UNIX® name. Thus, for example, HP-UX as shipped on Hewlett Packard’s enterprise machinery is one of several commercially available UNIXes, while the Ubuntu Linux distribution on which this is being written is not.

When You Could Write Off In The Mail For UNIX On A Tape

The real answer is considerably less clear, and depends upon how much you view UNIX as an ecosystem and how much instead depends upon heritage or specification compliance, and even the user experience. Names such as GNU, Linux, BSD, and MINIX enter the fray, and you could be forgiven for asking: would the real UNIX please stand up?

Continue reading “Will The Real UNIX Please Stand Up?”

Hackaday Links Column Banner

Hackaday Links: September 22, 2019

Of all the stories we’d expect to hit our little corner of the world, we never thought that the seedy doings of a now-deceased accused pedophile billionaire would have impacted the intellectual home of the open-source software movement. But it did, and this week Richard Stallman resigned from the Computer Science and Artificial Intelligence Lab at MIT, as well as from the Free Software Foundation, which he founded and served as president. The resignations, which Stallman claims were “due to pressure on MIT and me over a series of misunderstandings and mischaracterizations”, followed the disclosure of a string of emails where he perhaps unwisely discussed what does and does not constitute sexual assault. The emails were written as a response to protests by MIT faculty and students outraged over the university’s long and deep relationship with Jeffrey Epstein, the late alleged pedophile-financier. This may be one of those stories where the less said, the better. If only Stallman had heeded that advice.

They may be the radio stations with the worst programming ever, but then again, the world’s atomic clock broadcasting stations can really keep a beat. One of the oldest of these stations, WWV, is turning 100 this year, and will be adding special messages to its usual fare of beeps and BCD-encoded time signals on a 100-Hz subcarrier. If you tune to WWV at 10 past the hour (or 50 minutes past the hour for WWVH, the time station located in Hawaii) you’ll hear a special announcement. There was also talk of an open house at the National Institute of Standards and Technology complete with a WWV birthday cake, but that has since been limited to 100 attendees who pre-registered.

For the machinists and wannabes out there, the Internet’s machine shop channels all pitched in this week on something called #tipblitz19, where everyone with a lathe or mill posted a short video of their favorite shop tip. There’s a ton of great tip out there now, with the likes of This Old Tony, Abom79, Stefan Gotteswinter, and even our own Quinn Dunki contributing timesaving – and finger saving – tips. Don’t stop there though – there’s a playlist with 77 videos at last count, many of them by smaller channels that should be getting more love. Check them out and then start making chips.

Most of us know that DLP chips, which lie behind the lens of the projectors that lull us to sleep in conference rooms with their white noise and warm exhaust, are a series of tiny mirrors that wiggle around to project images. But have you ever seen them work? Now you can: Huygens Optics has posted a fascinating video deep-dive into the workings of digital light processors. With a stroboscopic camera and a lot of fussy work, the video reveals the microscopic movements of these mirrors and how that syncs up with the rotation of a color filter wheel. It’s really fascinating stuff, and hats off to Huygens for pulling off the setup needed to capture this.

And speaking of tiny optics, get a load of these minuscule digital cameras, aptly described by tipster David Gustafik as “disturbingly small.” We know we shouldn’t be amazed by things like this anymore, but c’mon – they’re ridiculously tiny! According to the datasheet, the smaller one will occupy 1 mm² on a PCB; the larger stereo camera requires 2.2 mm². Dubbed NanEye, the diminutive cameras are aimed at the medical market – think endoscopy – and at wearables manufacturers. These would be a lot of fun to play with – just don’t drop one.

The Eric Lundgren Story: When Free Isn’t Free

At this point, you’ve almost certainly heard the tale of Eric Lundgren, the electronics recycler who is now looking at spending 15 months in prison because he was duplicating freely available Windows restore discs. Of no use to anyone who doesn’t already have a licensed copy of Windows, these restore discs have little to no monetary value. In fact, as an individual, you couldn’t buy one at retail if you wanted to. The duplication of these discs would therefore seem to be a victimless crime.

Eric Lundgren

Especially when you hear what Eric wanted to do with these discs. To help extend the functional lifespan of older computers, he intended on providing these discs at low cost to those looking to refurbish Windows computers. After each machine had its operating system reinstalled, the disc would go along with the computer in hopes the new owner would be able to utilize it themselves down the road.

It all sounds innocent enough, even honorable. But a quick glance at Microsoft’s licensing arrangement is all you need to know the whole scheme runs afoul of how the Redmond giant wants their operating system installed and maintained. It may be a hard pill to swallow, but when Eric Lundgren decided to use Microsoft’s product he agreed to play by their rules. Unfortunately for him, he lost.

Continue reading “The Eric Lundgren Story: When Free Isn’t Free”

The GNU GPL Is An Enforceable Contract At Last

It would be difficult to imagine the technological enhancements to the world we live in today without open-source software. You will find it somewhere in most of your consumer electronics, in the unseen data centres of the cloud, in machines, gadgets, and tools, in fact almost anywhere a microcomputer is used in a product. The willingness of software developers to share their work freely under licences that guarantee its continued free propagation has been as large a contributor to the success of our tech economy as any hardware innovation.

Though open-source licences have been with us for decades now, there have been relatively few moments in which they have been truly tested in a court. There have been frequent licence violations in which closed-source products have been found to contain open-source software, but they have more often resulted in out-of-court settlement than lengthy public legal fights. Sometimes the open-source community has gained previously closed-source projects, as their licence violations have involved software whose licence terms included a requirement for a whole project in which it is included to have the same licence. These terms are sometimes referred to as viral clauses by open-source detractors, and the most famous such licence is the GNU GPL, or General Public Licence. If you have ever installed OpenWRT on a router you will have been a beneficiary of this: the project has its roots in the closed-source firmware for a Linksys router that was found to contain GPL code.

Now we have news of an interesting milestone for the legal enforceability of open-source licences, a judge in California has ruled that the GPL is an enforceable contract. Previous case-law had only gone as far as treating GPL violations as a copyright matter, while this case extends its protection to another level.

The case in question involves a Korean developer of productivity software, Hancom Office, who were found to have incorporated the open-source Postscript and PDF encoder Ghostscript into their products without paying its developer a licence fee. Thus their use of Ghostscript falls under the GPL licencing of its open-source public version, and it was  on this basis that Artifex, the developer of Ghostscript, brought the action.

It’s important to understand that this is not a win for Artifex, it is merely a decision on how the game can be played. They must now go forth and fight the case, but that they can do so on the basis of a contract breach rather than a copyright violation should help them as well as all future GPL-licenced developers who find themselves in the same position.

We’re not lawyers here at Hackaday, but if we were to venture an opinion based on gut feeling it would be that we’d expect this case to end in the same way as so many others, with a quiet out-of-court settlement and a lucrative commercial licencing deal for Artifex. But whichever way it ends the important precedent will have been set, the GNU GPL is now an enforceable contract in the eyes of the law. And that can only be a good thing.

Via Hacker News.

GNU logo, CC-BY-SA 2.0.