This HTML5 document contains 25 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dct	http://purl.org/dc/terms/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
dbt	http://dbpedia.org/resource/Template:
rdfs	http://www.w3.org/2000/01/rdf-schema#
freebase	http://rdf.freebase.com/ns/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
n6	http://en.wikipedia.org/wiki/
dbp	http://dbpedia.org/property/
dbc	http://dbpedia.org/resource/Category:
prov	http://www.w3.org/ns/prov#
xsdh	http://www.w3.org/2001/XMLSchema#
gold	http://purl.org/linguistics/gold/
dbr	http://dbpedia.org/resource/

Statements

Subject Item

dbr:Computation_history

rdfs:label

Computation history

rdfs:comment

In computer science, a computation history is a sequence of steps taken by an abstract machine in the process of computing its result. Computation histories are frequently used in proofs about the capabilities of certain machines, and particularly about the undecidability of various formal languages. Formally, a computation history is a (normally finite) sequence of configurations of a formal automaton. Each configuration fully describes the status of the machine at a particular point. To be valid, certain conditions must hold:

owl:sameAs

freebase:m.0266zgq

dbp:wikiPageUsesTemplate

dbt:Reflist

dct:subject

dbc:Theory_of_computation

gold:hypernym

dbr:Sequence

prov:wasDerivedFrom

n6:Computation_history?oldid=1031336226&ns=0

dbo:wikiPageID

7620568

dbo:wikiPageLength

7211

dbo:wikiPageRevisionID

1031336226

dbo:wikiPageWikiLink

dbr:Finite-state_machine dbr:Determinism dbr:Context-free_language dbr:Mathematical_proof dbr:Abstract_machine dbr:Turing_machine dbr:Computer_science dbr:Automaton dbr:Pushdown_automaton dbr:Finite_set dbr:Undecidable_problem dbr:Formal_language dbc:Theory_of_computation

dbo:abstract

In computer science, a computation history is a sequence of steps taken by an abstract machine in the process of computing its result. Computation histories are frequently used in proofs about the capabilities of certain machines, and particularly about the undecidability of various formal languages. Formally, a computation history is a (normally finite) sequence of configurations of a formal automaton. Each configuration fully describes the status of the machine at a particular point. To be valid, certain conditions must hold: * the first configuration must be a valid initial configuration of the automaton and * each transition between adjacent configurations must be valid according to the transition rules of the automaton. In addition, to be complete, a computation history must be finite and * the final configuration must be a valid terminal configuration of the automaton. The definitions of "valid initial configuration", "valid transition", and "valid terminal configuration" vary for different kinds of formal machines. A deterministic automaton has exactly one computation history for a given initial configuration, though the history may be infinite and therefore incomplete.

foaf:isPrimaryTopicOf

n6:Computation_history