Algoritmikus va rendszer
Minden szókincs algoritmus U foglalkozik egy ábécé A, a megoldás, hogy egy adott probléma csökken a feldolgozás szavak egy adott ábécé néhány előre meghatározott szabályok S. Egy ilyen megközelítés az algoritmusok elmélete által kidolgozott AA Markov, aki azt javasolta, a koncepció egy normál algoritmus matematikai modell koncepció számítási eljárást.
Normál algoritmusok U =
Minden normális algoritmus, hogy egy algoritmus bizonyos ábécé A, generál egy determinisztikus folyamat feldolgozási szó. Ezért, bármilyen szabványos algoritmus fix ábécé A teljesen határozza megadja annak áramkör S - rendezett listáját a végső helyettesítési képletek képletű A. minden ilyen pár lényegében
Normál algoritmus U az ábécé A egy recept a feltevésen alapul, tetszőleges szót P A (PÎA *), a sorrend a szavak ai.
A fentiek fényében a algoritmikus rendszer „normális” algoritmussal a következő:
rendes alkalmazása az algoritmus a szót U nevezzük meghatározott folyamat a következő szabály szerint (ami egy folyamatábra a szokásos algoritmus):
1. Tegyük fel, hogy i = 1. Ugorjon a 2. lépésre.
2. Ellenőrizze, hogy alkalmas arra, hogy átalakítani a szó i-edik egyenlet. Ha igen, ugorjon a 3. lépésre, ha nem - az 5. lépésre.
3. Az első előfordulása egy egyszerű bal oldalán az i-edik képlet az átalakított szót helyett a jobb oldali részén az i-edik formula. Eredmény tekinthető továbbiakban átváltható szót, folytassa a 4. lépéssel.
4. Ha az i-edik formula egy végleges szubsztitúció, a folyamat megszakad. Ellenkező esetben folytassa az 1. lépéshez.
5. Ellenőrizzük, hogy van-egyenlőség i = n. Ha igen, akkor a folyamat megszakad, egyébként folytassa a 6. lépéssel.
6. növelése az i értéke 1, és ugorjon a 2. lépésre.
Bármely szó az ábécé P szolgálhatnak bemenő adatokat az algoritmus a normál ábécé A. Ebben az esetben előfordulhat olyan eset:
- A folyamat a végrehajtó algoritmus normális szóbólÎ* A képlet végeredménye ai ® · bi után véges számú lépésben. Ebben az esetben azt mondja, a szokásos algoritmus alkalmazható a szót egy, és annak teljesítménye után kapott szót bÎA * nevezzük az eredmény.
- A folyamat a végrehajtó algoritmus normális kezdeti szóbólÎ* És ez soha nem ér véget, vagy ha nem meggyőző ütköző (azaz nem a képlet ai ® · bi). Ebben az esetben azt mondjuk, hogy a szokásos algoritmus nem alkalmazható a szót a.
Algoritmus U =<í0, 1ý
Például, a szó, ez a normális 100 algoritmus folyamatosan átalakul szó 0 h10, 0h10, 00h1, h00h1, 0h0h1, h0h0h1, hh0h0h1, x0h0h1, 0xh0h1, 0x0h1, 00xh1, 00x1, 001x, 001Ù.
Az utolsó kifejezés ennek a szekvenciának kell tekinteni alkalmazásának eredménye az algoritmus a szót U a = 100, és jelöljük az U (a). Feltételezzük, hogy újrahasznosítja U a = 100 b = 001, és a levelet U (a) = b (ebben a példában, U (100) = 001).
Algoritmus U =<ía, bý,
Így szólva babaa kiindulási az első átmenetifém (azaz, a következő képlet segítségével bah® HABA), kapjuk baaaba (itt h = BAA), és miután a második (azaz, a következő képlet segítségével bah® HABA újra) van aabaaba (itt h = AABA). Képletének alkalmazásával aah® · h megszerezni az eredmény szót aabaaba Baaba (azaz U (babaa) = Baaba).
Azonban figyelembe kiindulási szavát a = Baaba, megkapjuk egy végtelen szekvencia abaaba, baabab, abababa, bababab, babababa, ... amelyben nincs szó Ááá. Ez azt jelenti, hogy az algoritmus nem alkalmazza az U egy szót = Baaba.
Ha a forrás adatok abaab felszólalni, kapunk egy véges sorozat baabb, abbaba, bbabab, amikor az utolsó szó nem szabad alkalmazni egy átmeneti, ez esetben a megállás a hiábavaló (ez azt is jelenti, nem alkalmas egy adott algoritmus U abaab szó).
Úgy gondoljuk, hogy minden algoritmus az ábécé A szokásos algoritmus U építhető ezen ábécé feldolgozása tetszőleges szót egyÎA * az azonos eredmény, amely újrahasznosítja az eredeti algoritmus B. Ez a megállapodás ismert algoritmusok elmélete, az úgynevezett normalizáció elvét.
Ebben a tekintetben az az elképzelés, finomítás algoritmus algoritmikus A.Markova rendszerek A.Chercha és A.Tyuringa egyenértékű.
További finomítása a koncepció az algoritmus kapcsolódó asszociatív fogkő, amely a készlet minden szava néhány ábécé együtt bármely véges rendszerben megengedhető helyettesítések.
Az asszociatív analízis (Thue rendszer) U - formális rendszer F. S. így a tanfolyam egyes asszociatív rendszer (félig) Ku.
Minden asszociatív fogkő U =
Megengedett tekintetében a lista # 931; akció felett szava ábécé A bármely permutációja egyik részeit bármely arányú # 945; i ↔ # 946; i ((# 945; i ↔ # 946; i)Î# 931;) bevitele helyett egy másik része azonos arányban.
Az asszociatív fogkő U =
Csere ab↔bcb vonatkozik négy módon szót P1 = abcbcbab: csere a két előfordulását a szó BCB aabcbab és abcabab, és cseréje a két előfordulását ab és ad szavakat bcbcbcbab abcbcbbcb. Ugyanakkor az út P2 = bacb ez a helyettesítés nem alkalmazható, és a helyettesítés az űrlap # 945; ↔e segítségével átalakítja szó Pi ÎA * dobnak előfordulása # 945;, és bármely két betű a konvertált szavak vagy előtte vagy mögötte a szó kerül beillesztésre # 945; (E-üres szó, eÎA *. eÏA). Minden szó a Q, amelyek ebben az esetben kapott (beleértve a legtöbb a kezdeti szó P), azt mondják, hogy azok megegyeznek a asszociatív fogkő P U =
hozzáállás # 9576; minden asszociatív fogkő U reflexív, szimmetrikus és tranzitív. Ezen túlmenően, az U: P1 # 9576; Q és P2 # 9576; R, az következik, hogy U: P1 P2 # 9576; QR. Ez egy természetes módon összehasonlítani minden asszociatív fogkő U néhány asszociatív véges Ku rendszer. véve annak elemei szavakat osztályok, amelyek egyenértékűek egymással az U =
Úgy van kialakítva, asszociatív Ku rendszer monoid, azaz lesz egy semleges elem eÎA *; Ku elemek képviselik ábécé betűit A, majd alkotnak rendszert Ku generáló elem, és a listát a kapcsolatok # 931; képviseli a teljes rendszer közötti kapcsolatok mondta Ku generáló elem abban az értelemben, hogy a Ku elemekkel. benyújtott szavakat P és Q, azonosak Ku, ha, és csak akkor, ha a P és Q egyenértékű U =
Ez magyarázza, hogy fontos a tanulás megoldhatóságának algoritmikus problémák egyenértékűségének elismeréséről szavak tetszőleges asszociatív kalkulus. A probléma abban rejlik, hogy minden U =
„Van egy asszociatív fogkő amelyben egyenértékűsége elismerésének szóval a probléma algoritmikusan megoldhatatlan”
Valóban, figyelembe véve a Turing-gép, mint egy matematikai modellt az algoritmus, tudjuk csökkenteni a problémát egyenértékűsége elismerésének szava U =
Nézzük a következő két tételt:
„Minden számozott sor permutációk létezik M rendszer, több végső szavai amely egybeesik M '
„A asszociatív fogkő két szó egyenértékű, ha megfelelnek a két konfiguráció egy Turing-gép úgy, hogy egy véges számú ciklus a gép megy az első elrendezésből a második”
Nyilvánvaló, hogy a tételt: „Van egy félcsoport által adott meghatározó kapcsolatok, amelyek egyenértékűségének elismerése probléma (egyenlőség) algoritmikusan megoldhatatlan szó” újrafogalmazása a Markov-Post tétel.
A probléma az egyenértékűség szavak asszociatív fogkő csökkentésére számos matematikai problémákat.
Így minden formula a matematika nyelvén lehet tekinteni, mint egy szót egy bizonyos ábécé. Process egyenértékű átalakításával vagy kimenet ebben az esetben egy hátrány, ezek a szavak vagy más helyettesítések jelennek axiómák identitás törvényeket.