# Rule 30 cell

> Find the next state of one Rule 30 cell from its neighbours, so every row of the pattern can be replayed and checked.

Inspired by afflom/rule30 (https://github.com/afflom/rule30), live at https://afflom.github.io/rule30/. LexLean and Lean 4 formalization of Wolfram's Rule 30 with verified artifacts. Pattern: Decision table, OMG DMN 1.5, hit policy FIRST. To write one of your own, follow How to build a decision table app (../../guides/decision-table/index.md). The prompt below is data, quoted from the example.

**Figure: What the Rule 30 cell app does.** A request goes in, the rules decide, and the Lean kernel has already proved what the rules promise.

| Step | What happens |
| --- | --- |
| 1. Request | left, center, right |
| 2. 3 rules | the first that matches wins |
| 3. Answer | off, on |
| 4. Proved | 2 theorems, 19 tests |

Verified by prismpm verify in the pinned SDK. Fingerprint: eca1f4f622046d7be3ffd5a691eff31348096b18576de16e86ef3d7e528749b3. Acceptance vectors: 19. Claims: 5.

## The prompt

```json
{
  "schema": "prism/prompt/1",
  "goal": "Find the next state of one Rule 30 cell from its neighbours, so every row of the pattern can be replayed and checked.",
  "pattern": "decisionTable",
  "repository": "afflom/rule30",
  "license": "MIT",
  "app": {
    "name": "rule-thirty-cell",
    "title": "Rule 30 cell",
    "purpose": "Decide the next state of a Rule 30 cell from its left neighbour, itself and its right neighbour.",
    "fields": [
      {
        "name": "left",
        "kind": "choice",
        "values": [
          "off",
          "on"
        ],
        "means": "the left neighbour now"
      },
      {
        "name": "center",
        "kind": "choice",
        "values": [
          "off",
          "on"
        ],
        "means": "the cell now"
      },
      {
        "name": "right",
        "kind": "choice",
        "values": [
          "off",
          "on"
        ],
        "means": "the right neighbour now"
      }
    ],
    "outcomes": [
      "off",
      "on"
    ],
    "meanings": {
      "on": "the cell is black in the next row",
      "off": "the cell is white in the next row"
    },
    "rules": [
      {
        "when": [
          {
            "field": "left",
            "op": "is",
            "value": "on"
          },
          {
            "field": "center",
            "op": "is",
            "value": "off"
          },
          {
            "field": "right",
            "op": "is",
            "value": "off"
          }
        ],
        "then": "on",
        "why": "rule30-lexlean/src/Core.lex.tex: rule a b c = bxor a (b || c), so 100 gives 1"
      },
      {
        "when": [
          {
            "field": "left",
            "op": "is",
            "value": "off"
          },
          {
            "field": "center",
            "op": "is",
            "value": "on"
          }
        ],
        "then": "on",
        "why": "rule30-lexlean/src/Core.lex.tex: with a off, rule is b || c, so 010 and 011 give 1"
      },
      {
        "when": [
          {
            "field": "left",
            "op": "is",
            "value": "off"
          },
          {
            "field": "right",
            "op": "is",
            "value": "on"
          }
        ],
        "then": "on",
        "why": "rule30-lexlean/src/Core.lex.tex: with a off, rule is b || c, so 001 gives 1"
      }
    ],
    "otherwise": "off",
    "otherwiseWhy": "rule30-lexlean/src/Core.lex.tex: bxor a (b || c) is 0 for 000, 101, 110 and 111",
    "properties": [
      {
        "kind": "never",
        "when": [
          {
            "field": "left",
            "op": "is",
            "value": "on"
          },
          {
            "field": "center",
            "op": "is",
            "value": "on"
          }
        ],
        "then": "on",
        "why": "Core.lex.tex: with a and b on, bxor true true is false, so 110 and 111 give 0"
      },
      {
        "kind": "always",
        "when": [
          {
            "field": "left",
            "op": "is",
            "value": "off"
          },
          {
            "field": "center",
            "op": "is",
            "value": "off"
          },
          {
            "field": "right",
            "op": "is",
            "value": "off"
          }
        ],
        "then": "off",
        "why": "a white neighbourhood stays white, the background of the Rule 30 diagram"
      }
    ],
    "examples": [
      {
        "request": "off off off",
        "response": "off"
      },
      {
        "request": "off off on",
        "response": "on"
      },
      {
        "request": "off on off",
        "response": "on"
      },
      {
        "request": "off on on",
        "response": "on"
      },
      {
        "request": "on off off",
        "response": "on"
      },
      {
        "request": "on off on",
        "response": "off"
      },
      {
        "request": "on on off",
        "response": "off"
      },
      {
        "request": "on on on",
        "response": "off"
      }
    ]
  },
  "stakeholders": [
    {
      "name": "Researcher",
      "text": "Studies the Rule 30 sequence for Prize Problem 1 and needs every cell of every row to be the one the rule gives.",
      "concerns": [
        "Correct answers",
        "Proved guarantees"
      ]
    },
    {
      "name": "Proof engineer",
      "text": "Extends the LexLean and Lean 4 formalization and needs the cell rule to stay the one Core.lex.tex and the prize kit define.",
      "concerns": [
        "Agreement with the prize kit",
        "Proved guarantees"
      ]
    }
  ],
  "concerns": [
    {
      "name": "Agreement with the prize kit",
      "text": "The local rule is the one Rule30PrizeKit defines, as rule30-bridge/Rule30Bridge.lean connects every paper theorem to Ruliology.CellularAutomata.Rule30Prize.",
      "model": "component"
    }
  ],
  "components": [
    {
      "name": "Rule30PrizeKit",
      "text": "The Rule 30 Prize kit, Ruliology.CellularAutomata.Rule30Prize, whose definitions the bridge module ties the LexLean theorems to.",
      "kind": "externalSystem"
    },
    {
      "name": "r30 command surface",
      "text": "bin/r30: status, frontier, theorem add, check, verify and axioms, also served as an MCP server.",
      "kind": "cliAdapter"
    }
  ],
  "threats": [
    {
      "name": "Rule drifts from the prize kit",
      "text": "The cell table differs from the Rule 30 the prize kit defines, so a replayed row is not the automaton the prize asks about.",
      "stride": "tampering",
      "asset": "source",
      "likelihood": "low",
      "impact": "critical",
      "control": {
        "name": "Bridged to the prize kit",
        "text": "Rule30Bridge.lean proves every LexLean paper theorem against the kit definition, and all eight neighbourhoods are acceptance examples.",
        "evidence": [
          {
            "kind": "review",
            "reference": "rule30-bridge/Rule30Bridge.lean"
          },
          {
            "kind": "gate",
            "reference": "make check-research"
          }
        ]
      }
    },
    {
      "name": "Classical choice in a proof",
      "text": "A proof of the rule depends on Classical.choice, which the repository forbids in its authored proof surfaces.",
      "stride": "tampering",
      "asset": "source",
      "likelihood": "low",
      "impact": "major",
      "control": {
        "name": "Choice forbidden",
        "text": "The kernel axiom audit accepts only propext and Quot.sound, and a source check rejects classical constants.",
        "evidence": [
          {
            "kind": "gate",
            "reference": "scripts/check_no_choice.py"
          },
          {
            "kind": "gate",
            "reference": "make check-research"
          }
        ]
      }
    },
    {
      "name": "Boundary cells guessed",
      "text": "A caller asks about a cell at the edge of a finite row and supplies a neighbour that is not in the row.",
      "stride": "tampering",
      "asset": "request",
      "likelihood": "medium",
      "impact": "minor",
      "accepted": "The app answers one neighbourhood exactly; the convention for cells beyond a finite row belongs to the caller that builds the row."
    }
  ],
  "quality": [
    {
      "characteristic": "Maintainability",
      "subcharacteristic": "Testability",
      "requirement": "Whole truth table pinned",
      "text": "Each of the eight neighbourhoods of three cells is an acceptance example, so the table is checked row by row against Core.lex.tex.",
      "measure": "Neighbourhoods without an example",
      "measureText": "Of the eight three-cell neighbourhoods, those no example states.",
      "threshold": 0
    }
  ],
  "journeys": [
    {
      "stakeholder": "Researcher",
      "steps": [
        "REQ-001",
        "REQ-002",
        "REQ-003",
        "otherwise",
        "INV-001",
        "INV-002"
      ]
    }
  ],
  "axioms": {}
}
```

## Claims

- RT-01: The app never answers on when left is on and center is on
- RT-02: The app always answers off when left is off and center is off and right is off
- RT-03: The architecture description declares every stakeholder, concern, component, edge, viewpoint and view it references
- RT-04: The ISO/IEC 25010 quality model numbers every characteristic, subcharacteristic, requirement and measure, and every parent it names is declared
- RT-05: Every compliance obligation is numbered in order and names its evidence

## Pattern

Decision table: OMG DMN 1.5, hit policy FIRST. The rules are tried in order, and the first one that matches gives the answer. If none matches, the default answer applies. This is a DMN decision table with the FIRST hit policy.

| Pattern | Standard | Answers |
| --- | --- | --- |
| Decision table | OMG DMN 1.5, hit policy FIRST | off, on |

**Figure: Rules for each answer.** Each bar counts the rules that give one answer. When no rule matches, the answer is off.

|  | rules |
| --- | --- |
| off | 0 |
| on | 3 |

## Behavior

A request is left, center, right, separated by spaces. The first rule that matches decides. If none matches, the answer is off. A request over 88 bytes, or in any other form, is answered invalid.

| Rule | When | Answer | Why |
| --- | --- | --- | --- |
| REQ-001 | left is on and center is off and right is off | on | rule30-lexlean/src/Core.lex.tex: rule a b c = bxor a (b \|\| c), so 100 gives 1 |
| REQ-002 | left is off and center is on | on | rule30-lexlean/src/Core.lex.tex: with a off, rule is b \|\| c, so 010 and 011 give 1 |
| REQ-003 | left is off and right is on | on | rule30-lexlean/src/Core.lex.tex: with a off, rule is b \|\| c, so 001 gives 1 |
| otherwise | no rule matches | off | rule30-lexlean/src/Core.lex.tex: bxor a (b \|\| c) is 0 for 000, 101, 110 and 111 |

## Properties Lean proves

Each property is a theorem about the same definitions the app is built from. It is proved for every request, not only the tested ones.

| Property | Statement | Theorem | Why |
| --- | --- | --- | --- |
| INV-001 | It never answers on when left is on and center is on. | RuleThirtyCellProofs::inv001Holds | Core.lex.tex: with a and b on, bxor true true is false, so 110 and 111 give 0 |
| INV-002 | It always answers off when left is off and center is off and right is off. | RuleThirtyCellProofs::inv002Holds | a white neighbourhood stays white, the background of the Rule 30 diagram |

## Architecture

Stakeholders and the concerns each one views the app through (ISO/IEC/IEEE 42010).

| Stakeholder | Who they are | Concerns |
| --- | --- | --- |
| Proof engineer | Extends the LexLean and Lean 4 formalization and needs the cell rule to stay the one Core.lex.tex and the prize kit define. | Agreement with the prize kit, Proved guarantees |
| Researcher | Studies the Rule 30 sequence for Prize Problem 1 and needs every cell of every row to be the one the rule gives. | Correct answers, Proved guarantees |
| Verifier | Anyone who loads the holo, checks its fingerprint and replays its acceptance vectors before trusting an answer. | Integrity of the published app, Refused malformed requests, Proved guarantees |

## Concerns

What the stakeholders care about, and the model each is viewed in.

| Concern | What it means | Model |
| --- | --- | --- |
| Agreement with the prize kit | The local rule is the one Rule30PrizeKit defines, as rule30-bridge/Rule30Bridge.lean connects every paper theorem to Ruliology.CellularAutomata.Rule30Prize. | component |
| Correct answers | Every well-formed request is answered by the first rule that matches it, or off when none does, as the spec states. | quality |
| Integrity of the published app | What a visitor runs is the holo the build verified, with its fingerprint and signed provenance beside it. | security |
| Proved guarantees | Each of the 2 properties of the spec holds for every request, proved by the Lean kernel. | quality |
| Refused malformed requests | A request that is not the 3 fields in order, or is longer than 88 bytes, is answered invalid and never guessed. | security |

## Components

8 components and 11 edges between them.

| Component | Kind | What it is |
| --- | --- | --- |
| Browser | externalSystem | The visitor's web browser, which loads the page and runs the Rule 30 cell guest. |
| GitHub Pages | externalSystem | Serves the page and the holo from the repository Pages workflow. |
| Prism build | cliAdapter | prismpm verify in the SDK image prismpm.lock pins: it checks every theorem, builds the guest and replays every vector. |
| r30 command surface | cliAdapter | bin/r30: status, frontier, theorem add, check, verify and axioms, also served as an MCP server. |
| Rule 30 cell guest | service | The Core-Wasm guest built from the model: it answers one request of at most 88 bytes with one answer of at most 64. |
| Rule 30 cell page | staticSite | The page the template publishes: the holo, its fingerprint, its provenance and its acceptance vectors. |
| Rule30PrizeKit | externalSystem | The Rule 30 Prize kit, Ruliology.CellularAutomata.Rule30Prize, whose definitions the bridge module ties the LexLean theorems to. |
| Source repository | externalSystem | The repository that holds the prompt, the model and its gate. |

## Design views

The SDK checks each view against the system model and draws it as OPL and PlantUML.

| View | Diagram | Viewpoint |
| --- | --- | --- |
| Deciding a Rule 30 cell request | opmObjectProcess | Researcher: Correct answers |
| Components of Rule 30 cell | umlComponent | Verifier: Integrity of the published app |
| Answering a Rule 30 cell request | umlSequence | Researcher: Correct answers |
| States of the Rule 30 cell guest | umlStateMachine | Verifier: Refused malformed requests |

## Features and journeys

7 features. Each names the definitions that do the work and the tests that accept it. Each stakeholder has one journey.

| Feature | Calls | Accepted by |
| --- | --- | --- |
| When left is on and center is off and right is off, the answer is on. | RuleThirtyCell::rule1, RuleThirtyCell::judge | RuleThirtyCell::application |
| When left is off and center is on, the answer is on. | RuleThirtyCell::rule2, RuleThirtyCell::judge | RuleThirtyCell::application |
| When left is off and right is on, the answer is on. | RuleThirtyCell::rule3, RuleThirtyCell::judge | RuleThirtyCell::application |
| When no rule matches, the answer is off. | RuleThirtyCell::judge | RuleThirtyCell::application |
| A request that is not left, center, right in order, separated by single spaces, or is over 88 bytes, is answered invalid. | RuleThirtyCell::dispatch, RuleThirtyCell::decodeField1 | RuleThirtyCell::application |
| It never answers on when left is on and center is on. | RuleThirtyCell::judge | RuleThirtyCellProofs::inv001Holds |
| It always answers off when left is off and center is off and right is off. | RuleThirtyCell::judge | RuleThirtyCellProofs::inv002Holds |

## Journeys

The ordered features each stakeholder takes.

| Stakeholder | Steps |
| --- | --- |
| Proof engineer | REQ-001 → REQ-002 → REQ-003 → otherwise |
| Researcher | REQ-001 → REQ-002 → REQ-003 → otherwise → INV-001 → INV-002 |
| Verifier | refuse → INV-001 → INV-002 |

## Security and threat model

11 threats against 4 assets. Each has a STRIDE category, and either a control with evidence or a risk that is accepted on purpose.

| Threat | STRIDE | Asset | Risk | Answered by |
| --- | --- | --- | --- | --- |
| Answer that breaks INV-001 | repudiation | Answer | medium likelihood, critical impact | Proof of INV-001: proof RuleThirtyCellProofs::inv001Holds |
| Answer that breaks INV-002 | repudiation | Answer | medium likelihood, critical impact | Proof of INV-002: proof RuleThirtyCellProofs::inv002Holds |
| Boundary cells guessed | tampering | Request bytes | medium likelihood, minor impact | accepted: The app answers one neighbourhood exactly; the convention for cells beyond a finite row belongs to the caller that builds the row. |
| Classical choice in a proof | tampering | Model source | low likelihood, major impact | Choice forbidden: gate scripts/check\_no\_choice.py; gate make check-research |
| Granted capability | informationDisclosure | Answer | low likelihood, major impact | No capability granted: gate prism-code check refuses an ungranted guest import |
| Malformed request | tampering | Request bytes | high likelihood, major impact | Strict decoder: gate malformed-request acceptance vectors, replayed in the compiled guest by prismpm verify |
| Oversized request | denialOfService | Request bytes | medium likelihood, minor impact | Bounded request: gate acceptance vectors at the request bound, one byte over it, and at the guest allocation bound, replayed by prismpm verify |
| Rule drifts from the prize kit | tampering | Model source | low likelihood, critical impact | Bridged to the prize kit: review rule30-bridge/Rule30Bridge.lean; gate make check-research |
| Substituted holo | spoofing | Published holo | low likelihood, critical impact | Fingerprint and provenance: gate actions/attest-build-provenance in the pages workflow; gate prism-code check of the holo identities in the page |
| Substituted host | spoofing | Published holo | low likelihood, critical impact | accepted: A page cannot defend against its own host. The holo carries signed build provenance a visitor can check, and the app can be rebuilt from its prompt. |
| Tampered model | tampering | Model source | low likelihood, major impact | Regenerated from the prompt: gate prismpm verify in the SDK image prismpm.lock pins; review app/prompt.json |

## Quality

ISO/IEC 25010:2023 requirements. Each has a measure and a threshold that a theorem pins.

| Requirement | Characteristic | Measure | Threshold |
| --- | --- | --- | --- |
| Bounded allocation: The guest allocates at most 176 bytes for one request. | Performance efficiency: Resource utilization | Guest allocation bytes | 176 |
| Bounded request: A request over 88 bytes is refused before any field is read. | Performance efficiency: Time behaviour | Request bytes read | 88 |
| Every property proved: All 2 properties are theorems the Lean kernel checks. | Security: Integrity | Unproved properties | 0 |
| Every request answered: Every request gets an answer: a rule, off otherwise, or invalid. | Functional suitability: Functional completeness | Unanswered requests | 0 |
| Every vector replays: All 19 acceptance vectors replay in the compiled guest, the shortest 0 bytes long. | Reliability: Faultlessness | Failed vectors | 0 |
| Examples answered as stated: Every one of the 8 examples of the spec is answered as it states. | Functional suitability: Functional correctness | Example mismatches | 0 |
| Whole truth table pinned: Each of the eight neighbourhoods of three cells is an acceptance example, so the table is checked row by row against Core.lex.tex. | Maintainability: Testability | Neighbourhoods without an example | 0 |

## Compliance

One obligation per standard, each naming its evidence.

| Standard | Subject | Evidence |
| --- | --- | --- |
| ISO/IEC/IEEE 42010:2022 | Architecture description | Architecture::architectureDescriptionHolds |
| ISO/PAS 19450:2015 and OMG UML 2.5.1 | Design views | Design::viewOpmDecide, Design::viewUmlComponents, Design::viewUmlRequest, Design::viewUmlStates |
| ISO/IEC 25010:2023 | Product quality | Quality::qualityModelHolds |
| ISO/IEC 27034-1:2011 and ISO/IEC 27005:2022 | Application security and risk | Security::controlSet |
| OMG DMN 1.5, hit policy FIRST | Decision table | RuleThirtyCell::judge |
| OpenSpec | Requirements | RuleThirtyCell::application |
| SPDX MIT | Licensing | RuleThirtyCell::application |

## Rendered design views

Written by the SDK from the design records when it verified the app.

### design/Design.viewOpmDecide.opl

```
View: Design::viewOpmDecide
Title: Deciding a Rule 30 cell request
Viewpoint: Architecture::viewpointResearcherCorrectAnswers
Notation: ISO/PAS 19450:2015 OPM, Prism OPL profile

componentBrowser is an object.
componentRule30CellGuest is an object.
componentRule30CellGuest can be stateDeciding or stateIdle.
processDecide is a process.
processEncodeAnswer is a process.
processJudge is a process.
processParseRequest is a process.
componentRule30CellGuest handles processDecide.
processParseRequest requires componentBrowser.
processEncodeAnswer affects componentBrowser.
processJudge invokes processEncodeAnswer.
processParseRequest invokes processJudge.
processDecide zooms into processParseRequest, processJudge, and processEncodeAnswer, in that sequence.

```

### design/Design.viewUmlComponents.puml

```
@startuml
' UML 2.5.1 component diagram
' view: Design::viewUmlComponents
' viewpoint: Architecture::viewpointVerifierIntegrityOfThePublishedApp
title Components of Rule 30 cell
component "componentBrowser" as c0
component "componentGitHubPages" as c1
component "componentPrismBuild" as c2
component "componentR30CommandSurface" as c3
component "componentRule30CellGuest" as c4
component "componentRule30CellPage" as c5
component "componentRule30PrizeKit" as c6
component "componentSourceRepository" as c7
c0 --> c4 : edgeBrowserToRule30CellGuest
c1 --> c0 : edgeGitHubPagesToBrowser
c2 --> c4 : edgePrismBuildToRule30CellGuest
c2 --> c5 : edgePrismBuildToRule30CellPage
c3 --> c4 : edgeR30CommandSurfaceToRule30CellGuest
c4 --> c0 : edgeRule30CellGuestToBrowser
c4 --> c3 : edgeRule30CellGuestToR30CommandSurface
c4 --> c6 : edgeRule30CellGuestToRule30PrizeKit
c5 --> c1 : edgeRule30CellPageToGitHubPages
c6 --> c4 : edgeRule30PrizeKitToRule30CellGuest
c7 --> c2 : edgeSourceRepositoryToPrismBuild
@enduml

```

### design/Design.viewUmlRequest.puml

```
@startuml
' UML 2.5.1 sequence diagram
' view: Design::viewUmlRequest
' viewpoint: Architecture::viewpointResearcherCorrectAnswers
title Answering a Rule 30 cell request
participant "componentBrowser" as p0
participant "componentRule30CellGuest" as p1
p0 -> p1 : processDecide
p1 --> p0 : processDecide
@enduml

```

### design/Design.viewUmlStates.puml

```
@startuml
' UML 2.5.1 state machine diagram
' view: Design::viewUmlStates
' viewpoint: Architecture::viewpointVerifierRefusedMalformedRequests
title States of the Rule 30 cell guest
state "stateAnsweredOff" as s0
state "stateAnsweredOn" as s1
state "stateDeciding" as s2
state "stateIdle" as s3
state "stateRefused" as s4
[*] --> s3
s3 --> s2 : processParseRequest
s3 --> s4 : processParseRequest
s2 --> s1 : processRule1
s2 --> s1 : processRule2
s2 --> s1 : processRule3
s2 --> s0 : processOtherwise
s0 --> s3 : processEncodeAnswer
s1 --> s3 : processEncodeAnswer
s4 --> s3 : processEncodeAnswer
@enduml

```

## Prism source

Every file the builder wrote, laid out as a repository created from UOR-Foundation/template; the download prism-rule-thirty-cell.zip has them all.

- app/src/Architecture.lex.tex (413 lines)
- app/src/Compliance.lex.tex (56 lines)
- app/src/Design.lex.tex (514 lines)
- app/src/Features.lex.tex (95 lines)
- app/src/Quality.lex.tex (361 lines)
- app/src/Security.lex.tex (509 lines)
- app/src/RuleThirtyCell.lex.tex (199 lines)
- app/src/RuleThirtyCellProofs.lex.tex (71 lines)
- app/lexlean.toml (43 lines)
- app/prompt.json (299 lines)
- model/ids.toml (53 lines)
- features/suites/rule\_thirty\_cell.feature (32 lines)
- crates/conformance/tests/rule\_thirty\_cell.rs (112 lines)
- site/app.json (90 lines)
- openspec/specs/rule-thirty-cell/spec.md (136 lines)
