# Non-deterministic Turing machine that halts on at least one branches of computation

I'm looking at my textbook here from Michael Sipser and he says that a nondeterministic Turing machine is a decider if all its computation branches halt on all inputs. I think I recall seeing somewhere what you'd call a nondeterministic Turing machine that halts on at least one branch for all inputs, but may loop on others. Is there a name for such a thing? I see later in this chapter the word verifier, but that doesn't seem to fit... I think that refers to an algorithm.

A verifier for a language $A$ is an algorithm $V$, where $$A=\{w\mid V\text{ accepts }\langle w,c\rangle\text{ for some string c}\}.$$ We measure the time of a verifier only in terms of the length of $w$, so a polynomial time verifier runs in polynomial time in the length of $w$. A language $A$ is polynomially verifiable if it has a polynomial time verifier.

-

Perhaps just in the definition of the language recognized by a NTM? An NTM accepts a string $w$ if there exists at least one computation path that ends in the accepting state ... but not necessarily this happens for all input strings (otherwise L(NTM) = \Sigma^* ) – Vor Feb 12 at 16:46
I believe that you would say that the machine "accepts" the language. – Philip Feb 12 at 19:03

## 1 Answer

The idea is that a deterministic TM will always answer Yes/No in finite time (else the whole idea makes no sense). And to do that, the deterministic simulation of the NTM can't just go off into lala-land on some branches, i.e., every branch must end in yes/no at a finite depth. It decides (gives you a definite answer). If not all branches halt, it can verify (i.e., given a word in the language it is guaranteed to answer Yes; if not, perhaps it anwers No, perhaps it loops).

-

Well, clearly an NTM can indeed have branches that are infinitely deep just by virtue of trying to solve an undecidable problem. What do you mean then to say that it can't? Or am I misunderstanding something? – agent154 Feb 20 at 20:39
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 6, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9336438775062561, "perplexity_flag": "head"}