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ć.
Podczas klasyfikacji maszyn abstrakcyjnych, jedno z najprostszych rozróżnień dotyczy liczby operacji, które mogą wykonywać w danym punkcie. 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ść do manipulowania stosem danych wejściowych, a nie po prostu odpowiadania na nie jeden przez One w kolejności, w jakiej się pojawiają.
Wolfram Mathworld podaje dwa słynne przykłady maszyn abstrakcyjnych. Jednym z tych przykładów jest gra Conwaya, która jest deterministyczną maszyną abstrakcyjną, ponieważ tylko jedna konfiguracja może wyłonić się z dowolnej innej. Ta gra wykorzystuje siatkę, w której każde pudełko lub komórka może albo mieć stan „żyjący” lub „martwy”. 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.
Inny przykład, maszyna Turinga, jest jedną z najbardziej podstawowych i podstawowych maszyn abstrakcyjnych w informatyce. Maszyna Turinga wykonuje operacje na taśmie - ciąg symboli -nieograniczonej wielkości. Zawiera instrukcje zarówno dotyczące zmiany symboli, jak i zmiany symbolu, na którym działa. Prosta maszyna Turinga może mieć tylko instrukcję „Symbol transformacji na 1, a następnie poruszać się w prawo”. Ta maszyna wyświetliłaby tylko ciąg 1. 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ę to samo wejście.
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 dyscypliny.