Tetris is Capable of Universal Computation

This text presents a method for embedding a programmable, general-purpose, digital computer into Tetris. It describes the capabilities and performance of an implementation that runs Tetris on Tetris.

Contents

Introduction

Fundamentals

Method Overview

Nodes

Infinite Playfield

Input Language

TetrominoScript

Logic Gates

Buffer

Inverter (NOT)

OR

NOR

NAND

AND

XOR

XNOR

Intermediate Gates

Wires

Fan-out

Fan-in

Crossing

Multiplexing

Functions

Overview

Identity

Constant

Logical Left Shift

Logical Right Shift

Logical AND

Logical AND-NOT

Bitwise AND

Bitwise OR

Bitwise XOR

Byte Swap

Byte Match

Equals

Byte Copy

Conditional Byte Copy

Decrement

Increment

Conditional Increment

Add

Subtract

Function Catalog

Memory

Implementation

Memory Code

Infinite Array Abstraction

Abstract Machines

Function Emulator

State Machine

Sequencer

Classifier

Transducer

Turing Machine

Definition

Implementation

Discussion

General-purpose Computer

Overview

Microcode

Assembly Language

Registers

Transfer Instructions

Arithmetic and Logic Instructions

Branch Instructions

Load Instructions

Store Instructions

Set Instructions

Example Program

Simulator

Applications

Overview

TetrominoScript Editor

Run

User Interface

NAND Tutorial

Wires

Translate

Export SVG

Export HTML

TetrominoScript Tester

Lookup Table Generator

Assembler

Cycle Programs Generator

General-purpose Computer

Conclusion

Acknowledgements