请输入您要查询的字词:

 

单词 DecisionProblem
释义

decision problem


Let T be a Turing machineMathworldPlanetmath and let LΓ+ be a languagePlanetmathPlanetmath. We say T decides L if for any xL, T accepts x, and for any xL, T rejects x.

We say T enumeratesMathworldPlanetmath L if:

xL iff T accepts x

For some Turing machines (for instance non-deterministic machines) these definitions are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath, but for others they are not. For example, in order for a deterministic Turing machine T to decide L, it must be that T halts on every input. On the other hand T could enumerate L if it does not halt on some strings which are not in L.

L is sometimes said to be a decision problem, and a Turing machine which decides it is said to solve the decision problem.

The set of strings which T accepts is denoted L(T).

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 20:43:40