Abstraktni stroji, imenovani tudi avtomati, so element teoretičnega računalništva. Abstraktni stroj je podoben funkciji v matematiki. Sprejema vložke in proizvaja izhode po določenih pravilih. Abstraktni stroji se razlikujejo od bolj dobesednih strojev, ker se domneva, da delujejo popolnoma in neodvisno od strojne opreme. Razdeljeni so na vrste na podlagi značilnosti, na primer, kako izvajajo svoje operacije in katere vrste vložkov lahko prejmejo.
Pri razvrščanju abstraktnih strojev se ena najpreprostejših razlik nanaša na število operacij, ki jih lahko izvajajo na kateri koli točki. Abstraktni stroj se imenuje determinističen, če vedno obstaja samo en način, da nadaljuje. Nedeterministično je, če za stroj obstaja več možnosti v vsaj enem od njegovih možnih stanj. “Potisni” avtomat je tisti, ki ima sposobnost manipulirati s svojim nizom vhodov, namesto da se preprosto odzove nanje enega za drugim v vrstnem redu, v katerem se pojavljajo.
Wolfram MathWorld daje dva znana primera abstraktnih strojev. Eden od teh primerov je Conwayeva igra življenja, ki je deterministični abstraktni stroj, ker lahko iz katere koli druge nastane samo ena konfiguracija. Ta igra uporablja mrežo, v kateri ima lahko vsaka škatla ali celica stanje “živa” ali “mrtva”. Stanje celotne mreže se določi na podlagi prejšnjega stanja. Če se živa celica dotakne natanko dveh ali treh drugih živih celic, živi še naprej. Če ima enega, dva ali več kot tri sosede (do možnih osem), umre. Oživela bo mrtva celica z natanko tremi sosedi; drugače bo ostal mrtev.
Drug primer, Turingov stroj, je eden najbolj osnovnih in temeljnih abstraktnih strojev v računalništvu. Turingov stroj izvaja operacije na traku – nizu simbolov – neomejene velikosti. Vsebuje navodila za spreminjanje simbolov in za spreminjanje simbola, na katerem deluje. Preprost Turingov stroj ima lahko samo navodilo “pretvori simbol v 1, nato se premakni desno.” Ta stroj ne bi dal nič drugega kot niz 1. Ta preprost Turingov stroj je determinističen, vendar je mogoče sestaviti tudi nedeterministične Turingove stroje, ki lahko izvajajo več različnih operacij z istim vhodom.
Ti abstraktni stroji lahko služijo številnim namenom. Lahko so zabavne teoretične igrače, lahko pa služijo tudi kot modeli za prave računalniške sisteme. Abstraktni stroj je v središču računalništva kot discipline.