PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (211)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (36)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very low Entry average rating: No information on entry rating
decision problem (Definition)

Let $ T$ be a Turing machine and let $ L\subseteq\Gamma^+$ be a language. We say $ T$ decides $ L$ if for any $ x\in L$, $ T$ accepts $ x$, and for any $ x\notin L$, $ T$ rejects $ x$.

We say $ T$ enumerates $ L$ if:

$\displaystyle x\in L$    iff $\displaystyle T$    accepts $\displaystyle x$

For some Turing machines (for instance non-deterministic machines) these definitions are equivalent, 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)$.



"decision problem" is owned by Henry.
(view preamble)

View style:

Also defines:  enumerates, decide
Log in to rate this entry.
(view current ratings)

Cross-references: strings, deterministic Turing machine, order, equivalent, definitions, machines, language, Turing machine
There are 24 references to this entry.

This is version 9 of decision problem, born on 2002-09-05, modified 2002-09-07.
Object id is 3423, canonical name is Decides.
Accessed 6888 times total.

Classification:
AMS MSC: 68Q25 (Computer science :: Theory of computing :: Analysis of algorithms and problem complexity)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)