In computability theory, a machine that always halts—also called a decider (Sipser, 1996) or a total Turing machine (Kozen, 1997)—is a Turing machine that halts for every input. Because it always halts, the machine is able to decide whether a given string is a member of a formal language. The class of languages which can be decided by such machines is exactly the set of recursive languages.

PropertyValue
dbpedia-owl:abstract
  • In computability theory, a machine that always halts—also called a decider (Sipser, 1996) or a total Turing machine (Kozen, 1997)—is a Turing machine that halts for every input. Because it always halts, the machine is able to decide whether a given string is a member of a formal language. The class of languages which can be decided by such machines is exactly the set of recursive languages. However, due to the Halting Problem, determining whether an arbitrary Turing machine halts on an arbitrary input is itself an undecidable decision problem.
  • Nella teoria della computabilità, una macchina che termina sempre — chiamata anche un decider o macchina di Turing totale — è un particolare di tipo di macchina di Turing che, al contrario del modello generale, è garantito che termini per ogni input. Poiché si ferma sempre, la macchina è in grado di decidere se una data stringa è membro di un linguaggio formale. La classe dei linguaggi che possono essere decisi da tale macchina è esattamente l'insieme dei linguaggi ricorsivi. È importante notare che, dato il problema della fermata, determinare se un'arbitraria macchina di Turing termini sempre è indecidibile - non c'è nessun algoritmo per determinarlo. L'insieme delle macchine che terminano sempre è solo ricorsivamente enumerabile.
  • Na Teoria da Computação, uma Máquina de Turing que sempre pára é uma Máquina de Turing que para para qualquer entrada. Como ela sempre para, a máquina é sempre capaz de decidir se uma determinada cadeia pertence a uma determinada linguagem formal. A classe de linguagens que podem ser decidida por estas máquinas é exatamente o conjunto das linguagens recursivas. No entanto, devido ao problema da parada, determinar quando uma Máquina de Turing para para uma entrada arbitrária é um problema indecidível.
  • Машины, которые всегда останавливаются. В теории вычислений решатель (Sipser, 1996) — любая абстрактная машина или модель вычислений, которая гарантированно остановится на любом входе.
  • 在可计算性理论中，总是停机的机器也叫做判定器（Template:Lang，1996年）或全图灵机（Template:Lang，1997年）是对所有输入总是停机的图灵机。 因为它总是停机，这个机器有能力判定给定字符串是否是一个形式语言的成员。可由这种机器判定的语言类精确的是递归语言的集合。但是由于停机问题，判定任意图灵机是否在任意输入上停机的问题自身是不可判定的判定问题。
dcterms:subject
rdfs:comment
  • Машины, которые всегда останавливаются. В теории вычислений решатель (Sipser, 1996) — любая абстрактная машина или модель вычислений, которая гарантированно остановится на любом входе.
  • 在可计算性理论中，总是停机的机器也叫做判定器（Template:Lang，1996年）或全图灵机（Template:Lang，1997年）是对所有输入总是停机的图灵机。 因为它总是停机，这个机器有能力判定给定字符串是否是一个形式语言的成员。可由这种机器判定的语言类精确的是递归语言的集合。但是由于停机问题，判定任意图灵机是否在任意输入上停机的问题自身是不可判定的判定问题。
  • In computability theory, a machine that always halts—also called a decider (Sipser, 1996) or a total Turing machine (Kozen, 1997)—is a Turing machine that halts for every input. Because it always halts, the machine is able to decide whether a given string is a member of a formal language. The class of languages which can be decided by such machines is exactly the set of recursive languages.
  • Nella teoria della computabilità, una macchina che termina sempre — chiamata anche un decider o macchina di Turing totale — è un particolare di tipo di macchina di Turing che, al contrario del modello generale, è garantito che termini per ogni input. Poiché si ferma sempre, la macchina è in grado di decidere se una data stringa è membro di un linguaggio formale. La classe dei linguaggi che possono essere decisi da tale macchina è esattamente l'insieme dei linguaggi ricorsivi.
  • Na Teoria da Computação, uma Máquina de Turing que sempre pára é uma Máquina de Turing que para para qualquer entrada. Como ela sempre para, a máquina é sempre capaz de decidir se uma determinada cadeia pertence a uma determinada linguagem formal. A classe de linguagens que podem ser decidida por estas máquinas é exatamente o conjunto das linguagens recursivas.
rdfs:label
  • Machine that always halts
  • Macchina che termina sempre
  • Máquina de Turing que sempre para
  • Машины, которые всегда останавливаются
  • 判定器
owl:sameAs
foaf:page
is dbpedia-owl:wikiPageRedirects of
is owl:sameAs of
is foaf:primaryTopic of