Co to jest maszyna abstrakcyjna?

Maszyny abstrakcyjne, zwane również automatami, są elementem informatyki teoretycznej.Abstrakcyjna maszyna przypomina funkcję matematyki.Otrzymuje dane wejściowe i wytwarza wyniki zgodnie z określonymi regułami.Maszyny abstrakcyjne różnią się od bardziej dosłownych maszyn, ponieważ zakłada się, że działają idealnie 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ć.dowolny punkt.Maszyna abstrakcyjna nazywa się deterministyczną, jeśli zawsze istnieje tylko jeden sposób, aby kontynuować.Jest to nieokreślone, jeśli istnieje wiele możliwości dla maszyny w co najmniej jednym z jej możliwych stanów.Automat wypychania 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

daje dwa słynne przykłady abstrakcyjnych maszyn.Jednym z tych przykładów jest Gra Life of Life, która jest deterministyczną maszyną abstrakcyjną, ponieważ tylko jedna konfiguracja może pojawić się z innej innej.Ta gra wykorzystuje siatkę, w której każde pudełko lub komórka może albo mieć państwo żyjące lub martwe.Stan całej siatki jest określany na podstawie poprzedniego stanu.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 (do możliwego ośmiu), umiera.Martwa komórka z dokładnie trzema sąsiadami ożyje;W przeciwnym razie pozostanie martwy. Kolejny przykład, maszyna Turinga, jest jedną z najbardziej podstawowych i podstawowych maszyn abstrakcyjnych w informatyce.Maszyna Turinga wykonuje operacje na taśmie mdash; ciąg symboli i mdash; nieograniczonego rozmiaru.Zawiera instrukcje zarówno dotyczące zmiany symboli, jak i zmiany symbolu, na którym działa.Prosta maszyna Turinga może mieć tylko symbol transformacji instrukcji do 1, a następnie poruszać się w prawo.Ta maszyna wyświetliłaby tylko ciąg 1s.Ta prosta maszyna Turinga jest deterministyczna, ale możliwe jest również konstruowanie niedeterministycznych maszyn Turinga, które mogą wykonywać kilka różnych operacji, biorąc pod uwagę te same dane wejściowe.

Te abstrakcyjne maszyny mogą służyć wielu celom.Mogą być zabawne zabawki teoretyczne, ale mogą również służyć jako modele prawdziwych systemów komputerowych.Maszyna abstrakcyjna leży u podstaw informatyki jako dyscyplina.