What does it mean to be 'Turing complete'?
The term "Turing complete" describes all computers and even some things we don't expect to be as powerful as a typical computer. In this article, I describe what it means and discuss the implications of Turing completeness on projects that need just a little more power, on alternative processor designs, and even security.
Summary
The article unpacks the concept of Turing completeness and why it matters to embedded engineers. It describes what makes a system computationally universal and discusses practical consequences for firmware design, alternative processor architectures, and security.
Key Takeaways
- Explain the formal meaning of Turing completeness and how it differs from everyday notions of "computing power".
- Evaluate whether a given device, language, or constrained system (e.g., microcontroller firmware or DSL) is Turing complete.
- Assess practical trade-offs of Turing-complete designs for firmware and embedded Linux, especially regarding resources and determinism.
- Apply Turing-completeness concepts to security and sandboxing decisions, and to the design of minimal VMs or alternative processor ISAs.
Who Should Read This
Embedded systems developers and firmware engineers (intermediate experience) who need to decide when to add computation power, design minimal runtimes/VMs, or evaluate security implications.
TimelessIntermediate
Related Documents
- Consistent Overhead Byte Stuffing TimelessIntermediate
- PID Without a PhD TimelessIntermediate
- Introduction to Embedded Systems - A Cyber-Physical Systems Approach Still RelevantIntermediate
- Can an RTOS be really real-time? TimelessAdvanced
- Memory Mapped I/O in C TimelessIntermediate
