Abstrakcyjne maszyny, zwane też automatami, są elementem informatyki teoretycznej. Abstrakcyjna maszyna przypomina funkcję w matematyce. Otrzymuje dane wejściowe i wytwarza produkty zgodnie z określonymi regułami. Maszyny abstrakcyjne różnią się od maszyn bardziej dosłownych, ponieważ zakłada się, że działają doskonale i niezależnie od sprzętu. Są one podzielone na typy na podstawie cech, takich jak sposób wykonywania swoich operacji i rodzaje wejść, które mogą otrzymać.
Podczas klasyfikowania abstrakcyjnych maszyn jedno z najprostszych rozróżnień dotyczy liczby operacji, które mogą wykonać w danym momencie. Maszyna abstrakcyjna nazywana jest deterministyczną, jeśli zawsze istnieje tylko jeden sposób jej działania. Jest niedeterministyczne, jeśli istnieje wiele możliwości dla maszyny w co najmniej jednym z jej możliwych stanów. Automat „spychający” to taki, który ma zdolność manipulowania stosem danych wejściowych, zamiast po prostu odpowiadać na nie jeden po drugim w kolejności, w jakiej się pojawiają.
Wolfram MathWorld podaje dwa słynne przykłady abstrakcyjnych maszyn. Jednym z takich przykładów jest gra w życie Conwaya, która jest deterministyczną maszyną abstrakcyjną, ponieważ tylko jedna konfiguracja może wyłonić się z każdej innej. Ta gra wykorzystuje siatkę, w której każde pudełko lub komórka może mieć stan „żywy” lub „martwy”. Stan całej sieci ustalany jest na podstawie stanu poprzedniego. Jeśli żywa komórka dotyka dokładnie dwóch lub trzech innych żywych komórek, nadal żyje. Jeśli ma jednego, dwóch lub więcej niż trzech sąsiadów (maksymalnie ośmiu), umiera. Ożyje martwa komórka z dokładnie trzema sąsiadami; w przeciwnym razie pozostanie martwy.
Inny przykład, maszyna Turinga, jest jedną z najbardziej podstawowych i fundamentalnych abstrakcyjnych maszyn w informatyce. Maszyna Turinga wykonuje operacje na taśmie — ciągu symboli — o nieograniczonej wielkości. Zawiera instrukcje dotyczące zarówno zmiany symboli, jak i zmiany symbolu, na którym działa. Prosta maszyna Turinga może mieć tylko instrukcję „przekształć symbol w 1, a następnie przesuń się w prawo”. Ta maszyna wyprowadzałaby tylko ciąg jedynek. Ta prosta maszyna Turinga jest deterministyczna, ale możliwe jest również konstruowanie niedeterministycznych maszyn Turinga, które mogą wykonywać kilka różnych operacji przy tych samych danych wejściowych.
Te abstrakcyjne maszyny mogą służyć wielu celom. Mogą być zabawnymi zabawkami teoretycznymi, ale mogą również służyć jako modele dla prawdziwych systemów komputerowych. Abstrakcyjna maszyna jest sercem dyscypliny informatyki.