Maszyna Posta–Turinga
Model obliczeń Emila Posta z 1936 roku: robotnik poruszający się między pudełkami w nieskończonym rzędzie według ponumerowanej listy instrukcji — ta sama idea co u Turinga, opublikowana w tym samym roku, niezależnie.
Post opisał „robotnika” w pokoju z nieskończonym ciągiem pudełek, z których każde jest zaznaczone albo nie. Instrukcji było pięć: zaznacz pudełko, odznacz je, przesuń się o jedno w prawo, przesuń się o jedno w lewo, rozgałęź w zależności od tego, czy pudełko jest zaznaczone. Każda instrukcja wskazuje numer następnej. To program w nowoczesnym sensie — ponumerowana lista ze skokami — podczas gdy maszyna Turinga wyraża tę samą treść tablicą stanów.
Finite Combinatory Processes — Formulation 1 trafiło do Journal of Symbolic Logic zaledwie kilka miesięcy po artykule Turinga i Post musiał dodać przypis, że praca jest niezależna. Różnica w renomie bierze się stąd, że Post zatrzymał się na modelu, a Turing poszedł dalej i udowodnił, czego model nie potrafi. Post już w 1921 roku był blisko twierdzeń o niezupełności, ale ich nie opublikował. Nazwę „maszyna Posta–Turinga” ukuł znacznie później Martin Davis.