Apstraktni strojevi, koji se nazivaju i automati, element su teorijske računalne znanosti. Apstraktni stroj nalikuje funkciji u matematici. Prima ulaze i proizvodi izlaze prema određenim pravilima. Apstraktni strojevi razlikuju se od doslovnijih strojeva jer se pretpostavlja da funkcioniraju savršeno i neovisno o hardveru. Podijeljeni su na vrste na temelju karakteristika kao što su način na koji izvode svoje operacije i koje vrste ulaznih podataka mogu primiti.
Kada se klasificiraju apstraktni strojevi, jedna od najjednostavnijih razlika odnosi se na broj operacija koje im je dopušteno izvesti u bilo kojoj točki. Apstraktni stroj naziva se determinističkim ako uvijek postoji samo jedan način da se nastavi. Nedeterministički je ako postoji više mogućnosti za stroj u barem jednom od njegovih mogućih stanja. „Pushdown” automat je onaj koji ima sposobnost manipuliranja svojim hrpom ulaza, umjesto da jednostavno odgovara na njih jedan po jedan redoslijedom kojim se pojavljuju.
Wolfram MathWorld daje dva poznata primjera apstraktnih strojeva. Jedan od tih primjera je Conwayeva igra života, koja je deterministički apstraktni stroj jer samo jedna konfiguracija može proizaći iz bilo koje druge. Ova igra koristi mrežu u kojoj svaka kutija ili ćelija može imati stanje “živ” ili “mrtav”. Stanje cijele mreže određuje se na temelju prethodnog stanja. Ako živa stanica dodirne točno dvije ili tri druge žive stanice, ona nastavlja živjeti. Ako ima jednog, dva ili više od tri susjeda (do mogućih osam), umire. Mrtva ćelija s točno tri susjeda će oživjeti; inače će ostati mrtav.
Drugi primjer, Turingov stroj, jedan je od najosnovnijih i najosnovnijih apstraktnih strojeva u informatici. Turingov stroj izvodi operacije na vrpci – nizu simbola – neograničene veličine. Sadrži upute za promjenu simbola i za promjenu simbola na kojem radi. Jednostavan Turingov stroj može imati samo naredbu “pretvorite simbol u 1, a zatim se pomaknite udesno”. Ovaj stroj ne bi dao ništa osim niza 1. Ovaj jednostavan Turingov stroj je deterministički, ali je također moguće konstruirati nedeterminističke Turingove strojeve koji mogu izvoditi nekoliko različitih operacija uz isti ulaz.
Ovi apstraktni strojevi mogu poslužiti u mnoge svrhe. Mogu biti zabavne teorijske igračke, ali mogu poslužiti i kao modeli za stvarne računalne sustave. Apstraktni stroj je u središtu informatičke znanosti kao discipline.