Числення Поста — клас числень, який запропонував американський математик Еміль Пост. Числення Поста можна розглядати як математичне уточнення інтуїтивного поняття алгоритму.
Визначення
Численням Поста називається четвірка виду , де:
- алфавіт числення,
- список слів в алфавіті A, що називається аксіомами,
- алфавіт змінних, при чому
- список правил виведення.
Список правил виведення має вигляд:
де
- та
- деякі конкретні слова в алфавіті A,
- ,
- деякі (не обов'язкові відмінні між собою) літери алфавіту P.
Слово Q називається виводимим із слів по описаному правилу, якщо для кожної змінної та знайдеться таке слово в алфавіті A, що, якщо підставити всі ці слова на місця входження цих змінних в описаному правилі, то отримаємо вираз виду:
— |
Список слів називається виводом в численні , якщо кожне його слово є або аксіомою, або виводимо із попередніх слів по одному із правил виведення. Слово D називається виводимим в численні , якщо існує вивід, останнім словом якого є слово D.
Властивості числення Поста
Доведено, що будь-яку рекурсивно перелічену множину слів в алфавіті A можна отримати як множину виводимих слів у спеціально підібраному численні Поста, що має лише скінченну кількість аксіом та правил виведення. Еміль Пост довів, що такий самий результат справедливий для більш вузького класу числень, так званих нормальних канонічних числень, всі правила яких мають вигляд .
Разом з тим, числення Поста, які мають правила виводу
породжують лише регулярні події в теорії автоматів.
Числення Поста виявились дуже зручними для зведення їх до різноманітних алгоритмічних проблем дискретної математики та теоретичної кібернетики. Тим самим була доведена алгоритмічна нерозв'язність цілого ряду проблем, наприклад проблема тотожності слів в напівгрупах, проблема розпізнавання повноти для скінченних автоматів тощо.
Джерела інформації
- Енциклопедія кібернетики, т. 2, с. 188.
Див. також
- Алгоритм
- Теорія алгоритмів
- Машина Тюринга
- Нормальні алгоритми Маркова.
- в теорії автоматів.
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Chislennya Posta klas chislen yakij zaproponuvav amerikanskij matematik Emil Post Chislennya Posta mozhna rozglyadati yak matematichne utochnennya intuyitivnogo ponyattya algoritmu ViznachennyaChislennyam Posta nazivayetsya chetvirka vidu R A A P p displaystyle mathfrak R left langle A mathfrak A P pi right rangle de A displaystyle A alfavit chislennya A displaystyle mathfrak A spisok sliv v alfaviti A sho nazivayetsya aksiomami P displaystyle P alfavit zminnih pri chomu A P displaystyle A cap P emptyset p displaystyle pi spisok pravil vivedennya Spisok pravil vivedennya maye viglyad G 1 1 p 1 1 G 1 2 p 1 2 G 1 n p 1 n G 1 n 1 displaystyle G 1 1 p 1 1 G 1 2 p 1 2 dots G 1 n p 1 n G 1 n 1 G 2 1 p 2 1 G 2 2 p 2 2 G 2 n p 2 n G 2 n 1 displaystyle G 2 1 p 2 1 G 2 2 p 2 2 dots G 2 n p 2 n G 2 n 1 G m 1 p m 1 G m 2 p m 2 G m n p m n G m n 1 G 1 p 1 G 2 p 2 G n p n G n 1 displaystyle G m 1 p m 1 G m 2 p m 2 dots G m n p m n G m n 1 over G 1 p 1 G 2 p 2 dots G n p n G n 1 de G i j 1 i m 1 n i 1 displaystyle G i j 1 leq i leq m 1 leq n i 1 ta G k 1 k n 1 displaystyle G k 1 leq k leq n 1 deyaki konkretni slova v alfaviti A p i j 1 i m 1 j n displaystyle p i j 1 leq i leq m 1 leq j leq n p k 1 k n displaystyle p k 1 leq k leq n deyaki ne obov yazkovi vidminni mizh soboyu literi alfavitu P Slovo Q nazivayetsya vivodimim iz sliv Q 1 Q m displaystyle Q 1 dots Q m po opisanomu pravilu yaksho dlya kozhnoyi zminnoyi p i j displaystyle p i j ta p k displaystyle p k znajdetsya take slovo v alfaviti A sho yaksho pidstaviti vsi ci slova na miscya vhodzhennya cih zminnih v opisanomu pravili to otrimayemo viraz vidu Q 1 Q 2 Q m displaystyle begin matrix Q 1 Q 2 vdots Q m end matrix Q displaystyle Q Spisok sliv nazivayetsya vivodom v chislenni R displaystyle mathfrak R yaksho kozhne jogo slovo ye abo aksiomoyu abo vivodimo iz poperednih sliv po odnomu iz pravil vivedennya Slovo D nazivayetsya vivodimim v chislenni R displaystyle mathfrak R yaksho isnuye vivid ostannim slovom yakogo ye slovo D Vlastivosti chislennya PostaDovedeno sho bud yaku rekursivno perelichenu mnozhinu sliv v alfaviti A mozhna otrimati yak mnozhinu vivodimih sliv u specialno pidibranomu chislenni Posta sho maye lishe skinchennu kilkist aksiom ta pravil vivedennya Emil Post doviv sho takij samij rezultat spravedlivij dlya bilsh vuzkogo klasu chislen tak zvanih normalnih kanonichnih chislen vsi pravila yakih mayut viglyad Q p p Q 1 displaystyle Q p pQ 1 Razom z tim chislennya Posta yaki mayut pravila vivodu Q p Q 1 p displaystyle Qp over Q 1 p porodzhuyut lishe regulyarni podiyi v teoriyi avtomativ Chislennya Posta viyavilis duzhe zruchnimi dlya zvedennya yih do riznomanitnih algoritmichnih problem diskretnoyi matematiki ta teoretichnoyi kibernetiki Tim samim bula dovedena algoritmichna nerozv yaznist cilogo ryadu problem napriklad problema totozhnosti sliv v napivgrupah problema rozpiznavannya povnoti dlya skinchennih avtomativ tosho Dzherela informaciyiEnciklopediya kibernetiki t 2 s 188 Div takozhAlgoritm Teoriya algoritmiv Mashina Tyuringa Normalni algoritmi Markova v teoriyi avtomativ Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi