computer science

A Nurse Call System Becomes Turing Complete

March 9, 2019 by 3 Comments

George Mallory, a famous English mountaineer, once suggested that it was of no use to climb mountains. Instead, he posited, the only reason to climb a mountain is because it is there. Likewise, when you become an expert in nurse call systems like those found in hospitals, you may find that you do things with them that are of similar use. Making a Turing-complete nurse call system is something you do because you can.

[Erik] has been working on this particular call system, known as Netrix, and used Wireshark to sniff out all of its protocols. With this information he realized that it would be possible to use the system’s routing features to perform all of the tasks that any Turing complete system can do: conditional branching and memory access. He set up a virtual machine and set about implementing all of these tasks using the nurse call system’s features.

The setup for this project is impressive, and belies an extensive knowledge of this one proprietary system but also of computer science in general. It’s interesting to see how something can be formed into a working computer system from parts that otherwise might not be used that way. Even things that aren’t electronic can be used as Turing-complete computers.

Photo via Wikimedia Commons

A Compiler in Plain Text Also Plays Music

January 17, 2019 by 18 Comments

As a layperson reading about some branches of mathematics, it often seems like mathematicians are just people who really like to create and solve puzzles. And, knowing that computer science shares a lot of its fundamentals with mathematics, we can assume that most computer scientists are also puzzle-solvers as well. This latest project from [tom7] shows off his puzzle creating and solving skills with a readable file which is also a paper, which is also a compiler for C programs, which can also play music.

[tom7] started off with the instruction set for the Intel 8086 processor. Of the instructions available, he wanted to use only instructions which are also readable in a text file. This limits him dramatically in what this file will be able to execute, but also sets up the puzzle. He walks through each of the hurdles he found by only using instructions that also code to text, including limited memory space, no obvious way of exiting the program once it was complete, not being able to jump backward in the program (i.e. looping), and a flurry of other issues that come up once the instruction set is limited in this way.

The result is a sort of C compiler which might not be the most efficient way of executing programs, but it sure is the most effective way of showing off [tom7]’s PhD in computer science. As a bonus, the file can also play an antiquated type of sound file due to one of the available instructions being a call for the processor to interact with I/O. If you want to learn a little bit more about compilers, you can check out a primer we have for investigating some of their features.

Thanks to [Greg] for the tip!

Continue reading “A Compiler in Plain Text Also Plays Music” →

Software: It Is All In The Details

January 6, 2019 by 22 Comments

Who’s the better programmer? The guy that knows 10 different languages, or someone who knows just one? It depends. Programming is akin to math, or perhaps it is that we treat some topics differently than others which leads to misconceptions about what makes a good programmer, mathematician, or engineer. We submit that to be a great programmer is less about the languages you know and more about the algorithms and data structures you understand. If you know how to solve the problem, mapping it to a particular computer language should be almost an afterthought. While there are many places that you can learn those things, there is a lot more focus on how to write the languages,  C++ or Java or Python or whatever. We were excited, then, to see [Jeff Erickson] is publishing his algorithms book distilled from teaching at the University of Illinois, Urbana-Champaign for a number of years. The best part? You can read the preprint version online now and it will remain online even after the book goes to print.

When you were in school, you probably learned math in two ways: there was the mechanics (4×4=16) and then there were the word problems (Johnny has 10 candy bars and eats 4, how many are left?). Word problems are usually the bane of the student’s existence, yet they are much more realistic. Your boss has (probably) never come in your office and asked you what 147 divided by 12 is. If she did, you could hand her a calculator. The real value comes in being able to synthesize the right math for the right problem and — if you are lucky — gaining intuition about it (doubling the price will only increase profit by 10%). Software is pretty much the same, for example no one rushes into your cubicle and says “Quick! We need a for loop written!” You get a hazy set of requirements if you are lucky, and you then need to map that into something that computers can do. For that reason, we’ve always been more of a fan of learning about algorithms and data structures rather than specific language features.

Continue reading “Software: It Is All In The Details” →

Computer Programming Unplugged For Kids

August 3, 2018 by 10 Comments

There was a time when computers were far too expensive to let mere students use them. In those days, we wrote fake programs for fictitious machines and checked them by hand. That wasn’t fun, but it did teach you to think about the algorithm. You weren’t worried about how many tabs to indent code in the editor, or checking your social media feed, or changing the track on your Spotify playlist. Maybe that was the idea behind Computer Science Unplugged. The site is aimed at educators and gives them lesson plans to teach kids about computer concepts through activities that don’t use a computer.

The target ages are from 5 to 14 and topics range from binary numbers, sorting, searching, error detection, and robotics. For example, one exercise has students line up to be bits in a binary number. Each kid holds a card that is blank on one side or has the right number of dots on the other (for example, bit 0 has 1 dot, bit 2 has 4 dots, and so on).

Continue reading “Computer Programming Unplugged For Kids” →

Algorithms for Visual Learners

May 6, 2018 by 10 Comments

Computer programming is a lot like chess. It is fairly simple to teach people the moves. But knowing how the pieces move isn’t the reason you can win. You have to understand how the pieces work together. It is easy to learn the mechanics of a for loop or a Java interface. But what makes programs work are algorithms. There are many books and classes dedicated to algorithms, but if you are a visual learner, you might be interested in a site that shows visualizations of algorithms called VisuAlgo.

The site is from [Dr. Steven Halim] and is meant for students at the National University of Singapore, but it is available “free of charge for Computer Science community on earth.” We suspect if any astronauts or cosmonauts wanted to use it in space, they’d be OK with that, too.

The animations and commentary take you through algorithms ranging from the common — sorting and linked lists — to the obscure — Steiner and Fenwick trees. Each animation frame has some commentary, so it isn’t just pretty pictures. The site is available in many languages, too.

Many of the animations allow you to set up problems and execute them using a C-like pseudo language. When it executes, you can watch the execution pointer and a box comments on the current operation. For example, in the linked list unit, you can create a random doubly linked list and then search it for a particular value. Not only can you see the code, but the graphical representation of the list will update as the code runs.

The site allows you to register for free to get additional features, but we didn’t and it was still a great read about many different data structures. Also, a few of the commentary slides require you to show you are actually a computer science professor — we assume there’s some copyright issue involved because it is only a few.

This site is a great example of how many free educational resources are out there on the web. It isn’t just computer science either. MITx — or more generally, edX — has some great hardware classes and many other topics

Mechanical Wooden Turing Machine

March 8, 2018 by 19 Comments

Alan Turing theorized a machine that could do infinite calculations from an infinite amount of data that computes based on a set of rules. It starts with an input, transforms the data and outputs an answer. Computation at its simplest. The Turing machine is considered a blueprint for modern computers and has also become a blueprint for builders to challenge themselves for decades.

Inspired by watching The Imitation Game, a historical drama loosely based on Alan Turing, [Richard J. Ridel] researched Alan Turing and decided to build a Turing machine of his own. During his research, he found most machines were created using electrical parts so he decided to challenge himself by building a purely mechanical Turing machine.

Unlike the machine Alan Turing hypothesized, [Richard J. Ridel] decided on building a machine that accommodated three data elements (0, 1, and “b” for blank) and three states. This was informed by research he did on the minimum amount of data elements and states a machine could have in order to perform any calculation along with his own experimentation and material constraints.

Read more about Richard’s trial and error build development, how his machine works, and possible improvements in the document he wrote linked to above. It’s a great document of process and begs you to learn from it and take on your own challenge of building a Turing machine.

For more inspiration on how to build a Turing machine check out how to build one using readily available electronic components.

Continue reading “Mechanical Wooden Turing Machine” →

A Two Tapes Turing Machine

February 23, 2018 by 6 Comments

Though as with so many independent inventors the origins of computing can be said to have been arrived at through the work of many people, Alan Turing is certainly one of the foundational figures in computer science. His Turing machine was a thought-experiment computing device in which a program performs operations upon symbols printed on an infinite strip of tape, and can in theory calculate anything that any computer can.

In practice, we do not use Turing machines as our everyday computing platforms. A machine designed as an academic abstract exercise is not designed for efficiency. But that won’t stop Hackaday, and to prove that point [Olivier Bailleux] has done just that using readily available electronic components. His twin-tape Turing machine is presented on a large PCB, and is shown in the video below the break computing the first few numbers of the Fibonacci sequence.

The schematic is available as a PDF, and mostly comprises of 74-series logic chips with the tape contents being displayed as two rows of LEDs. The program is expressed as a pluggable diode matrix, but in a particularly neat manner he has used LEDs instead of traditional diodes, allowing us to see each instruction as it is accessed. The whole is a fascinating item for anyone wishing to learn about Turing machines, though we wish [Olivier] had given  us a little more information in his write-up.

That fascination with Turing machines has manifested itself in numerous builds here over the years. Just a small selection are one using 3D printing, another using Lego, and a third using ball bearings. And of course, if you’d like instant gratification, take a look at the one Google put in one of their doodles for Turing’s 100th anniversary.

Continue reading “A Two Tapes Turing Machine” →