Примери коришћења Халтинг на Српском и њихови преводи на Енглески
{-}
-
Colloquial
-
Ecclesiastic
-
Computer
-
Latin
-
Cyrillic
Ово значи да нам ово даје алгоритам да одлучимо халтинг проблем.
У теорији усклађености, халтинг проблем је проблем одлучивања који може почети овако.
In computability theory, the halting problem is a decision problem which can be stated as follows.Али, многи од ових индексних скупова су још компликованији него халтинг проблем.
But, many of these index sets are even more complicated than the halting problem.То је због чињенице да је халтинг проблем нерешив, који има велике импликације за теоријске границе рачунарства.
This is due to the fact that the halting problem is unsolvable, which has major implications for the theoretical limits of computing.Ова чињеница је у блиској вези са алгоритамском нерешивошћу халтинг проблема.
This fact is closely related to the algorithmic unsolvability of the Halting problem.Стога је овај проблем строго тежи од халтинг проблема, који поставља питање да ли ће машина са индексом e стати за улаз 0.
Thus this problem is strictly more difficult than the Halting problem, which asks whether the machine with index e Постоје и проблеми одлучивања који су НП-тешки, али нису НП-комплетни,на пример халтинг проблем.
There are decision problems that are NP-hard but not NP-complete,for example the halting problem.Алан Тјуринг је 1936. године доказао да општи алгоритам за решавање халтинг проблема за све могуће парове програм-улаз не може да постоји.
Alan turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.Уствари, слабија форма од Прве Теореме Непотпуности која је лака последица неодлучивости халтинг проблема.
In fact, a weaker form of the First Incompleteness Theorem is an easy consequence of the undecidability of the halting problem.Халтинг проблем, који је скуп( описа) Тјурингових машина које се заустављају на улазу 0, је и добро познат пример неизрачунљивог скупа.
The halting problem, which is the set of(descriptions of) Turing machines that Харингтон је дао још један пример једне аутоморфне имовине: да креативни скупови,скупови који су многи-један еквивалентни халтинг проблему.
Harrington gave a further example of an automorphic property: that of the creative sets,the sets which are many-one equivalent to the halting problem.Проналажење горње границе на прометној функцији даброва је еквивалентна решавању халтинг проблема, проблем познат бити нерешив Тјуринговим машинама.
Finding an upper bound on the busy beaver function is equivalent to solving the halting problem, a problem known to be unsolvable by Turing machines.Иако Халтинг проблем није израчунљив, могуће је да симулира извршавање програма и произведе бесконачну листу програма које се заустављају.
Although the halting problem is not computable, it is possible to simulate program execution and produce an infinite list of the programs that do Ова чињеница даје хијерархију машина, која се назива аритметичка хијерархија,са све моћнијим халтинг пророчиштем и све тежим халтинг проблемом.
This fact creates a hierarchy of machines, called the arithmetical hierarchy,each with a more powerful halting oracle and an even harder halting problem.Интуитивно, ова разлика у неизрачунљивости је последица чињенице да свака инстанца проблема тоталне машине представља бесконачно много инстанци халтинг проблема.
Intuitively, this difference in unsolvability is because each instance of the"total machine" problem represents infinitely many instances of the Halting problem.Природни примери скупова који нису израчунљиви, укључујући имного различитих скупова који кодирају варијанте халтинг проблема, имају два својства у заједничком.
The natural examples of sets that are not computable,including many different sets that encode variants of the halting problem, have two properties in common.Такође је лако видети да халтинг проблем није НП, јер су сви проблеми из класе НП одлучиви у коначном броју операција, док халтинг проблем у општем случају није.
It is also easy to see that the halting problem is not in NP since all problems in NP are decidable in a finite number of operations, while the halting problem, in general, is undecidable.Рачунар са приступом бескрајној траци података може бити моћнији од Тјурингове машине: на пример,трака можда садржи решење халтинг проблема или неког другог Тјуринговог-неодлучивог проблема.
A computer with access to an infinite tape of data may be more powerful than a Turing machine: for instance,the tape might contain the solution to the halting problem, or some other Turing-undecidable problem.Пост( 1944) је питао да ли је сваки рекурзивно пребројив скуп такође и израчунљив илиТјуринг еквивалентан халтинг проблему, то јест, да ли постоји рекурзивно пребројив скуп са Тјуринговим степеном у средини између њих двоје.
Post(1944) asked whether every recursively enumerable set is either computable orTuring equivalent to the halting problem, that is, whether there is no recursively enumerable set with a Turing degree intermediate between those two.То јест, иако ове машине могу да одреде да ли појединачна Тјурингова машина стаје за појединачан улаз, не могу даодреде да ли машине са еквивалентним халтинг пророчиштима и саме стају.
That is, although they can determine whether particular Turing machines will Пример distNP-комплетног проблема је ограничени Халтинг проблем, BH, дефинисан као: BH={( M, x, 1t):M је недетерминистичка Тјурингова машина која прихвата x у ≤ t корака.} У његовом оригиналном раду, Левин приказује пример дистрибутивног поплочавања који је NP-комплетан.
An example of a distNP-complete problem is the Bounded Halting Problem, BH, defined as follows: BH={(M, x, 1t): M is a non-deterministic Turing machine that accepts x in≤ t steps.} In his original paper, Levin showed an example of a distributional tiling problem that is average-case NP-complete.
