NDTM · Recursively enumerable

Is n composite? Guess a factor

@thethinkmachine·version 1·CC BY 4.0·added 28 Sept 2026

Accepts 1ⁿ exactly when n is composite: the machine guesses a factor p, then verifies it by dealing the remaining 1s into rounds of p. Primality by nondeterministic elimination.

Open in AutomataStudio

The machine as drawn — 8 states, 21 transitions.

The author’s examples, run

1111 → accept111111 → accept111111111 → accept11111 → reject1111111 → reject

Definition

$$ \begin{aligned} M &= (Q, \Sigma, \Gamma, \delta, q_0, F) \\Q &= \{ \text{seed}, \text{guess p}, \text{next X}, \text{cross 1}, \text{last cross}, \text{reset ruler}, \text{any 1s left?}, \text{acc} \} \\\Sigma &= \{ \text{1} \} \\\Gamma &= \{ \text{1}, \text{\#}, \text{X}, \text{x}, \text{D}, \text{$\sqcup$} \} \\q_0 &= \text{seed} \\F &= \{ \text{acc} \} \\\delta &: Q \times \Gamma \to \mathcal{P}(Q \times \Gamma \times \{L, R, S\}) \end{aligned} $$

Verified by the library

Tests pass — 5 examples checked

Machine code

tm.1.%23DXx@h:---2RB------------_---(4RB4RC)------------_---1LC2RD3LC5RE5LC_---3LF---3RD---5RD_---3LC---3RE---5RE_------2RG3LF---4LF_0SZ1LC---3RG4RG---

Size: 8 states · 21 transitions
Level: Intermediate
Licence: Creative Commons Attribution 4.0
Tags: showcase ndtm