Paper Info
Title
Abstract Geometrical Computation and Computable Analysis
Abstract
Extended Signal machines are proven able to compute any computable function in the understanding of recursive/computable analysis (CA), here type-2 Turing machines (T2-TM) with signed binary encoding. This relies on an intermediate representation of any real number as an integer (in signed binary) plus an exact value in ( *** 1,1) which allows to have only finitely many signals present outside of the computation. Extracting a (signed) bit, improving the precision by one bit and iterating the T2-TM only involve standard signal machines. For exact CA-computations, T2-TM have to deal with an infinite entry and to run through infinitely many iterations to produce an infinite output. This infinite duration can be provided by constructions emulating the black hole model of computation on an extended signal machine. Extracting/encoding an infinite sequence of bits is achieved as the limit of the approximation process with a careful handling of accumulations and singularities.
Year
DOI
Venue
2009
10.1007/978-3-642-03745-0_20
UC
Keywords
Field
DocType
infinite output,exact ca-computations,computable analysis,binary encoding,signed binary,infinite duration,extended signal machine,infinite sequence,computable function,abstract geometrical computation,infinite entry,turing machine,intermediate representation,black hole,model of computation
Discrete mathematics,Universal Turing machine,Sequence,Computer science,Algorithm,Model of computation,Turing machine,Computable number,Computable function,Computable analysis,Binary number
Conference
Volume
ISSN
Citations 
5715
0302-9743
4
PageRank 
References 
Authors
0.43
8
1
Name
Order
Citations
PageRank
Jérôme Durand-Lose112714.93