cs.LOAug 25, 2026

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

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

Organizations: Dept. of Electronics and Computer Engineering, Thapathali Campus

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Explore similar work

CardsList
May 3, 2026

A PyTorch Library of Turing-Complete Neural Networks

We present a PyTorch package that compiles neural networks and their weights from Turing machine descriptions, producing models that exactly simulate the specified machine without any training. Given a transition function and a set of terminal states, the package constructs a model whose forward pass corresponds to one step of the Turing machine. Two architectures are implemented, each realizing a different theoretical result: (1) a transformer with self-attention, cross-attention, and feedforward layers based on Wei, Chen, and Ma (2021), and (2) a recurrent network based on Siegelmann and Sontag (1995) that encodes the stack in a Cantor set. We develop the constructions from first principles, showing how ReLU networks implement Boolean circuits (AND, OR, NOT, XOR gates and their composition into DNF formulas and binary adders) and how hard attention implements positional lookup on the tape. The package serves as a concrete, runnable reference for the symbolic-neural bridge, and as a foundation for future work on the stability of constructed solutions under gradient-based optimization. Code is available at https://github.com/jonrbates/turing.

Jonathan Bates

Neural Network Expressivity
AskPDF
Jul 7, 2026

When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?

Modern sequence models are increasingly deployed as agents that interleave token generation with calls to external tools. We study when such tool access increases computational expressivity. We model any fixed finite-precision recurrent sequence model, including finite-precision state-space models (SSMs) with BB bits of internal state, as a deterministic finite-state controller interacting with an oracle through a finite command/observation interface, and establish a separation between the two regimes analyzed. First, every finite-state bounded-interface tool with memory set MM can be internalized at a cost of at most ⌈log⁡2∣M∣⌉+O(1)\lceil\log_2|M|\rceil+O(1) recurrent bits, so the combined system remains finite-state. Second, a single unbounded tape with only local read\mathtt{read}/write\mathtt{write}/move\mathtt{move} commands suffices for Turing completeness: every single-tape Turing machine with state set QQ and tape alphabet ΓΓ is simulated by a controller with O(log⁡∣Q∣+log⁡∣Γ∣)O(\log|Q|+\log|Γ|) recurrent bits, and EQn\mathrm{EQ}_n requires 2n2^n states without tools but one constant-size controller with the tape. Third, this construction is realized exactly by a one-layer finite-precision selective affine SSM with binary one-hot states, {0,1}\{0,1\} transition matrices, and zero biases. Under explicitly stated resource conventions, O(log⁡B)O(\log B) recurrent bits suffice for tape-assisted simulation of any BB-state Turing machine, whereas directly realizing an arbitrary BB-state transition map in one exact affine update without external memory requires total recurrent dimension exactly B−1B-1. Fixed description size, occupied tape cells, and interaction cost are reported separately from recurrent memory. Our results concern exact expressivity under deterministic semantics, not learnability or empirical performance.

Nikola Zubić, Qian Li, Yuyi Wang +1

Robotics and Perception Group, University of Zurich · Shenzhen International Center for Industrial and Applied Mathematics, Shenzhen Research Institute of Big Data · Tengen Intelligence Institute, CRRC Zhuzhou Institute

Recurrent Neural NetworksNeural Network ExpressivityFinite-State Machine
AskPDF
May 18, 2026

DexHoldem: An Agentic Robotics Benchmark for Dexterous Manipulation in Texas Hold'em

Evaluating embodied systems with real dexterous hardware requires more than isolated motor-skill tests: an agent must perceive a changing scene (e.g. a tabletop), choose a context-appropriate action, execute it with a dexterous hand, and leave the scene usable for later decisions. We introduce DexHoldem, a comprehensive real-world benchmark evaluating Texas Hold'em related dexterous manipulations with a ShadowHand. DexHoldem provides 1,470 teleoperated demonstrations across 14 Texas Hold'em manipulation primitives, a standardized physical policy benchmark, and an agentic perception benchmark that tests whether agents can recover the structured game state needed for embodied decision making. On primitive execution, π0.5π_{0.5} obtains the highest task completion rate (61.2%61.2\%), while π0.5π_{0.5} and π0π_0 tie on scene-preserving success rate (47.5%47.5\%). On agentic perception, Opus 5.5 narrowly leads on both strict problem-level accuracy (49.1%49.1\%) and average field-wise accuracy (80.6%80.6\%); the gap between the two exposes the distance between isolated visual sub-capabilities and complete routing-relevant state recovery. Finally, we instantiate the full embodied-agent loop with one agent--policy pairing over 33 closed-loop hand-level rollouts, in which only 12.1%12.1\% of hands complete; retries restore the failed primitive in 12 of 34 dispatches and resolve prolonged execution stalls in three of the four completed hands, which would otherwise have required manual termination. Only one hand completes with neither a retry nor a human-help request. DexHoldem therefore evaluates dexterous tabletop execution, agentic perception, and embodied decision routing in a shared physical setting. Project website: https://dexholdem.github.io/Dexholdem/

Feng Chen, Tianzhe Chu, Li Sun +6

Dexterous ManipulationAI Agent EvaluationRobotic ManipulationRobot Manipulation BenchmarksEmbodied AI
AskPDF