Informeel gezegd is een automaat een “apparaat” dat, uitgaande van een begintoestand, via de stappen van een vastgelegd programma een nieuwe toestand “berekent”. De automaat leest invoer. Het programma zorgt er voor dat steeds een nieuwe toestand wordt berekend. Het programma kan uiteindelijk in een laatste toestand stoppen, maar het kan ook zijn dat er geen einde komt aan het programma.
Bij een automaat denkt men direct aan een computer. En niet ten onrechte. Een computer is een automaat. In dit artikel wordt echter de nadruk gelegd op een paar “wiskundige” automaten.
Bij Cellular automaten gaat het om de waarde van cellen, die in een vaste positie ten opzichte van elkaar zijn opgesteld. In het meest eenvoudige geval kunnen de cellen alleen de waarde 0 of een 1 aannemen en liggen de cellen naast elkaar in een ééndimensionale rij.
Het “programma” van de automaat geeft aan op welke wijze de nieuwe waarden in de cellen worden berekend. Voor alle cellen wordt tegelijkertijd een nieuwe waarde berekend. Die uitkomst per cel wordt berekend uitgaande van de huidige waarde in die cel en de huidige waarde van cellen in zijn directe omgeving (zijn buren). … Overzicht 1-dimensionale automaten
Variaties op het thema zijn automaten waarin het aantal waarden in een cel groter is dan alleen de waarden 0 of 1 en automaten waarvan het rooster meer dan 1-dimensionaal is. Als de waarden niet alleen een 0 of een 1 hoeft te zijn worden de verschillende waarden vaak weergegeven met een bepaalde kleur (bijvoorbeeld 0=rood, 1=groen en 2=blauw). In twee-dimensionale roosters kan dit tot soms spectaculair mooie patronen leiden. Ook is het mogelijk om in een 2-dimensionale ‘wereld’ een volledig werkende computer te bouwen. … Overzicht 2-dimensionale automaten
Een Deterministic Finite State automaat (DFA) is het mathematisch model van een automaat, die een verzameling woorden over een alphabeth herkent. Het wordt ook wel een recogizer of een acceptor genoemd. De automaat is bedoeld om te reageren op invoer-woorden, die opgebouwd zijn uit tekens van een bepaald alfabeth en moet nagaan of een ingevoerd woord geacepteerd of verworpen moet worden. Het is bijvoorbeeld mogelijk om een DFA te maken die nagaat of een woord, bestaande uit ascii-tekens, een acceptabele datum is. In tegenstelling tot een Turing machine (zie hieronder) heeft een DFA geen extern schrijf-geheugen. … Overzicht DFA’s
Turing machines zijn ‘wiskundig versimpelde’ computers. Er wordt uitgegaan van een 1-dimensionaal lees/schrijf-geheugen met cellen die alleen de waarde uit een alphabet (het alphabeth kan beperkt worden tot alleen een 0 of 1) kunnen aannemen. Daarnaast is er een programma.
Er is een lees/schrijf-kop die steeds naar een volgende cel of naar een vorige cel kan worden verschoven. Alleen de cel onder de kop kan worden gelezen. En er kan alleen een schrijf-opdracht voor die cel onder de kop worden gegeven. Bij een Turing machine wordt dus slechts één cel tegelijkertijd gewijzigd.
Het programma kan maar een erg beperkt aantal instructies geven (zoals b.v. ga met kop naar rechts). Voor het vastleggen van het programma wordt gebruik gemaakt van een tabel. In de tabel staan een aantal rijen, waarin achtereenvolgens 1-een toestandscode, 2-de huidige waarde onder de leeskop 3-welke instructie moet worden uitgevoerd en 4-wat de volgende toestandscode zal worden.
Op de site van de Stanford Encyclopaedia is meer te vinden over deze computers. Daar wordt o.a. ook een formele definitie van een Turing machine gegeven.
Deze netwerken worden gebruikt om parallelle processen te analyseren. Zowel geschikt voor computernetwerken als voor bedrijfs-processen.
Petri netwerken hebben een graaf (graph) als onderliggende structuur. Er zijn twee soorten nodes: Place-nodes en Transition-nodes. Verder is het zo dat Places met Transitions zijn verbonden, nooit Places met Places of Transitions met Transitions. Wiskundig uitgedrukt kun je zeggen dat er sprake is van een bipartite graaf. Verder is de graaf gericht: de verbindingen tussen Places en Transitions (de edges) hebben een pijlpunt. Een Transition heeft dus een aantal Places als input en een aantal Places als output.
De Transitions kunnen actief worden. Het is niet zo dat alle Transitions actief zijn of dat steeds slechts één Transition actief is. Voor het bijhouden welke Transition-nodes aktief kunnen worden wordt gebruik gemaakt van tokens (vaak aangegeven door een dikke zwarte punt). In de Places staan 0, 1 of meer tokens. En een Transition wordt kan actief worden als al zijn input-Places een token hebben. Als een Transitionzijn aktie uitvoert wordt uit alle input-Places een token weggehaald en in alle output-Places wordt een token geplaatst.
Op Wikipedia is meer te vinden over Petri netwerken.