Turingi masin [tj'uuringi] on Alan Turingi 1937. aastal kirjeldatud lihtne abstraktne arvuti, mida kasutatakse arvutatavuse ja selle piiride uurimiseks.

Turingi masin koosneb mõlemas suunas lõpmata pikast lindist, mis on jagatud ühesugusteks pesadeks. Iga pesa võib olla kahes asendis: tähisega või tähiseta. Turingi masinal on viis võimalikku operatsiooni: teha samm vasakule, teha samm paremale, kirjutada pessa tähis, kustutada pesast tähis ja kontrollida, kas pesas on tähis.

Universaalse Turingi masina korral määrab lint ära ka teise Turingi masina. Algselt on tähised lõplikus hulgas pesades, ülejäänutes on tühikud. Sisemälu on igal ajahetkel mingis konkreetses seisundis ja taoliste seisundite hulk on lõplik.

Masina tegevusi juhtivad reeglid on deterministlikud ja on defineeritud seisunditabelis. Iga seisundi ja iga lindil oleva tähise kohta on tabelis kirje masinapoolse tegevuse ja järgmise seisundi kohta.

Kuna masina seisundite ja lindil olevate tähiste arv on lõplik, siis on ka tabel lõpliku suurusega ja seda saab hoida lindil. Eksisteerib universaalne Turingi masin ${\displaystyle M_{u))$, mis on võimeline jäljendama iga Turingi masinat, sealhulgas iseennast. Kui masina ${\displaystyle M}$ seisunditabel on kirjutatud ${\displaystyle M_{u))$ lindile, siis teostab universaalne masin ${\displaystyle M_{u))$ samu operatsioone mis ${\displaystyle M}$. Universaalne masin teeb seda, leides masina ${\displaystyle M}$ seisunditabeli järgi selle tegevused iga võimaliku sisendi korral.

Arvutusmudel, käsustik, programmeerimiskeel või rakuautomaat, mis suudab simuleerida mistahes Turingi masinat, kutsutakse Turing-täielikuks.^[1]

• Churchi tees
• Entscheidungsproblem

• Palm, Reimo; Prank, Rein 1994. Sissejuhatus matemaatilisse loogikasse. Tartu.

• Alan Turingi "On Computable Numbers, With an Application to the Entscheidungsproblem"
• Märksõna Turing Machine Stanfordi ülikooli filosoofialeksikonis.
• Teaduse helisõnastik: Turingi masin (Leo Mõtus) – ERR Teadus, 14. jaanuar 2010
• Härmel Nestra: Turingi masinad (arhiivitud originaalist 16. november 2007)