Design and Empirical Characterization of a Hardware-Realized Turing Machine with Automated Card-Based Programming

Agrima Regmi; Jenish Pant; Pratistha Sapkota; Sanskriti Khatiwada; Binod Sapkota

Source-linked AI summary

Design and Empirical Characterization of a Hardware-Realized Turing Machine with Automated Card-Based Programming

Agrima Regmi, Jenish Pant, Pratistha Sapkota, Sanskriti Khatiwada, Binod Sapkota

arXiv:2608.24742v1Aug 25, 2026cs.LOcs.CL

TL;DR

Prior physical Turing Machine demonstrations often require manual stepping or reprogramming, limiting autonomous extended computation. This paper builds a hardware UTM with optical punched-card programming and autonomous execution, achieving exact simulator agreement while quantitatively characterizing mechanical, optical, and electrical performance. The design remains bounded by finite tape, card-format state limits, environmental sensing constraints, and slow mechanical operation.

Problem
Prior physical Turing Machine demonstrations commonly require manual computation steps or state-table reconfiguration, limiting autonomous extended execution.
Method
The paper integrates microcontroller transition logic, motorized tape actuation, infrared symbol sensing, servo write and erase heads, an ESP32-CAM punched-card reader, BFS decoding, and parallel tlang verification.
Results
All evaluated hardware tape outputs matched the simulator outputs, while the complete system demonstrated binary increment and unary addition computations.
Takeaways & Limitations
Autonomous execution and camera-based punched-card input provide a physical platform for reprogrammable Turing Machine demonstrations without manual intervention between programs.
Takeaways & Limitations
The system is limited by finite tape length, a 22-state punched-card format, lighting-sensitive IR sensing, approximately one-symbol-per-second operation, and wear-prone 2 mm MDF mechanics.

Abstract

from arXiv · show

Physical implementations of Turing Machines remain rare, and existing electromechanical demonstrators and mechanical logic games typically require manual operator intervention, either to trigger each computational step or to reconfigure the state table, or both. This restricts prior physical models to short, operator-paced demonstrations and prevents autonomous execution of extended computations. This paper addresses that gap with a hardware Turing Machine that enables autonomous multi-step execution and reprogrammable optical input without manual intervention between programs. The system integrates an Arduino Mega for state-transition logic, dual NEMA 17 stepper motors for bidirectional tape actuation, infrared reflectance sensors for symbol detection, and an ESP32-CAM-based optical punched-card reader for automated state-table loading. Hole detection under non-uniform illumination used a Breadth-First Search flood-fill algorithm with local adaptive thresholding rather than fixed global thresholding, driven by the memory and library constraints of the ESP32-CAM's microcontroller environment; this improved card-decoding accuracy from 75% to 90% (100% with mechanical card flattening) on a 20-card test set. Mechanical evaluation showed fabrication accuracy of +/-0.15 mm, rack-and-pinion positional error below 0.3 mm across 50 trials, and voltage supply stability within +/-0.2 V under full system load. End-to-end computation was validated against a parallel software simulator (tlang), with all hardware outputs matching the simulated reference exactly across multiple test programs. The system advances prior physical Turing Machine demonstrations through autonomous execution, reprogrammable optical input, and quantitative evaluation of its mechanical, optical, and computational performance.

1. Introduction

Turing Machines provide a formal model of computation, but their abstract presentation and limited interactive hardware tools can make operation difficult to connect with practice. This work targets a physical machine that supports reprogrammable transition tables and autonomous multi-transition execution.

Theoretical Background: A Universal Turing Machine formalizes computation through an infinite tape, a movable head, and state-dependent transition rules.The head reads and writes symbols, moves across tape cells, and changes state according to defined rules.
Theoretical Background: The formal machine is defined as a 7-tuple specifying states, symbols, transition rules, initial configuration, a blank symbol, and accepting conditions.
Motivation: Abstract representations and the lack of interactive hardware-based learning tools create challenges for students connecting Turing Machine theory with application.
Motivation: Existing physical implementations often require manual intervention or simplified program configuration, limiting continuous reprogrammable computation in one system.
Contributions: The proposed work combines a low-cost UTM implementation, dual-stepper tape actuation, optical card decoding, simulator-assisted verification, and subsystem characterization.

2. Related Works

Prior work spans software simulators, theoretical extensions, and physical demonstrations, but the present system emphasizes autonomous execution and optical punched-card programming. Its camera-based reader is identified as a distinguishing feature among prior physical UTM implementations.

Historical Context: Turing Machine hardware development is situated within a broader history connecting computability theory, finite-state machines, and hardware-based computational models.
Software and Extensions: Related work includes JFLAP, FSM Builder, and theoretical extensions involving quantum and distributed Turing Machine frameworks.
Physical Models: Earlier physical models such as Davey’s implementation use mechanical components without electronic sensing or automated control, requiring manual state transitions.
Physical Models: Turing Tumble demonstrates Turing-complete logic under extended conditions but requires manual ball placement for each computation step.
Physical Models: The proposed implementation executes computation steps autonomously through programmed logic, supporting observation of extended computations in real time.
Physical Models: An ESP32-CAM optical reader loads state tables from punched cards, eliminating manual reprogramming between computation runs.

3. Materials and Methods

The materials-and-methods section includes a system block diagram identifying the machine’s overall system organization.

System Overview: Figure 1 is presented as the system block diagram for the proposed machine.
System Overview: The figure serves as a visual representation of the system-level arrangement described in the paper.
System Overview: The supplied figure passage identifies the diagram but does not specify its component connections or data flow.

3.1 System Architecture

The system architecture separates optical program acquisition, microcontroller control, motorized tape operation, sensing, writing, erasing, and software verification into interacting subsystems. Mechanical components are designed for accurate tape and card transport while sensors and actuators implement physical transition operations.

System Architecture: The architecture addresses programmable input, reliable tape positioning, autonomous symbol operations, and pre-hardware computational verification through four interacting subsystems.These subsystems are the optical punched-card reader, microcontroller control system, motorized tape mechanism, and software simulation environment.
Tape Mechanism: A 35 mm laminated tape stores binary symbols and blanks in discrete cells, with stepper-driven motion aligning cells to the read, write, and erase heads.
Read Head: Two infrared reflectance sensors convert predefined tape reflectance patterns into binary symbol representations during sequential cell sampling.
Write Head: Servo-driven dual rack-and-pinion motion positions the marker along two axes to write a new symbol or leave the cell unchanged.
Erase Head: A DC-motor-driven felt cylinder moves along one axis to erase the current tape symbol and prepare the cell for overwriting.
Control System: An Arduino controls the machine components using transition rules and punched-card-derived memory configuration, while buttons and an LCD support operation and feedback.
Mechanical Design: The machine base was designed in Onshape with dimensions of 180 mm × 135.1 mm × 50 mm to support transport, sensors, and control electronics.
Card Transport: The card transport uses a servo-driven rack-and-pinion mechanism to convert rotational shaft motion into controlled linear displacement.

3.2 Punched Card Reader

The punched card reader captures punched-card images, converts hole patterns into binary data, and transmits decoded transition rules to the Arduino control unit for automated loading.

The ESP32-CAM captures card images and digitizes hole presence or absence as binary values for transition-table input.Punched cards serve as the system’s primary programmable input medium.
Captured images undergo grayscale conversion, noise reduction, and thresholding before hole patterns are translated into binary sequences.
Decoded transition rules are transmitted over a serial interface to the Arduino-based control unit.The control unit uses them for state transitions, tape movement, and symbol manipulation.

3.3 Image Processing Pipeline

The image-processing pipeline combines grayscale conversion, adaptive binarization, and BFS flood-fill labeling to identify punched holes under variable illumination within the ESP32-CAM’s resource constraints.

Grayscale conversion uses a luminosity-weighted combination of RGB channels to increase contrast between black ink and the white card substrate.
Local adaptive thresholding was more robust than fixed global thresholding under non-uniform card illumination.Global thresholding used T = 128 and produced false positives and misses, especially near card edges.
BFS flood fill labels connected black-pixel regions in O(W×H) time using memory suited to the ESP32-CAM’s limited RAM.BFS was selected because standard OpenCV functions were unavailable and DFS stack usage was less predictable.
The flood-fill traversal examines 4-connected neighbours and marks visited pixels to measure each connected region’s area.Regions below a minimum pixel-area threshold are discarded as noise, while larger regions are classified as punched holes.
Detected hole positions map to card-grid rows and columns encoding transition-rule fields, which are serialized and sent to the Arduino Mega over UART.

3.4 Turing Machine Simulation - tlang

The tlang simulator provides a software reference for designing, testing, and verifying transition rules before physical execution, while visualizing tape and machine state.

A C-based Turing Machine simulator with a custom language was developed to observe and verify machine behavior digitally.It validates transition rules, tests algorithms, and establishes expected hardware behavior.
The simulator models an extendable tape, movable head, and state-transition mechanism using a compact instruction set.The language uses the keywords {F, N, R, L, S, H} to represent state-table operations.
The simulator executes operations step-by-step to expose state transitions and tape modifications.
Extensive simulator testing helped identify logical errors and edge cases before hardware implementation.The authors report that this process guided design decisions and improved physical-system reliability and feasibility.
The graphical interface displays tape content, the current machine state, and the head’s position.

4. Results

Subsystem characterization evaluated fabrication, actuation, power, tape transport, and symbol sensing before integration, showing dimensional and positional accuracy alongside stable operation.

4.1 Structural Base: ±0.15 mm average deviation was measured across 50 base locations relative to CAD nominal dimensions.The MDF base was laser-cut at 50 W and 300 mm/min with approximately 1 mm kerf compensation.
4.2 Linear Movement Mechanism: 0.28 mm mean positional error was measured across 50 rack-and-pinion displacements, below the 0.3 mm target.The maximum observed error was 0.41 mm, and mean response time was 150 ms over 30 trials.
4.3 Main Control Board: ±0.2 V rail deviations were measured under full-load operation across the system’s 12 V, 5 V, and 3.3 V supplies.
4.4 Tape Transport: 2.1 mm cumulative tape drift occurred over 50 cycles with the single-motor design, while the dual-motor configuration showed no measurable slippage over 200 cycles.Single-motor drift caused the read head to straddle cell boundaries and produce symbol misreads.
4.5 IR Symbol Detection: 100% symbol classification accuracy was achieved across 150 reads under diffuse indoor lighting with the sensor enclosure fitted.Without enclosure shielding under direct fluorescent lighting, misread rates were approximately 8%.

4.6 Punched Card Reader

The punched-card reader captures and processes card images to reconstruct transition tables for hardware execution. It decoded 90% of unconstrained test cards and 100% when cards were flattened, while full-system tests matched the tlang simulator.

Optical decoding: The ESP32-CAM captures top-down card images, then applies grayscale conversion, adaptive thresholding, and BFS flood-fill detection to reconstruct transition tables.The decoded table is used for finite-state-machine reconstruction and subsequent hardware execution.
End-to-end validation: The binary-increment test loaded a punched-card state table, executed 12 transitions in approximately 38 seconds, and produced 0111 from an initial 0110.The hardware output and every state transition matched the tlang reference; unary addition also succeeded for operands up to 5+4.
End-to-end validation: All evaluated hardware test programs produced final tape contents matching the outputs generated by the tlang simulator.The simulator was used before physical execution to validate the intended transition rules.
Accuracy: 90% of punched cards were decoded under unconstrained conditions, with both failures caused by shadows from curled card edges.The reader successfully decoded 18 of 20 test cards.
Accuracy: 100% decoding accuracy was achieved after mechanically flattening the cards during scanning.All 20 test cards were decoded correctly once card curling was removed.

5. Discussion

The system extends earlier physical Turing Machine demonstrations with autonomous execution, electronic sensing, optical state-table loading, and quantitative evaluation. Its engineering choices address tape drift and illumination variability, while remaining constrained by material durability, mechanical speed, and finite resources.

Comparison with prior implementations: The machine adds automated symbol reading, autonomous state transitions, and reprogrammable optical state-table loading compared with prior physical implementations.These capabilities allow algorithms to be changed without hardware modification and reduce operator intervention between computational steps.
Comparison with prior implementations: Unlike Turing Tumble, the machine operates autonomously after state-table loading rather than requiring an operator to trigger each computation step.The comparison frames autonomous execution as more representative of computational-device operation for educational demonstration.
Engineering rationale: Dual-motor tape actuation eliminates slack-related positional drift, while adaptive thresholding compensates for spatial illumination gradients that impair global thresholding.The adaptive-thresholding gain was 75%→90% in card decoding.
Engineering rationale: The design uses low-cost 2 mm MDF, trading reduced fabrication cost for approximately 200 g load tolerance and lower long-term durability than acrylic.Acrylic would trade higher cost for longer lifespan.
Verification: Simulator-assisted verification separated logical validation from physical execution, and hardware deviations were traced to subsystem faults rather than state-table logic.The cited faults included poor-lighting sensor misreads and tape slippage in early single-motor trials.
Limitations: The finite tape, 22-state punched-card limit, lighting sensitivity, approximately one-symbol-per-second speed, and MDF wear constrain computation and sustained use.The paper states that the mechanical speed makes computations beyond educational demonstration impractical.

6. Conclusion

The paper presents and evaluates a complete hardware Universal Turing Machine integrating optical programming, electronic sensing, motorized tape actuation, and simulator-assisted verification. Measured subsystem performance and matching hardware–simulator outputs support successful binary-increment and unary-addition demonstrations.

System contribution: The complete system combines dual NEMA 17 motors, IR reflectance sensors, servo-actuated write and erase heads, and an ESP32-CAM punched-card reader.The reader uses BFS flood-fill decoding, while the architecture supports physical execution of programmed transition rules.
System evaluation: Measured fabrication accuracy was ±0.15 mm, rack-and-pinion positional error was below 0.3 mm, and voltage stability was within ±0.2 V.These measurements are reported as evidence of robust subsystem performance.
System evaluation: Hardware execution matched tlang simulation for the binary-increment and unary-addition demonstrations, including the tested 12-transition increment run.The accompanying simulator provided pre-hardware verification of the theoretical transition rules.