Кіріспе
Шекті топтар теориясындағы мәселе. Математикада, әсіресе абстрактілі алгебра саласындағы комбинаторлық топтар теориясында, шекті түрде жасалған топ үшін сөз мәселесі – генераторлардағы екі сөздің бірдей элементті көрсететінін анықтаудың алгоритмдік мәселесі болып табылады. Сөз мәселесі – шешілмейтін мәселенің жақсы белгілі мысалы. Мысалы, [0,1] аралығындағы екі биекция және берілген, егер және белгілі болса, олардың композициясы тек шекті санда басқа биекцияларды ғана тудыра алатынын, туралы қосымша ақпаратсыз дәлелдей аласыз ба? Бұл функциялар генераторлар деп аталады, ал олардың барлық шекті композицияларының жиынтығы – олар жасаған топ. Бұл жағдайда генераторлар теңқабырлы үшбұрыштың симметрия тобына изоморфты 6-ретті шекті топты жасайды, сондықтан екі кездейсоқ шекті композицияның теңдігін анықтауға болады. Нақтырақ айтқанда, егер – топтың шекті генераторлар жиыны болса, онда сөз мәселесі – генераторлардағы барлық сөздердің формальді тіліндегі және табиғи бейнелеу арқылы толыққаннан сәйкес келетін инверсиялардың формальді жиынындағы мүшелік мәселесі болып табылады. Егер – топтың тағы бір шекті генераторлар жиыны болса, онда генераторлар жиыны бойынша сөз мәселесі генераторлар жиыны бойынша сөз мәселесімен эквивалентті. Осылайша, шекті жасалған топ үшін сөз мәселесінің шешілуі туралы нақты айтуға болады. Рекурсивті түрде берілген топтар класы үшін байланысты, бірақ әртүрлі бірыңғай сөз мәселесі – бұл, кластағы топ үшін берілген презентация және генераторлардағы екі сөз, олардың бір элементті көрсететінін анықтаудың алгоритмдік мәселесі. Кейбір авторлар кластың рекурсивті санамалы презентациялар жиынымен анықталуын талап етеді.
In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group is the algorithmic problem of deciding whether two words in the generators represent the same element. The word problem is a well known example of an undecidable problem. For example, given two bijections and on the interval such that and is known, can you prove that the compositions of and can only generate a finite number of other
bijections on without more information about and ? The functions and are called the generators, and the set of all finite compositions of and
is the group they generate. In this case, generators generate
a finite group of order 6 isomorphic to the symmetry group of an equilateral triangle, , hence the equality of two arbitrary finite compositions can be decided. More precisely, if is a finite set of generators for then the word problem is the membership problem for the formal language of all words in and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on to the group If is another finite generating set for , then the word problem over the generating set is equivalent to the word problem over the generating set Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group
The related but different uniform word problem for a class of recursively presented groups is the algorithmic problem of deciding, given as input a presentation for a group in the class and two words in the generators of , whether the words represent the same element of Some authors require the class to be definable by a recursively enumerable set of presentations.
Тарих
Тарих бойына топтардағы есептеулер әртүрлі қалыпты түрлерді пайдалана отырып жүргізілді. Бұл әдетте аталған топтар үшін сөздік проблеманы шешеді. 1911 жылы Макс Дэн сөздік проблеманы, конъюгация проблемасын және топтық изоморфизм проблемасын зерттеудің өз алдына маңызды саласы екенін ұсынды. 1912 жылы ол 2-ге тең немесе одан үлкен гендерлі, жабық бағытталған екі өлшемді манифольдтардың негізгі топтары үшін сөздік және конъюгация проблемаларын шешетін алгоритм берді. Кейінгі авторлар Дехн алгоритмін едәуір кеңейтіп, оны топтық теориялық шешімдердің кең ауқымына қолданды. 1955 жылы Пётр Новиков сөздік проблемасы шешілмейтін шекті ұсынылған топтың бар екенін көрсетті. Осыдан бірден біртұтас сөздік проблема да шешілмейтіндігі көрінеді. 1958 жылы Уильям Бун басқа дәлел келтірді. Сөздік проблема математикалық логикада немесе алгоритмдер теориясында емес, классикалық математиканың орталық салаларының бірі – алгебрада табылган шешілмейтін проблеманың алғашқы мысалдарының бірі болды. Оның шешілмейтіндігінің нәтижесінде комбинаторлық топтар теориясындағы басқа да бірнеше проблемалардың да шешілмейтіндігі дәлелденді. Сөздік проблеманың көптеген топтар үшін шешілетінін түсіну маңызды. Мысалы, полициклдік топтар шешілетін сөздік проблемаға ие, себебі полициклдік ұсынылымдағы кез келген сөздің қалыпты түрі оңай есептеледі; басқа алгоритмдер де, қолайлы жағдайларда, сөздік проблеманы шеше алады, мысалы, Тодд-Коксетер алгоритмі және Кнут-Бендикс толықтыру алгоритмі. Екінші жағынан, белгілі бір алгоритм белгілі бір топ үшін сөздік проблеманы шешпесе, бұл топтың шешілмейтін сөздік проблемасы бар дегенді білдірмейді. Мысалы, Дехн алгоритмі тордың негізгі тобы үшін сөздік проблеманы шешпейді. Алайда бұл топ екі шексіз циклдік топтың тікелей көбейтіндісі болып табылады және сондықтан шешілетін сөздік проблемаға ие.
Нақтырақ сипаттама
Нақтырақ айтқанда, бірыңғай сөз мәселесін сөз тізбектері үшін қайта жазу сұрағы ретінде қоюға болады. Топтың берілуі үшін , біз белгілі бір сандағы генераторларды анықтаймыз. Бізге әріпті енгізу қажет, және екінші бір әріпті (ыңғайлы болу үшін) топ элементі үшін. Бұл әріптерді (генераторлардың санынан екі есе көп) мәселенің алфавиті деп атаймыз. Содан кейін, топтың әрбір элементі белгілі бір жолмен алфавиттен алынған символдардың көбейтіндісі арқылы ұсытылады, оның ұзындығы белгілі бір сан болады. Ұзындығы 0-ге тең тізбек (бос тізбек) топтың бірлік элементін білдіреді. Мәселенің өзегі – берілген қатынастарды ескере отырып, элементтің барлық мүмкін ұсынылуын тану қабілеті. Қатынастардың әсері – әртүрлі тізбектердің бірдей топ элементін ұсынуына мүмкіндік беру. Шындығында, қатынастар тізбектер тізімін ұсынады, оларды қалауынша енгізуге болады немесе оларды көрген кезде жоюға болады, бұл «мәнін» өзгертпейді, яғни көбейту нәтижесінде алынған топ элементін. Мысал ретінде, берілуімен берілген топты қарастырайық. -ның кері шамасын деп белгілейік, онда символдардың кез келген санынан құралған тізбектер мүмкін болады. Егер біз немесе немесе тізбектерін көрсек, оларды жоюға болады. Сондай-ақ, тізбегін жоюды естен шығармауымыз керек, себебі -ның кубы топтың бірлік элементі болса, оның кері шамасының кубы да бірлік элементі болады. Мұндай жағдайда сөз мәселесі оңай болады. Бірінші кезекте тізбектерді бос тізбекке дейін қысқарту керек, яғни , , немесе . Содан кейін, біз тізбектерді көбейту арқылы да өзгерте алатынымызды ескеру қажет, мысалы, тізбегін тізбегіне, ал тізбегін тізбегіне айналдыруға болады. Нәтижесінде, үш реттік циклі тобы үшін сөз мәселесі шешіледі. Дегенмен, бұл әдеттегі жағдай емес. Мысалы, бізде кез келген тізбектің ұзындығын үштен аспайтындай етіп қысқартатын канондық форма бар, ұзындығын біртіндеп кеміте отырып. Жалпы алғанда, элементтерді бірте-бірте жою арқылы канондық форма алуға болады деп айтуға болмайды. Керісінше, тізбектің ұзындығын едәуір арттыруға тура келуі мүмкін, содан кейін ғана ұзындығын қысқартатын жоюды табуға болады. Соның салдарынан, ең жаман жағдайда, тізбектердің теңдігін көрсететін қатынастар шешілмейтін мәселеге айналады.
for We need to introduce one letter for and another (for convenience) for the group element represented by Call these letters (twice as many as the generators) the alphabet for our problem. Then each element in is represented in some way by a product
of symbols from , of some length, multiplied in The string of length 0 (null string) stands for the identity element of The crux of the whole problem is to be able to recognise all the ways can be represented, given some relations. The effect of the relations in is to make various such strings represent the same element of In fact the relations provide a list of strings that can be either introduced where we want, or cancelled out whenever we see them, without changing the 'value', i. e. the group element that is the result of the multiplication. For a simple example, consider the group given by the presentation Writing for the inverse of , we have possible strings combining any number of the symbols and Whenever we see , or or we may strike these out. We should also remember to strike out ; this says that since the cube of is the identity element of , so is the cube of the inverse of Under these conditions the word problem becomes easy. First reduce strings to the empty string, , , or Then note that we may also multiply by , so we can convert to and convert to The result is that the word problem, here for the cyclic group of order three, is solvable. This is not, however, the typical case. For the example, we have a canonical form available that reduces any string to one of length at most three, by decreasing the length monotonically. In general, it is not true that one can get a canonical form for the elements, by stepwise cancellation. One may have to use relations to expand a string many fold, in order eventually to find a cancellation that brings the length right down. The upshot is, in the worst case, that the relation between strings that says they are equal in is an Undecidable problem.