Number of the records: 1

Computation as an Unbounded Process

SYSNO ASEP	0368246
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	Computation as an Unbounded Process
Author(s)	van Leeuwen, J. (NL) Wiedermann, Jiří (UIVT-O)_{RID, SAI, ORCID}
Source Title	Theoretical Computer Science. - : Elsevier - ISSN 0304-3975 Roč. 429, 20 April (2012), s. 202-212
Number of pages	11 s.
Language	eng - English
Country	NL - Netherlands
Keywords	arithmetical hierarchy ; hypercomputation ; mind change complexity ; nondeterminism ; relativistic computation ; unbounded computation
Subject RIV	IN - Informatics, Computer Science
R&D Projects	GAP202/10/1333 GA ČR - Czech Science Foundation (CSF)
CEZ	AV0Z10300504 - UIVT-O (2005-2011)
UT WOS	000302822300022
EID SCOPUS	84858337195
DOI	10.1016/j.tcs.2011.12.040
Annotation	We develop a model of computation as an unbounded process, measuring complexity by the number of observed behavioural changes during the computation. In a natural way, the model brings effective unbounded computation up to the second level of the Arithmetical Hierarchy, unifying several earlier concepts like trial-and-error predicates and relativistic computing. The roots of the model can be traced back to the circular a-machines already distinguished by Turing in 1936.
Workplace	Institute of Computer Science
Contact	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Year of Publishing	2013

Number of the records: 1