Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Көрсеткіштердің теңдігіне қатысты шешімдік мәселе
Decision problem pertaining to equivalence of expressions
Есептеу математикасында сөздік мәселе – екі берілген көрсеткіштің қайта жазу сәйкестіктері жинағына қатысты теңдігін анықтау мәселесі болып табылады. Типик мысал – топтар үшін сөздік мәселе, бірақ одан да көп мысалдар бар. Есептеу теориясының маңызды нәтижесі – осы сұраққа жауап беру көптеген маңызды жағдайларда шешілмейтін болып табылады. Мысалы, біреу , , және көрсеткіштері үшін нормалды түрін анықтап, осы көрсеткіштерді сол формаға түрлендіру жүйесін құрастыруы мүмкін, осы арқылы барлық теңдес көрсеткіштер бірдей нормалды формаға түрлендіріледі. Алайда, сөздік мәселенің барлық шешімдері нормалды форма теоремасын қолданбайды, кейбір алгебралық қасиеттер алгоритмнің бар екенін тікелей көрсетпейді, бірақ оның болуын білдіреді.
In computational mathematics, a word problem is the problem of deciding whether two given expressions are equivalent with respect to a set of rewriting identities. A prototypical example is the word problem for groups, but there are many other instances as well. A deep result of computational theory is that answering this question is in many important cases undecidable. For example one might decide that is the normal form of , , and , and devise a transformation system to rewrite those expressions to that form, in the process proving that all equivalent expressions will be rewritten to the same normal form. But not all solutions to the word problem use a normal form theorem there are algebraic properties which indirectly imply the existence of an algorithm.
Жартылай Тью жүйелері үшін сөз мәселесі
Сызықтарды қайта жазу жүйелерінің (жартылай Thue жүйелері немесе жартылай топтар) қолжетімділік мәселесін былай қоюға болады: Берілген жартылай Thue жүйесі және екі сөз (жол) үшін, ? ережелерін қолдану арқылы -ға түрлендіріле ала ма? Мұнда қайта жазу бір бағытта ғана жүреді. Сөз мәселесі – симметриялық қайта жазу қатынастарының, яғни Thue жүйелерінің қолжетімділік мәселесі. Қолжетімділік және сөз мәселелері шешілмейді, яғни осы мәселені шешу үшін жалпы алгоритм жоқ. Бұл тіпті жүйелерді шекті ұсыныстармен, яғни шекті символдар жиынымен және осы символдар арасындағы қатынастардың шекті жиынымен шектеген жағдайда да қолданылады.
The accessibility problem for string rewriting systems (semi Thue systems or semigroups) can be stated as follows: Given a semi Thue system and two words (strings) , can be transformed into by applying rules from ? Note that the rewriting here is one way. The word problem is the accessibility problem for symmetric rewrite relations, i. e. Thue systems. The accessibility and word problems are undecidable, i. e. there is no general algorithm for solving this problem. This even holds if we limit the systems to have finite presentations, i. e. a finite set of symbols and a finite set of relations on those symbols.
Топтар үшін сөз проблемасы
G тобының берілген презентациясын қарастыра отырып, сөздік мәселе – бұл S ішіндегі екі сөз берілгенде, олардың G тобының бірдей элементін көрсететінін анықтаудың алгоритмдік мәселесі. Сөздік мәселе – 1911 жылы Макс Дехн ұсынған топтар үшін қарастырылған үш алгоритмдік мәселенің бірі. 1955 жылы Пётр Новиков шекті түрде берілген G тобы бар екенін көрсетті, онда G тобы үшін сөздік мәселе шешілмейді.
Given a presentation for a group G, the word problem is the algorithmic problem of deciding, given as input two words in S, whether they represent the same element of G. The word problem is one of three algorithmic problems for groups proposed by Max Dehn in 1911. It was shown by Pyotr Novikov in 1955 that there exists a finitely presented group G such that the word problem for G is undecidable.
Комбинаторлық және ламбдалық есептеудегі сөз мәселесі
Сөз мәселесінің шешілмейтіндігіне ең алғашқы дәлелдердің бірі комбинаторлық логика үшін келді: комбинаторлардың екі тізбегі қай жағдайда эквивалентті болады? Комбинаторлар барлық мүмкін Тьюринг машиналарын кодтайды, ал екі Тьюринг машинасының эквиваленттілігі шешілмейтін болғандықтан, комбинаторлардың екі тізбегінің эквиваленттілігі де шешілмейтін болады. Алонзо Черч мұны 1936 жылы байқаған. Сол сияқты, (типтелмеген) лямбда-калькулда да шамамен бірдей мәселе бар: екі әртүрлі лямбда өрнегі берілгенде, олардың эквивалентті екенін немесе емесін анықтай алатын алгоритм жоқ; эквиваленттілік шешілмейтін. Лямбда-калькулының бірнеше типтелген нұсқалары үшін эквиваленттілік нормалды формаларды салыстыру арқылы шешіледі.
One of the earliest proofs that a word problem is undecidable was for combinatory logic: when are two strings of combinators equivalent? Because combinators encode all possible Turing machines, and the equivalence of two Turing machines is undecidable, it follows that the equivalence of two strings of combinators is undecidable. Alonzo Church observed this in 1936. Likewise, one has essentially the same problem in (untyped) lambda calculus: given two distinct lambda expressions, there is no algorithm which can discern whether they are equivalent or not; equivalence is undecidable. For several typed variants of the lambda calculus, equivalence is decidable by comparison of normal forms.
Абстрактілі қайта жазу жүйелері үшін сөз проблемасы
Абстрактты қайта жазу жүйесі (ARS) үшін сөз мәселесі өте тұжырымды: берілген x және y нысандары қатысты тең бе? АРС үшін сөз мәселесі жалпы жағдайда шешілмейді. Дегенмен, әрбір нысан шекті сандағы қадамдарда бірегей қалыпты түріне келгенде (яғни, жүйе жинақты болса) сөз мәселесінің есептеу арқылы шешімі бар: екі нысан бойынша тең болады, егер және тек егер олар бірдей қалыпты түрге келсе. Кнут-Бендикс толықтыру алгоритмі теңдеулер жиынтығын жинақты термин қайта жазу жүйесіне түрлендіру үшін қолданылуы мүмкін.
The word problem for an abstract rewriting system (ARS) is quite succinct: given objects x and y are they equivalent under ? The word problem for an ARS is undecidable in general. However, there is a computable solution for the word problem in the specific case where every object reduces to a unique normal form in a finite number of steps (i. e. the system is convergent): two objects are equivalent under if and only if they reduce to the same normal form. The Knuth Bendix completion algorithm can be used to transform a set of equations into a convergent term rewriting system.
Жалпыға бірдей алгебрадағы сөз мәселесі
Универсалды алгебрада A генераторлық жиынынан, A-дағы шекті арлықтағы операциялар жиынтығынан және осы операциялар орындауы тиіс сәйкестіктердің шекті жиынтығынан тұратын алгебралық құрылымдар зерттеледі. Алгебраның сөздік проблемасы – генераторлар мен операцияларды қолданатын екі өрнектің (сөздердің) алгебраның сәйкестіктер бойынша бірдей элементін көрсететінін анықтау болып табылады. Топтар мен жартылай топтар үшін сөздік проблемаларды алгебралар үшін сөздік проблемалар түрінде қоюға болады. Қазіргі кезде белгілі нәтижелердің жалғызы – бір генератордағы еркін Хейтинг алгебрасы шексіз екендігі және бір генератордағы еркін толық Хейтинг алгебрасы бар (және ол еркін Хейтинг алгебрасынан бір элементке көп).
In universal algebra one studies algebraic structures consisting of a generating set A, a collection of operations on A of finite arity, and a finite set of identities that these operations must satisfy. The word problem for an algebra is then to determine, given two expressions (words) involving the generators and operations, whether they represent the same element of the algebra modulo the identities. The word problems for groups and semigroups can be phrased as word problems for algebras. The only known results are that the free Heyting algebra on one generator is infinite, and that the free complete Heyting algebra on one generator exists (and has one more element than the free Heyting algebra).