Шексіз белгісіздік – қатарлы жүйедегі ресурстар үшін күресте сұраныстың шексіз кешігуі, бірақ оның орындалуы кепілдігі. Теориялық есептеулерде маңызды.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік ғылымда шексіз нондерминизм немесе шексіз белгісіздік – бір мезгілде орындалудың қасиеті, онда ортақ ресурстарға таласқанда төрешілік ету нәтижесінде сұрауды қызмет көрсетудегі кешігу мерзімі шексіз ұзарады, бірақ сұраудың әрі қарай қызмет көрсетілетініне кепілдік беріледі. Шексіз нондерминизм бір мезгілде орындалудың денотациялық семантикасын әзірлеуде маңызды мәселе болды және кейіннен гиперкомпутацияның теориялық тұжырымдамасын зерттеуге қатысты.
In computer science, unbounded nondeterminism or unbounded indeterminacy is a property of concurrency by which the amount of delay in servicing a request can become unbounded as a result of arbitration of contention for shared resources while still guaranteeing that the request will eventually be serviced. Unbounded nondeterminism became an important issue in the development of the denotational semantics of concurrency, and later became part of research into the theoretical concept of hypercomputation.
Әділдік
Шексіз нондерминистік талқылау көбінесе әділдік туралы талқылауға ұласады. Негізгі идея – барлық есептеу жолдары «әділ» болуы керек, яғни егер машина бір күйге шексіз рет кірсе, ол сол күйден барлық мүмкін өтулерді жүзеге асыруы тиіс. Бұл машинаның, мүмкіндігі болса, сұранысқа қызмет көрсетуіне кепілдік беруді талап етумен бірдей, себебі шексіз күйлер тізбегі тек қана сұранысқа қызмет ететін өту болмаса ғана рұқсат етіледі. Басқаша айтқанда, кез келген мүмкін өту шексіз есептеуде ерте не кеш орын алуы керек, бірақ бұл өтуге шексіз уақыт қажет болуы мүмкін. Бұл ұғымды «әділ» тиынды лақтырудың жергілікті әділдігінен ажырату керек, онда кез келген шекті қадамдар саны үшін нәтиже әрқашан сырт болуы мүмкін, бірақ қадамдар саны артқан сайын мұндай жағдай болу ықтималдығы төмендейді. Уильям Д. Клингер өзінің 1981 жылғы диссертациясында жолдарды біріктірудегі әділ немесе шексіз нондерминистіктің рөлін көрсеткен. Ол екі жолдың «әділ бірігісін» үшінші жол деп анықтады, онда әр жолдың әр символы ерте не кеш пайда болуы керек. Содан кейін ол екі жолдың барлық әділ бірігісінен тұратын жиынтықты қарастырды, оны монотонды функция деп есептеді. Ол содан кейін бос ағын қайда деп сұрады. Бұл элемент , демек, қайшылыққа әкеледі. Ол мынадай қорытынды жасады: әділ бірігісті ағындармен жұмыс істейтін нондерминистік деректер ағыны бағдарламасы ретінде жазу мүмкін емес.
Discussion of unbounded nondeterminism tends to get involved with discussions of fairness. The basic concept is that all computation paths must be "fair" in the sense that if the machine enters a state infinitely often, it must take every possible transition from that state. This amounts to requiring that the machine be guaranteed to service a request if it can, since an infinite sequence of states will only be allowed if there is no transition that leads to the request being serviced. Equivalently, every possible transition must occur eventually in an infinite computation, although it may take an unbounded amount of time for the transition to occur. This concept is to be distinguished from the local fairness of flipping a "fair" coin, by which it is understood that it is possible for the outcome to always be heads for any finite number of steps, although as the number of steps increases, this will almost surely not happen. An example of the role of fair or unbounded nondeterminism in the merging of strings was given by William D. Clinger, in his 1981 thesis. He defined a "fair merge" of two strings to be a third string in which each character of each string must occur eventually. He then considered the set of all fair merges of two strings , assuming it to be a monotone function. Then he argued that , where is the empty stream. Now }, so it must be that is an element of , a contradiction. He concluded that:
It appears that a fair merge cannot be written as a nondeterministic data flow program operating on streams.
Шексіз нондертимеризмді жүзеге асыру мүмкіндігі туралы
Эдсгер Дикстра шексіз белгісіздікпен жүйелерді іске асыру мүмкін емес екенін айтты. Осы себепті Тони Хоар "тиімді іске асыру оңды болуға ұмтылуы керек" деп ұсынды.
Edsger Dijkstra argued that it is impossible to implement systems with unbounded nondeterminism. For this reason, Tony Hoare suggested that "an efficient implementation should try to be reasonably fair."
Детерминистік емес автоматтар
Детерминистік емес Тьюринг машиналары тек шекті детерминизмді ғана қамтиды. Сол сияқты, нондетерминизмнің жалғыз көзі ретінде сақталған командаларды қамтитын ретті бағдарламалар да тек шектелген нондетерминизмге ие. Қысқаша айтқанда, таңдау нондерминизмі шектеледі. Гордон Плоткин өзінің powerdomains туралы алғашқы еңбегінде мынадай дәлел келтірді:
Nondeterministic Turing machines have only bounded nondeterminism. Likewise sequential programs containing guarded commands as the only sources of nondeterminism have only bounded nondeterminism. Briefly, choice nondeterminism is bounded. Gordon Plotkin gave a proof in his original paper on powerdomains:
Енді берілген нондетерминистік бағдарламаның орындалу тізбегінің бастапқы сегменттерінің жиынтығы, белгілі бір күйден басталып, ағаш құрайды. Ағаштың тармақталу нүктелері бағдарламадағы таңдау нүктелеріне сәйкес келеді. Әрбір таңдау нүктесінде әрқашан шекті ғана баламалар болғандықтан, ағаштың тармақталу факторы әрқашан шекті болады. Яғни, ағаш шекті. Кениг леммасы бойынша, егер шекті ағаштың кез келген тармағы шекті болса, онда ағаштың өзі де шекті болады. Осы жағдайда, егер бағдарламаның кез келген орындалу тізбегі аяқталса, онда тек шекті санда ғана орындалу тізбектері болады. Сондықтан, егер бағдарламаның шығыс жиынтығы шексіз болса, онда оның құрамында [аяқталмайтын есептеулер] болуы керек.
Now the set of initial segments of execution sequences of a given nondeterministic program , starting from a given state, will form a tree. The branching points will correspond to the choice points in the program. Since there are always only finitely many alternatives at each choice point, the branching factor of the tree is always finite. That is, the tree is finitary. Now Kőnig's lemma says that if every branch of a finitary tree is finite, then so is the tree itself. In the present case this means that if every execution sequence of terminates, then there are only finitely many execution sequences. So if an output set of is infinite, it must contain [a nonterminating computation].
Шексіз нондертимеризм және есептеу мүмкін еместігі
Спаан және тағы басқалар шексіз детерминистік емес бағдарлама тоқтату мәселесін шеше алатынын айтты; олардың алгоритмі екі бөліктен тұрады, олар былай анықталған:
Spaan et al. have argued that it is possible for an unboundedly nondeterministic program to solve the halting problem; their algorithm consists of two parts defined as follows:
Бағдарламаның бірінші бөлігі екінші бөліктен натурал сан сұрайды; оны алғаннан кейін, ол берілген Тьюринг машинасы үшін осы санға дейін қадамдарды орындайды және машина тоқтаса қабылдайды немесе тоқтамаса қабылдамайды. Бағдарламаның екінші бөлігі сұраныс бойынша кездейсоқ натурал санды таңдайды. Сан 0-ге бастама берілген айнымалыда сақталады; содан кейін бағдарлама қайта-қайта айнымалыны арттыруды немесе сұранысты өңдеуді таңдайды. Әділдік талабы бойынша сұранысқа ақырында жауап берілуі керек, әйтпесе айнымалыны арттыру тармағы ғана таңдалатын шексіз цикл пайда болады. Егер машина тоқтаса, алгоритмнің қабылдайтын жолы болады. Егер машина тоқтамаса, бағдарламаның екінші бөлігі қандай сан берсе де, бұл алгоритм әрқашан қабылдамайды.
The first part of the program requests a natural number from the second part; after receiving it, it will iterate the desired Turing machine for that many steps, and accept or reject according to whether the machine has yet halted. The second part of the program nondeterministically chooses a natural number on request. The number is stored in a variable which is initialized to 0; then the program repeatedly chooses whether to increment the variable, or service the request. The fairness constraint requires that the request eventually be serviced, for otherwise there is an infinite loop in which only the "increment the variable" branch is ever taken. Clearly, if the machine does halt, this algorithm has a path which accepts. If the machine does not halt, this algorithm will always reject, no matter what number the second part of the program returns.
Шексіз нондетерминизммен күресу үшін дәлелдер
Клингер мен Карл Хьюит [Клингер 1981; ; ; ] шексіз нондетерминизм қасиетімен бірге есептеудің моделін (актор моделі деп аталады) жасады; бұл жоғарыда көрсетілгендей, Тьюринг машиналарымен іске асырылмайтын есептеулерді жүзеге асыруға мүмкіндік береді. Дегенмен, бұл зерттеушілер бір мезгілде есептеу моделін Черч, Клини, Тьюринг және т.б. анықтады (бір мезгілде есептеудегі белгісіздік туралы қараңыз). Хьюит өзінің шексіз нондетерминизмін арбитр деп аталатын есептеу тізбегінің қанша уақытқа дейін тоқтауына шектеу қою мүмкін емес деп түсіндірді (электроникадағы метастабильділік туралы қараңыз). Арбитрлер компьютерлерде компьютерлік сағаттардың сыртқы кіріспен, мысалы, пернетақтадан, дискіге қатынаудан, желіден және т.б. синхронды жұмыс істемейтін жағдайларды шешу үшін қолданылады. Сондықтан, компьютерге жіберілген хабарды алу үшін шексіз уақыт қажет болуы мүмкін, ал осы уақыт ішінде компьютер шексіз көп күйлерден өтуі мүмкін. Ол сондай-ақ электрондық поштаның шексіз нондетерминизмге мүмкіндік беретінін, себебі пошта жеткізілгенге дейін серверлерде шексіз уақыт сақталуы мүмкін, ал Интернеттегі серверлерге деректерді жеткізу арналары да шексіз уақытқа тоқтап қалуы мүмкін екенін айтты. Бұл шексіз нондетерминизм туралы пікір қақтығысына әкеп соқты.
Clinger and Carl Hewitt have developed a model (known as the Actor model) of concurrent computation with the property of unbounded nondeterminism built in [Clinger 1981; ; ; ]; this allows computations that cannot be implemented by Turing Machines, as seen above. However, these researchers emphasize that their model of concurrent computations defined by Church, Kleene, Turing, etc. (See Indeterminacy in concurrent computation.) Hewitt justified his use of unbounded nondeterminism by arguing that there is no bound that can be placed on how long it takes a computational circuit called an arbiter to settle (see metastability in electronics). Arbiters are used in computers to deal with the circumstance that computer clocks operate asynchronously with input from outside, e. g , keyboard input, disk access, network input, etc. So it could take an unbounded time for a message sent to a computer to be received and in the meantime the computer could traverse an unbounded number of states. He further argued that Electronic mail enables unbounded nondeterminism since mail can be stored on servers indefinitely before being delivered, and that data links to servers on the Internet can likewise be out of service indefinitely. This gave rise to the unbounded nondeterminism controversy.
Хьюиттің әділдік туралы талдауы
Хьюит әділдік мәселелерінің жаһандық күй тұрғысынан туындайтынын айтты. Есептеудің ең ерте модельдері (мысалы, Тьюринг машиналары, Пост өндірістері, лямбда-есептеу және т.б.) есептеу қадамын көрсету үшін жаһандық күйді пайдаланатын математикаға негізделген. Әрбір есептеу қадамы – есептеудің бір жаһандық күйінен келесі жаһандық күйге өту. Жаһандық күйге қатысты тәсіл автоматтар теориясында шекті күй машиналары және олардың нондетерминистік нұсқаларын, сондай-ақ стек машиналарын төмен қарай итеру үшін де қолданылды. Бұл модельдердің барлығы шектелген нондетерминизм қасиетіне ие: егер машина бастапқы күйде іске қосылғанда әрқашан тоқтаса, онда тоқтатылатын күйлер саны шектеулі болады. Хьюиттің пікірінше, оның Актер моделінің жаһандық күй нондетерминизміндегі таңдау мен келу ретінің (нондетерминизм) арасындағы маңызды айырмашылық бар. Жаһандық күй нондетерминизмінде "келесі" жаһандық күй үшін "таңдау" жасалады. Келу ретінің белгісіздігінде, төрелік жергілікті түрде әрбір келу ретін шексіз уақыт ішінде шешеді. Жергілікті төрелік жүріп жатқанда, басқа жерде шексіз әрекеттер орын алуы мүмкін. Жаһандық күй болмайды, сондықтан "келесі" жаһандық күй туралы "таңдау" жасалмайды.
Hewitt argued that issues in fairness derive in part from the global state point of view. The oldest models of computation (e. g Turing machines, Post productions, the lambda calculus, etc.) are based on mathematics that makes use of a global state to represent a computational step. Each computational step is from one global state of the computation to the next global state. The global state approach was continued in automata theory for finite state machines and push down stack machines including their nondeterministic versions. All of these models have the property of bounded nondeterminism: if a machine always halts when started in its initial state, then there is a bound on the number of states in which it can halt. Hewitt argued that there is a fundamental difference between choices in global state nondeterminism and the arrival order indeterminacy (nondeterminism) of his Actor model. In global state nondeterminism, a "choice" is made for the "next" global state. In arrival order indeterminacy, arbitration locally decides each arrival order in an unbounded amount of time. While a local arbitration is proceeding, unbounded activity can take place elsewhere. There is no global state and consequently no "choice" to be made as to the "next" global state.