Müssen zelluläre Automaten notwenigerweise deterministisch sein?
-
Hi, die Frage seteht ja schon im Titel.
Ich bin ja der Meinung, dass sie es sein müssen, da sie durch eine Übergangsfunktion definiert werden. Müsste es nicht eine allgemeine Relation sein, wenn der Automat nicht deterministisch arbeiten soll? Bin mir da aber sehr unsicher...
-
Warum sollte es eine Relation sein müssen, wenn der Automat stochastisch arbeitet? Alle vernünftigen zellulären Automaten, die ich bisher gesehen habe, haben stochastische Einflüsse.
-
Also die in der Wikipedia (zellulärer Automat) beschriebenen Automaten sind alle deterministisch (und stochastische Einflüsse beziehen sich bestenfalls auf die Startbedingungen). Aber es ist bestimmt möglich, auch nichtdeterministische Automaten zu definieren, wobei ich allerdings den Sinn dahinter nicht sehe (und ein nichtdeterministischer Automat auch wieder auf einen deterministischen reduziert werden kann - Stichwort Potenzmengenkonstruktion).
-
CStoll schrieb:
Aber es ist bestimmt möglich, auch nichtdeterministische Automaten zu definieren, wobei ich allerdings den Sinn dahinter nicht sehe
Beispiel, das in der Verkehrsforschung eingesetzt wird: Man definiert ein Schachbrettmuster auf einer Straße und ein paar Übergangsregeln für Autos, die den Zielen Abstand halten, Fahren möglichst mit Maximalgeschwindigkeit usw. gerecht werden. Dazu sind Autofahrer doof und bremsen, wenn Werbeplakate mit leicht bekleideten Frauen am Rand stehen oder die Kinder auf der Rückbank Terror machen. Solche Einflüsse modelliert man stochastisch: mit Wahrscheinlichkeit p verliert ein Auto ohne erkennbaren Grund Geschwindigkeit.