Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations
type: Item
instance of: scholarly article
title: Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations
zbMATH Open document ID: 1061.03075
author: Verónica Becher
author: Serge Grigorieff
published in: Theoretical Computer Science
publication date: 2004-10-27T00:00:00Z
review text: The authors consider the space \(2^{\leq \omega} = 2^* \cup 2^\omega\) in the context of possibly infinite computations, which can result in finite or infinite outputs. The paper is divided into 10 sections. The first one gives a review of the fundamental notions, recalls the known important results, and describes the main purpose of the article. The second section is about sets of words, especially a lot of space is devoted to the prefix ordering of words and properties of checkable and recursively enumerable sets of words. This material is introduced as useful to characterize the computable subsets of \(2^{\leq \omega}\). In the third section, the topological space \(2^{\leq \omega}\) is discussed: different types of topologies are presented, characteristics of open, closed and clopen sets for \(2^{\leq \omega}\) and \(2^{\omega}\) are given. Section 4 gives a self-contained direct approach of the computability notion for \(2^{\leq \omega}\) by elaborating from the classical theory for \(2^{\omega}\). However, it is pointed out that computability over \(2^{\omega}\) is not induced by computability over \(2^{\leq \omega}\). A characterization of computable subsets by clopen sets is proved. Moreover, the arithmetical hierarchy over \(2^{\leq \omega}\) is obtained as an effectivization of the finite levels of the Borel hierarchy, and logical expression of the arithmetical hierarchy is added. In the fifth section, semicomputability with possibly infinite computations is considered. For this purpose, monotone Turing machines are used. With this notion, the definition of computable and semicomputable total maps with domain among the sets \(2^*, 2^\omega\), \(2^{\leq \omega}\) and range in the set \(2^{\leq \omega}\) are given. The properties of such maps are listed, and the syntactical complexity of some predicates involving computable and semicomputable maps is established. The next section contains a detailed analysis of relations between continuity and computability …
reviewed by: Jerzy Mycka
Mathematics Subject Classification ID: 03F60
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 03D55
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D45
zbMATH DE Number: 2111106
zbMATH Keywords: infinite computation
zbMATH Keywords: continuity
zbMATH Keywords: semicontinuity
zbMATH Keywords: computability
zbMATH Keywords: semicomputability
zbMATH Keywords: monotone Turing machines
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.03.026
OpenAlex ID: W2015307217
Wikidata QID: Q61927045
cites work: Random reals and possibly infinite computations Part I: Randomness in ∅′
cites work: Adherences of languages
cites work: Recursive characterization of computable real-valued functions and relations
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Algorithmic entropy of sets
cites work: Wadge hierarchy and Veblen hierarchy. I: Borel sets of finite rank
cites work: \(X\)-automata on \(\omega\)-words
cites work: Computable functionals of finite types
cites work: Kolmogorov complexity and set theoretical representations of integers
cites work: Q4885914
cites work: Computable functionals
cites work: On the definition of computable functionals
cites work: On the definitions of computable real continuous functions
cites work: Q3687738
cites work: The topological structure of adherences of regular languages
cites work: Q4323294
cites work: Q5541832
cites work: Q3226754
cites work: Q3262213
cites work: Q4070738
cites work: Q4337021
cites work: Descriptive set theory
cites work: On computable sequences
cites work: Classical recursion theory. The theory of functions and sets of natural numbers
cites work: Q5317419
cites work: Compact zero-dimensional metric spaces of finite type
cites work: Infinite-word languages and continuous mappings
cites work: Q5573961
cites work: Process complexity and effective random tests
cites work: On degrees of unsolvability
cites work: Q4273953
cites work: Q4140968
cites work: Q3030812
cites work: Q3777489
cites work: Rekursive Folgenmengen I
cites work: On Computable Numbers, with an Application to the Entscheidungsproblem
cites work: Arithmetische Operatoren
cites work: Type 2 recursion theory
cites work: Q3751553
cites work: Computability on computable metric spaces
cites work: Q4485693
cites work: Theory of representations
cites work: Type 2 computational complexity of functions on Cantor's space
cites work: Computability theory of generalized functions
DBLP publication ID: journals/tcs/BecherG04
DOI: 10.1016/J.TCS.2004.03.026
description: scientific article; zbMATH DE number 2111106