Co to jest abstrakcyjna maszyna?

Maszyny abstrakcyjne, zwane także automatami, są elementem teoretycznej informatyki. Maszyna abstrakcyjna przypomina funkcję w matematyce. Odbiera dane wejściowe i wytwarza dane wyjściowe zgodnie z określonymi regułami. Maszyny abstrakcyjne różnią się od bardziej dosłownych maszyn, ponieważ zakłada się, że działają one doskonale i niezależnie od sprzętu. Są one podzielone na typy na podstawie cech, takich jak sposób, w jaki wykonują swoje operacje i jakie rodzaje danych wejściowych mogą otrzymać.

Podczas klasyfikacji maszyn abstrakcyjnych jedno z najprostszych rozróżnień dotyczy liczby operacji, które mogą wykonywać w danym momencie. Maszyna abstrakcyjna jest nazywana deterministyczną, jeśli zawsze istnieje tylko jeden sposób jej działania. Nie jest to deterministyczne, jeśli istnieje wiele możliwości dla maszyny w co najmniej jednym z jej możliwych stanów. Automat „wypychający” to taki, który ma zdolność do manipulowania swoim stosem danych wejściowych, zamiast po prostu reagować na nie jeden po drugim w kolejności, w jakiej się pojawiają.

Wolfram MathWorld podaje dwa słynne przykłady abstrakcyjnych maszyn. Jednym z tych przykładów jest gra Conwaya w życie, która jest deterministyczną abstrakcyjną maszyną, ponieważ tylko jedna konfiguracja może wyjść z 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 siatki jest ustalany na podstawie poprzedniego stanu. Jeśli żywa komórka dotknie 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. Martwa cela z dokładnie trzema sąsiadami ożyje; w przeciwnym razie pozostanie martwy.

Kolejny przykład, maszyna Turinga, jest jedną z najbardziej podstawowych i fundamentalnych abstrakcyjnych maszyn w informatyce. Maszyna Turinga wykonuje operacje na taśmie - szeregu symboli - o nieograniczonej wielkości. Zawiera instrukcje dotyczące zmiany symboli i zmiany symbolu, na którym działa. Prosta maszyna Turinga może mieć tylko instrukcję „przekształcić symbol na 1, a następnie przejść w prawo”. Ta maszyna wyświetliłaby tylko ciąg 1. Ta prosta maszyna Turinga jest deterministyczna, ale możliwe jest również zbudowanie 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 teoretycznymi zabawkami, ale mogą też służyć jako modele dla prawdziwych systemów komputerowych. Maszyna abstrakcyjna stanowi istotę dyscypliny informatycznej.