Zdefiniowanie problemu zatrzymania dla niedeterministycznych automatów

18

Podstawowa definicja maszyny Turinga (TM), przynajmniej w moim własnym podręczniku (Hopcroft + Ullman 1979), jest deterministyczna.

Stąd moje własne rozumienie problemu zatrzymania dotyczy przede wszystkim deterministycznej TM, chociaż jestem świadomy, że można go rozważyć w przypadku innych rodzajów automatów.

Zauważyłem również, że determinizm jest często mniej lub bardziej dorozumiany w sposobie, w jaki ludzie często odnoszą się do TM lub problemu zatrzymania. Dobrym tego przykładem jest strona wikipedia dotycząca problemu zatrzymania .

Ale wydaje się, że nie ma powodu do takiego ograniczenia. Biorąc pod uwagę rodzinę automatów które mogą być niedeterministyczne, problem zatrzymania dla można zdefiniować jako: $\mathcal F$ $\mathcal F$

Czy istnieje jednolita procedura decyzyjna taka, że biorąc pod uwagę automat i wejście , może zdecydować, czy na wejściu zostanie obliczone zatrzymanie $A\in\mathcal F$ $x$ $A$ $x$ .

(To nie jest całkiem to samo, co powiedzenie, że obliczenie z wejściem $A$ $x$ zakończy się.)

Rzeczywiście wydaje się, że jest to jedyny sposób, aby nadać sens rozmowom na temat problemu zatrzymania automatów liniowo ograniczonych (LBA), które są przede wszystkim automatami niedeterministycznymi.

Więc moje pytanie brzmi: czy mam rację i czy istnieje powód (i powód) tego pozornie drugiego traktowania problemu zatrzymania dla niedeterministycznych automatów.

— Babou
źródło

Jeśli uważasz, że coś jest nie tak w tym pytaniu, czy byłbyś tak uprzejmy, aby powiedzieć, co to jest, abyśmy wszyscy mogli skorzystać z Twojej wiedzy i poprawić post dla wszystkich użytkowników. Dziękuję Ci.

— babou

12

There are a few reasons I think we put less effort into the Halting problem for non-deterministic models.

The first is that there are, in fact, two relevant halting problems for a ND model. Given an input $x$ and a non-deterministic machine $M$ :

Does there exist a valid run of $M$ on $x$ which halts?
Does there exist a valid run of $M$ on $x$ which doesn't halt? i.e. do all valid runs halt?

For deterministic machines, these are identical, since there is exactly one valid run of $M$ on an input $x$ . But for non-deterministic machines, there might be multiple runs. Which one you're interested in depends on your application.

Secondly, non-deterministic models are already unrealistic: they assume that you either have a magical box telling you which path to take, or that you have some form of infinite parallelism. Since non-deterministic and deterministic Turing Machines are equivalent in power, in most cases you just convert the machine into a determinstic one before you worry about halting.

Jako rozszerzenie tego nie obchodzi nas to, ponieważ udowodnienie czegoś o maszynie niedeterministycznej jest co najmniej tak trudne, jak udowodnienie czegoś o równoważnej maszynie deterministycznej. Wiemy już, że nie ma rozwiązania deterministycznego problemu zatrzymania, więc naprawdę przydatne jest udowodnienie innych problemów nierozstrzygalnych poprzez redukcje. I zawsze będzie mniej pracy, aby zredukować się do deterministycznego problemu zatrzymania, ponieważ jest to łatwiejsze niż niedeterministyczny odpowiednik.

— jmite
źródło

You state: "But for non-deterministic machines, there might be multiple runs. Which one you're interested in depends on your application." Could you illustrate that statement with an example? Then you state "you just convert the machine into a deterministic one before you worry about halting". How is that done for a LBA?

— babou

LBA's are a subset of non-deterministic Turing Machines, so they can always be converted into deterministic Turing Machines using the usual method. I suspect there's special construction that can be used to convert to a machine with specific properties, so we can keep the extra reasoning ability we get from LBAs. I think it's going to look like a backtracking algorithm where linear space is used, except the call stack could potentially be exponentially large (I'm not sure, I'd have to look it up).

— jmite

M_{1}, M_{2}

$M_1, M_2$

x

$x$

x

$x$

M

$M$

M_{1}

$M_1$

M_{2}

$M_2$

x

$x$

x

$x$

x

$x$

x

$x$ .

— jmite

1

@HendrikJan It seems that halting of NLBA is rather addressed with Savitch's theorem. But it changes the linear bound into a quadratic one.

— babou

1

@Raphael what I mean by this is that, to show problem

P

$P$ undecidable, you show that you can use

P

$P$ to simulate another undecidable problem. Since there's a trivial injective mapping from DTMs to NTMs, any reduction from NTM halting is also a reduction from DTM halting. Usually it would be less work to reduce from DTM halting, since it's a less difficult problem you're trying to simulate.

— jmite

4

The halting problem is the quintessential $\Sigma_1$ -complete problem, since it can be stated as:

$H(P,x) \leftrightarrow \exists c \, \text{ s. t. $c$ is a halting computing of $P$ on $x$}$ .

This suggests that your definition is a correct one. In general, every $\Sigma_1$ -complete definition is "correct".

— Yuval Filmus
źródło

Unfortunately, I know close to nothing about arithmetical hierarchy. Am I correct in understanding that

Σ_{1}

$\Sigma_1$ represents semi-decidable problems? What about:

K (P, x) \leftrightarrow \forall c, c is a computing of P on x ⟹ c is halting.

$K(P,x)\leftrightarrow\forall c, c\text{ is a computing of $P$ on $x\implies c$ is halting.}$ . I am asking because existential and universal quantifications seem to end up in different classes, but it is all hazy for me.

K

$K$ is also semi-decidable.

— babou

That is what I was afraid you would answer. I asked because I think that I have a semi-decision procedure for it. So either my proof is wrong, or I formalized my problem incorrectly. Basically it is jmite's suggestion that non-deterministic halting on input

x

$x$ could be defined by requiring that all computations on

x

$x$ halt. And I believed until now I had a semi-decision for that.

— babou

Actually your definition isn't good for another reason: what do you mean by "

c

$c$ is halting"? Either you mean that

c

$c$ , which is a-priori only an incomplete computation, is actually complete. In that case,

K (P, x)

$K(P,x)$ is never true, since you can take

c

$c$ to be the empty computation. In any other case, it's not clear that the description of

c

$c$ is finite, and it's also not clear that the predicate "

c

$c$ is halting" is computable.

— Yuval Filmus

So in fact the problem is in

Π_{1}

$\Pi_1$ but probably not

Π_{1}

$\Pi_1$ -complete.

— Yuval Filmus

Thanks, and sorry for my naive reading. I thought the

c

$c$ you used stood for "complete" computations, which is apparently an error on the domain quantified. I guess one can use only countable domains and the set of non-halting computations of a nondeterministic TM does not qualify. Also I guess the quantifiers tell us how bad the computability may be, but offer no garantee that it is that bad. So it seems that jmite's proposal is not easily expressed in a direct way in the required "format", but my semi-decision procedure may be correct.

— babou

2

you say there is an "apparent second class treatment" of the halting problem for nondeterministic machines. it does appear that nondeterminism was not considered historically until long after Turings creation of the deterministic TM & this may have something to do with research focus in the area. however the main point here is that the nondeterministic problem can easily be reduced to the deterministic problem, so one only needs to study the deterministic problem "without loss of generality".

furthermore, to counter the idea of "2nd class" here is at least one ref/ paper that studies the halting problem for nondeterministic machines and finds useful/ deep connections. some circumstantial evidence along the lines that CS research is so vast/ specialized, sometimes some starting research has been done in most areas, even seemingly narrow, and it can approach nearly meaningless or hairsplitting to rank different problems in their importance. and quite to the contrary, nondeterminism seems a very deep/ ubiquitous/ crosscutting concept in CS (key open questions like P vs NP are on it) & that aspect is likely to continue long into the future.

A Parameterized Halting Problem / Chen, Flum

Abstract. The parameterized problem p-Halt takes as input a nondeterministic Turing machine M and a natural number n, the size of M being the parameter. It asks whether every accepting run of M on empty input tape takes more than n steps. This problem is in the class XPuni, the class “uniform XP,” if there is an algorithm deciding it, which for fixed machine M runs in time polynomial in n. It turns out that various open problems of different areas of theoretical computer science are related or even equivalent to p-Halt ∈ XPuni. Thus this statement forms a bridge which allows to derive equivalences between statements of different areas (proof theory, complexity theory, descriptive complexity, . . . ) which at first glance seem to be unrelated. As our presentation shows, various of these equivalences may be obtained by the same method.

— vzn
źródło

2

In a nutshell

There seems to be no good reason to neglect the halting problem in settings that are not the classical one of deterministic Turing machines, other than the fact that the classical halting problem answers some major mathematical questions (such as the Entscheidungsproblem), while variants are only interesting (?) technical issues, but with less impact on the foundations.

After reviewing some of the arguments given in previous answers, I analyze and compare the two proposals by jmite for a possible definition of "nondeterministic" halting in the case of nondeterministic automata. The issue is not to define what halting means for a single computation, but what it should mean for the set of possible computations of a given nondeterministic automaton $A$ on a given input $x$ . This can then serve as a basis for defining the halting problem on nondeterministic automata.

According to jmite's answer, this nondeterministic halting can be defined as corresponding to the existence of at least one halting computation (existential halting), or alternatively to requiring that all possible computation be halting (universal halting). These two definitions correspond to two different definitions of the nondeterministic halting problem.

I show that, for Turing machines, the two definitions corresponds to two distinct ways of determinizing the machine by dovetailing. From this, I infer that the two variants of the nondeterministic halting problem are both Turing equivalent to the classical deterministic halting problem.

However, I also show that each of these definitions of halting is directly related to a corresponding definition of the language recognized by a Turing machine, and this relation can be simply expressed on the condition of choosing consistent definitions.

Hence, given the usual definition of the language recognized by a nondeterministic automaton, the natural definition of nondeterministic halting is existential halting, as proposed in the original question.

Most of this analysis naturally extends to other types of automata, though the dovetailing constructions are often not available within less powerful families than Turing machines.

Introduction

I am writing this as an answer since it partially answers my question after more thoughts about it, taking existing answers into account. Also, editing my question after three answers might in this case confuse issues, and I would rather leave the question as originally written to avoid that.

I first discuss some of my disagreements with the given answers. The point is not to disparage fair attempts at answering my question (my thanks for all answers), but to get to the bottom of issues by discussing or disputing technical points.

I think the original question hardly needs context or motivation. The halting problem is one of the major questions we ask about automata on the one hand, and nondeterminism is one very common and useful features of many automata on the other hand. Furthermore, nondeterminism is not just a common theoretical device to simplify proofs, but an essential feature of some families of automata, such as the linear bounded automaton (LBA), at least at the time of this writing.

Hence it is quite natural to wonder whether the halting problem has meaning, or a preferred meaning, which and why, in the case of nondeterministic automata.

Is the nonderterministic halting problem well addressed?

My question wonders why the halting problem for nondeterministic automata seems to receive second class treatment, which did generate a downvote and an answer by vzn. The answer by vzn, which is really more a long comment, insists that "nondeterminism seems a very deep/ ubiquitous/ crosscutting concept in CS", which I never doubted. It also gives one reference to some reasearch on halting for nondeterministic machines which is not surprising, but does not really address my point. My point is that I do not recall actually seeing a definition of the halting problem aimed at nondeterministic machines, though I did read some litterature in the field. It is not addressed, AFAIK, in my reference textbook (Hopcroft+Ullman 1979). It seem often implicit in the mind of people that they are considering deterministic automata, usually Turing machines, whose reference definition is deterministic.

For example, in the question Why is the halting problem decidable for LBA?, Yuval Filmus forgot in his answer that LBAs are nondeterministic devices - but brilliantly saved his answer with a 4 words comment.

As a last witness to the fact that this issue is not well addressed in general (despite some specialized research), I would call the fact that the issue has to be discussed here.

The answer from jmite is the only one that actually attempts to explain why it might not be well addressed. His first argument is that there are two possible definitions, but I believe that this situation should rather encourage more analysis to determine which definition would be most appropriate. I attempt to do that below.

He also suggests that, since a nondeterministic TM can always be converted into an equivalent deterministic one, there is not much point in worrying about the issue of halting in the nondeterministic case. I am not fully convinced, but it may be perceived as a good reason by many. However, the argument does not apply to Linear Bounded Automata (LBA), because it is still an open problem whether deterministic LBA are equivalent to nondeterministic LBA. And there are other families of automata for which the deterministic subfamily is weaker that the whole nondeterministic family (PDA for example).

I also disagree with the last point, asserting that we should not be concerned with nondeterministic halting because proofs are easier with deterministic machines. Raphael objected to that in a comment: "I usually find reductions to harder problems easier". Indeed, for many types of automata, the nondeterministic version serves mainly to simplify proofs, such as reduction to that type of automaton. Having in addition two forms of halting that may be used, as suggested by jmite himself, could even be considered an advantage as it give more flexibility to address problems.

On the definition of the nondeterministic halting problem

_{Note: the use of the word "universal" in the following text refers
to universal quantification, NOT to universal Turing machines}

The answer from jmite is the most detailed.

This answer conjectures that nondeterministic automata foster less effort on the halting problem because it can be defined in two different ways (the terminology is mine):

existential halting: is there a halting computation of automaton $M$ on input $x$ ?
universal halting: are there only halting computations of automaton $M$ on input $x$ ?

The only definition I had suggested adequate is existential halting.

Proposition 1: When a nondeterministic automaton is universally halting on input $x$ , it can only have a finite number of halting computations on that input.

Proof: This is easily proved with König's lemma, since the number of possible nondeterministic choices at each step is bounded for a given automaton. If there were infinitely many halting computations, we could label each configuration with each of the computational paths leading to it, which would make a computation graph with infinitely many nodes, but only finite nondeterministic branching at each node. By König's lemma, this implies the existence of an infinite computational path, corresponding to a non-halting computation.

The case of (nondeterministic) Turing machines

So now, let's examine halting in the case of nondeterministic Turing machine (NTM).

To analyze the two definitions, the simplest is indeed to consider deterministic versions of non deterministic machines, which can be achieved, as recalled by Hendrik Jan, by dovetailing of all possible computations.

But there are (at least) two ways of dovetailing computations for determinization, though only one is usually considered:

existential dovetailing determinization which simulates all computations in parallel and terminates when one of the simulated computations terminates.
universal dovetailing determinization which simulates all computations in parallel and terminates only when all of the simulated computations terminate. But it can conceivably enumerates in some way the terminating computations, or count them.

Proposition 2:

A nondeterministic TM $M$ is existentially halting on input $x$ iff its existential dovetailing determinization $M_\exists$ is a TM that halts on input $x$ .
A nondeterministic TM $M$ is universally halting on input $x$ iff its universal dovetailing determinization $M_\forall$ is a TM that halts on input $x$ .

Proof: The proof for the existential case is obvious. For the universal case, the universal dovetailing determinization will halt iff it simulates a finite number of computations, all of which are halting. Given a nondeterministic TM $M$ , if it halts universally on input $x$ , then, by proposition 1, it has only a finite number of distinct computations, which all halt. Hence its universal dovetailing determinization $M_\forall$ halts on input $x$ . The converse is straightforward.

Theorem 3: The halting problem for deterministic TM, and the existential and universal halting problems for nondeterministic TM are Turing equivalent.

Proof: This results from proposition 2 and from the fact that deterministic TMs are a subset of nondeterministic TM, where both existential and universal halting reduce to simple deterministic halting.

Hence, from a computability point of view, and I am tempted to say from a symbol pushing point of view, it seems that it does not really matter which definition is chosen, existential or universal, for the nondeterministic halting problem.

Why choose one definition of NTM halting, and which

However, is there much sense to a determinization process that does not preserve the language recognized by the original automaton?

The essence of the use of nondeterminism in language recognition is that it assumes an oracle that is supposed to guess a right computational path whenever there is one that will lead to acceptance, a fundamentally existential view.

In a nondeterministic computation, there is no difference between rejection on halting and non-halting. In both cases, no conclusion can be drawn. The language recognized is not changed if you replace rejection on halting by a non-halting infinite loop, which can be done for all nondeterministic automata I can think of, including NFA (just add a looping $\epsilon$ -transition on the failure states). This is also true of deterministic automata, provided there is a special symbol marking the end of the input, as usually done for LBA.

Thus acceptance by halting may be seen as a canonical form of acceptance for nondeterministic automata.

Considering this canonical view, the halting problem may also be expressed equivalently as the recognition problem:

Is there a uniform procedure that, given a language $L$ recognized by a Turing machine $M$ , can decide for any word $x$ whether $x\in L$ ?

This evidences the close ties between recursive enumerabiliy and the halting problem. This equivalence between deciding halting of the TM $M$ on input $x$ and containement of $x$ in the language $M$ recognizes is true for both deterministic TM and for nondeterministic ones, provided we consider the existential definition of nondeterministic halting.

However, in the case universal halting, this close relation is lost. A similar statement can be made, but for a different language than the one recognized by the NTM (or alternatively for a different, universal, definition of what is the language recognized by a NTM).

When developing a theory, it is essential to use consistent definitions so as to emphasize structures and relations in their simplest and most perspicuous form. It is quite clear that in the present case, consistency with other definitions suggests that existential halting is the natural definition of halting for nondeterministic Turing machines.

Of course, one may always be interested in analyzing universal halting. Similarly, one could also develop a theory of universal acceptance for NTM based on the requirement that a string $x$ is accepted iff all computation on input $x$ halt and accept. But, apparently, it is not considered a major issue in the theory of Turing machines.

The case of other families of automata

Parts of the above analysis cannot be extended to most families of nondeterministic automata. For example a pushdown atomaton (PDA) may define languages that cannot be recognized by a deterministic PDA. The same may be true of LBAs. Other parts can be extended to all nondeterministic families.

Regarding the definition of nondeterministic halting, even though the reasoning used in the Turing machine case may not be usable, it seems that the only sensible choice is to adopt a definition which is consistent with the one used for nondeterministic Turing machines, hence the existential definition.

The definition of the Halting problem for these families of nondeterministic automata follows, and conforms the definition proposed in the question.

— babou
źródło