Что означает
каждый знак.

Формулы ниже объясняют наше исполнение. Английское чтение дано вместе с русским смыслом. Исторические обозначения отдельно привязаны к статье; современная запись не выдаётся за цитату.

Практикум Тьюринг на фишках Оригинал: 36 страниц, все исходные формулы

1. Фишка и действие

b ∈ {0,1}, FLIP(b) = 1 − b

Read: “b belongs to the set zero, one. Flip of b equals one minus b.” b is the current bit; the braces name its two possible values; ∈ means “belongs to”; the minus sign specifies the opposite bit. Meaning: FLIP exchanges the two faces. Это определение переворота, а не наличие арифметического вычитания в машине.

b = DATA[h]; p′ = a_b; (h′, DATA′) = action(op,h,DATA)

Read: “b equals data at h; p prime equals a sub b; h prime and data prime are the result of the action.” h is the DATA head; p is the PROGRAM address; op is the operation; a₀ and a₁ are its two successor addresses. A prime means “after the step.” Meaning: choose the successor using the bit before the action. Это точное правило CHIP4, созданное для практикума.

w = max(1, ⌈log₂ N⌉), L = 2 + 2w

Read: “w equals the maximum of one and the ceiling of log base two of N. L equals two plus two times w.” N is the number of instructions; ⌈…⌉ rounds up; w is address width; L is instruction width. Meaning: four operation kinds need two bits; each of two successors needs its own address.

2. Номер фишки и число

i = W·y + x; v = ∑_k=0ⁿ⁻¹ b_k·2^n−1−k

Read: “i equals W times y plus x. v equals the sum, for k from zero to n minus one, of b sub k times two to the power n minus one minus k.” W is row width; x and y are zero-based column and row. n is bit count; k is bit position, counted from the most significant bit. Meaning: a matrix has a linear address; a bit sequence has a numeric interpretation only when its reading convention is fixed.

На поле 20×20 клетка (x=3,y=2) имеет адрес 43. Последовательность 0011 даёт 3. Последовательность 0000 0000 0011 0011 даёт 51 — код символа «3», а не число три в регистре калькулятора.

3. UTF-16 и глиф

u = 2¹⁰(H − D800₁₆) + (L − DC00₁₆) + 10000₁₆

Read: “u equals two to the power ten times H minus hexadecimal D eight zero zero, plus L minus hexadecimal D C zero zero, plus hexadecimal one zero zero zero zero.” H is the high surrogate in D800–DBFF; L is the low surrogate in DC00–DFFF; u is the Unicode scalar value. Meaning: a valid pair of UTF-16 units denotes one supplementary character. Для 😀: D83D DE00 → U+1F600.

code → table[code] → glyph program → 8 × 16 chips

Read: “code selects a table entry; the entry supplies a glyph program; the program produces eight by sixteen chips.” The arrow means a stage of interpretation, not an automatic command executed by the number itself. Meaning: the code and the drawing are different data. Формат таблицы и размер 8×16 — наше соглашение. Unicode не предписывает этот рисунок.

Проверенные источники: Unicode FAQ: UTF-16, Unicode FAQ: fonts and rendering. Начертания поставки наследуют атлас предыдущей версии; см. лицензия шрифта и происхождение.

4. Life на торе

n_t(x,y) = ∑_{(dx,dy)∈{−1,0,1}²∖{(0,0)}} A_t((x+dx) mod 20,(y+dy) mod 20)

Read: “n at time t and position x, y is the sum of A at time t over the eight neighboring offsets, with both coordinates taken modulo twenty.” t numbers generations; A is the current field; dx and dy are offsets; ∖ removes the centre. Meaning: count the eight neighbors, wrapping both edges.

A_t+1(x,y) = 1 ⇔ n_t = 3 ∨ (A_t = 1 ∧ n_t = 2)

Read: “the next cell equals one if and only if the neighbor count equals three, or the cell is alive and the neighbor count equals two.” ⇔ means “if and only if”; ∨ means “or”; ∧ means “and.” Meaning: B3/S23. All decisions read the old field; they write a separate next field.

A_t = A_s, s < t; μ = s, λ = t − s

Read: “A at t equals A at s, with s less than t; mu equals s; lambda equals t minus s.” Equality compares all 400 bits. μ is transient length; λ is period, when this is the first repeat. Meaning: a quiet block and a repeating oscillator have different periods. “No repeat observed” does not prove that a repeat will never occur.

Правила и одновременное обновление сверены с Martin Gardner, Scientific American, October 1970. Замыкание границ — явно выбранный нами вариант конечного поля; описание топологии см. Golly: bounded grids. Историческую цветовую технику демонстрации не отождествляем с нашим соглашением «чёрное = 1».

5. Тьюринг: обозначения и связь с исполнением

Статья On Computable Numbers, with an Application to the Entscheidungsproblem опубликована в Proceedings of the London Mathematical Society, series 2, volume 42, pp. 230–265. Наши исполняемые таблицы: §3, pp. 233–234; обозначения — §§1–2. Навигатор даёт доступ ко всем страницам и исходным формулам, включая доказательства.

q₁, q₂, …, q_R; S(r); (q_n, S(r))

Read: “q one, q two, up to q sub R; S of r; q sub n together with S of r.” q is a machine state; R is the number of states; r is the scanned square; S(r) is its symbol. Meaning: the pair selects a rule. В интерфейсе q показано как b, c, e, f или другое имя состояния; S(r) видно под головкой. S — здесь удобная типографская передача обозначения scanned symbol.

C = (q,h,T), δ(q,T(h)) = (operations,q′)

Read: “C is the triple q, h, T. Delta of q and T of h gives operations and q prime.” C is a complete configuration, q the current state, h the head position, T the tape map. δ is the rule table. Meaning: a saved state must include the whole tape, the head, and the machine state. Это наша современная формализация для JSON и интерфейса, не буквальная формула статьи. Для остановки внутри строки мы дополнительно сохраняем номер строки и следующей операции.

□ ≠ 0 ≠ 1; P0 ↔ PUT:0; P1 ↔ PUT:1; E ↔ REMOVE

Read: “blank is distinct from zero and one. P zero corresponds to put zero; P one corresponds to put one; E corresponds to remove.” The double arrow here denotes matching notations. Meaning: an empty square contains no chip. A zero is an existing white chip.

PUT:0(□) → 0; PUT:0(1) → 0; REMOVE(0) → □; FLIP(□) → error

Read: “put zero on blank gives zero; put zero on one gives zero; remove zero gives blank; flip on blank is an error.” Meaning: placement, flipping and removal are distinct physical events. The explicit FLIP spelling belongs to our physical editor; the original examples use P and E.

0.010101…₂ = ∑_k=1^∞ 2^−2k = 1/3

Read: “binary zero point zero one zero one and so on equals the sum of two to the power minus two k, for k from one to infinity, which equals one third.” k counts the one-bits. Meaning: the first example prints the digits of a number forever; a finite observation is only a prefix. Равенство с суммой — наше пояснение к примеру.

6. Описание тоже может стать данными

q_i → DAⁱ; S_j → DC^j; q_iS_jS_kRq_m

Read: “q sub i becomes D followed by i copies of A; S sub j becomes D followed by j copies of C; q i, S j, S k, R, q m.” i,m number states; j,k number symbols; exponent here means repetition. Meaning: a rule can be encoded as text. The five parts mean state, scanned symbol, replacement, movement, next state. Историческая S.D. из §5; S₀ — пустота, S₁ — 0, S₂ — 1. N в стандартном описании означает отсутствие движения.

A,C,D,L,R,N,; → 1,2,3,4,5,6,7

Read: “A, C, D, L, R, N and semicolon are replaced by one through seven.” Meaning: the standard description becomes a description number, D.N. Это отдельный исторический способ кодирования, не двоичный формат CHIP4.

Остальные разделы статьи содержат сокращённые подпрограммы, универсальную машину, диагональные рассуждения и логические доказательства. Они доступны в оригинале через навигатор. Интерфейс исполняет введённые таблицы; он не объявляет доказательства командами и не выдаёт конечный эксперимент за решение общей проблемы вычислимости. Для произвольной машины время наблюдения не доказывает, что она остановится или напечатает ещё одну цифру.

В терминологии статьи circular означает конечное число выведенных цифр первого рода; машина при этом может двигаться бесконечно. Circle-free означает бесконечный вывод таких цифр. Кнопка паузы — действие наблюдателя.

Происхождение и проверка

Калькулятор и распознаватель развивают компиляторы выпуска 2.1.0. Их старые битовые циклы развёрнуты в FLIP и адресные переходы с восстановлением проверяемой фишки. Новые коды действий, запись жестов, граф переходов, Life, файловый формат 3 и физическая машина Тьюринга реализованы в этом выпуске. Сравнение Life с независимым эталоном используется только в проверках. Реальный запуск исполняет развёрнутые инструкции.

Проверки поставки: все 200 допустимых выражений калькулятора; UTF-16 и суррогатные пары; распознавание; периоды 1, 2 и 80 на торе; случайные поля; остановки посреди исполнения; исходные последовательности §3. Исходники проверок находятся в авторском пакете.

Что означаеткаждый знак.