About: Enumeration reducibility

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Enumeration reducibility Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FEnumeration_reducibility

In computability theory and computational complexity theory, enumeration reducibility is a method of reduction that determines if there is some effective procedure for determining enumerability between sets of natural numbers. An enumeration in the context of e-reducibility is a listing of the elements in a particular set, or collection of items, though not necessarily ordered or complete. According to Hartley Rogers Jr., an intuitive model that can be used to explain e-reducibility is as follows:

Attributes	Values
rdfs:label	Enumeration reducibility (en)
rdfs:comment	In computability theory and computational complexity theory, enumeration reducibility is a method of reduction that determines if there is some effective procedure for determining enumerability between sets of natural numbers. An enumeration in the context of e-reducibility is a listing of the elements in a particular set, or collection of items, though not necessarily ordered or complete. According to Hartley Rogers Jr., an intuitive model that can be used to explain e-reducibility is as follows: (en)
dcterms:subject	Reduction (complexity) Computability theory Mathematical logic
Wikipage page ID	66125656 (xsd:integer)
Wikipage revision ID	1121154142 (xsd:integer)
Link from a Wikipage to another Wikipage	Robert M. Solovay Reduction (complexity) John Myhill Richard M. Friedberg Intersection Complement (set theory) Computability theory Negation Oracle machine Enumeration Function (mathematics) General recursive function Arithmetical hierarchy Computation Computational complexity theory Partial function Many-one reduction Hartley Rogers, Jr. Truth-table reduction Finite set Computability theory Mathematical logic Supremum Natural number Recursively enumerable set Reduction (recursion theory) Set (mathematics) Kleene's recursion theorem dbr:Mathematical_Logic_Quarterly Monus Turing reduction Enumerability Reducibility relation
Link from a Wikipage to an external page	https://web.archive.org/web/20200208205636/https:/pdfs.semanticscholar.org/1c6c/3e5e245869e5282e07a655e475c83e60883e.pdf https://www.academia.edu/6411846/_S_C_Kleene_Introduction_to_Metamathematics_Book_Fi_org_1_ http://citeseerx.ist.psu.edu/viewdoc/download%3Fdoi=10.1.1.95.8166&rep=rep1&type=pdf
sameAs	Enumeration reducibility Enumeration reducibility
has abstract	In computability theory and computational complexity theory, enumeration reducibility is a method of reduction that determines if there is some effective procedure for determining enumerability between sets of natural numbers. An enumeration in the context of e-reducibility is a listing of the elements in a particular set, or collection of items, though not necessarily ordered or complete. E-reducibility is a form of positive reducibility, meaning that only positive information is processed. Positive information denotes the logic syntax for "and" and "or". The syntax for negation, "not" is not included or used. According to Hartley Rogers Jr., an intuitive model that can be used to explain e-reducibility is as follows: Let sets and be given. Consider a procedure that is determined by a finite set of instructions in the following way. A computation is begun. The computation proceeds algorithmically except that, from time to time, the computing agent may be requested to obtain an “input" integer, and, from time to time the procedure yields an “output” integer. When an input is requested, any integer, or no integer, may be supplied. Assume that when the members of are supplied, in any order whatsoever as inputs, then the computation always eventually yields the set , in some order, as outputs. The order in which the members of appear may vary as the order of inputs varies. (We permit repetitions in the listing of and in the listing of .) If such a procedure exists we say that is enumeration reducible to . The concept of e-reducibility was first introduced by the results of John Myhill, which concluded that "a set is many-one complete if and only if it is recursively enumerable and its complement is productive". This result extends to e-reducibility as well. E-reducibility was later formally codified by Rogers and his collaborator Richard M. Friedberg in Zeitschrift für mathematische Logik und Grundlagen der Mathematik (the predecessor of ) in 1959. (en)
prov:wasDerivedFrom	wikipedia-en:Enumeration_reducibility?oldid=1121154142&ns=0
page length (characters) of wiki page	12624 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Enumeration_reducibility
is Link from a Wikipage to another Wikipage of	Reduction (computability theory) Kleene's recursion theorem
is foaf:primaryTopic of	wikipedia-en:Enumeration_reducibility

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (61 GB total memory, 51 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software