Az elméleti számítástechnikában és matematikai logikában a Post rendszer vagy a kanonikus Post rendszer , az úgynevezett létrehozója, Emil Post , a húrok manipulálására szolgáló rendszer, amely véges számú szóval kezdődik, és átalakítja őket egy véges szabályhalmaz alkalmazásává. meghatározott formájú, és ezáltal formális nyelvet generál . Ezek a rendszerek különösen történelmi jelentőséggel bírnak, mert bármely Post rendszert le lehet redukálni egy szó átírási rendszerre (félig Thue rendszer), amely egyszerűbb megfogalmazás. A két formalizmus - a Post rendszere és az újraírás - Turing-teljes .
A Post rendszer egy ábécé adatai, a kezdő szavak és a gyártási szabályok összessége. Például :
Íme néhány levezetett szó:
[] | kezdőszó |
[][] | a 2. szabály szerint kapott. |
[[][]] | az 1. szabály szerint kapott. |
[[][]][[][]] | a 2. szabály szerint kapott. |
[[][]][][[][]] | a 3. szabály szerint kapott. |
A kanonikus Post rendszer egy hármas , ahol
Minden szabály a következő formájú:
hol és hol vannak rögzített szavak, amelyek változókat tartalmaznak , megjegyezve , illetve a forma alakját
és
.A szavak nevezik előzményei , a szó az ebből a szabály. A követelmény az, hogy mindegyik a következményben az egyik előzményváltozó legyen, és hogy minden következmény és előzmény legalább egy változót tartalmazzon.
Általában egy gyártási szabály csak egy előzményt tartalmaz, ebben az esetben egyszerűbben íródik
.Szabályt alkalmazhatunk egy szóra, ha azt a szabály előzményének megfelelően vesszük figyelembe, azáltal, hogy minden változóhoz társítjuk a szó egy tényezőjét. A kapott szó ekkor az, ahol a következmény változóit az előzmény változóihoz tartozó értékekkel helyettesítjük. Több előzmény esetén a szót az egyes előzmények szerint kell figyelembe venni, hogy levezetjük a következményt. Maga Post bebizonyította, Minsky könyvének bizonyítékai azt bizonyítják, hogy csak egy előzménnyel lehet megelégedni a szabályokkal.
A Post rendszere által generált nyelv a kezdőszavakból és a gyártási szabályok ismételt alkalmazásával nyert szavakból álló készlet. Ezek a halmazok rekurzív módon megszámlálható nyelvek, és fordítva, bármely rekurzív módon megszámlálható nyelv az ilyen halmazok ábécére való korlátozása .
Post A rendszer normál formában van ( normál formában ), ha az összes szabály formájú
A normál formában szereplő szabályok tehát abból állnak, hogy eltávolítják az előtagot egy szó elején, és hozzáadják a szót a végén. A poszt 1943-ban bebizonyította a következő normál alakot:
A Post normál formájú tétele - Bármely Post rendszer esetén létezik ennek megfelelő normális forma Post rendszer; ez a rendszer hatékonyan kiépíthető.
A címkés játékrendszer , amely az univerzális számítás modellje is, a Post rendszer normál formájú példái; ráadásul „monogének”: Egy rendszerről akkor mondunk monogént, ha bármely lánc esetében legfeljebb egy új szó állítható elő, más szóval, ha a rendszer determinista.
Az átírási rendszer a Post rendszer speciális esete, ahol a produkciók a következő formájúak:
A produkciók helyettesítési szabályok, formában is megírva . Megmutatható, hogy bármely Post rendszer redukálható ilyen rendszerre, amely a Chomsky hierarchiában 0 típusú formális nyelvtan .