|
Труды Математического института имени В. А. Стеклова, 1967, том 93, страницы 50–88
(Mi tm2826)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Общая теория алгорифмов и исчислений
Простые примеры неразрешимых канонических исчислений
Ю. В. Матиясевич
Аннотация:
В работе приведен пример ассоциативного исчисления в двубуквенном алфавите с определяющей системой из 5 соотношений, для которого неразрешима проблема эквивалентности фиксированному слову. Также указаны примеры неразрешимых нормального и ограниченного исчислений, имеющих соответственно 9 и 18 производящих схем. Кроме того, в работе приведена однопосылочная производящая схема $\mathbf T$ такая, что любое перечислимое множество слов в произвольном алфавите может быть задано каноническим исчислением в однобуквенном расширении этого алфавита,
имеющим одну аксиому и одну производящую схему – схему $\mathbf T$. Указан способ построения по произвольному алфавиту $A$ слова $\mathbf S(A)$ в однобуквенном расширении этого алфавита такого, что любое перечислимое множество слов в алфавите $A$ может быть задано каноническим исчислением
в однобуквенном расширении этого алфавита, имеющим лишь одну аксиому – слово $\mathbf S(A)$ и одну однопосылочную производящую схему.
Библ. – 13 назв.
Образец цитирования:
Ю. В. Матиясевич, “Простые примеры неразрешимых канонических исчислений”, Проблемы конструктивного направления в математике. 4, Сборник работ, Тр. МИАН СССР, 93, Наука. Ленинградское отделение, Ленинград, 1967, 50–88
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tm2826 https://www.mathnet.ru/rus/tm/v93/p50
|
Статистика просмотров: |
Страница аннотации: | 453 | PDF полного текста: | 233 |
|