Publication:5573961

zbMath0183.01401MaRDI QIDQ5573961

Hartley jun. Rogers

Publication date: 1967

zbMATH Keywords

recursion theory, constructive mathematics

Related Items

Intrinsic complexity of learning geometrical concepts from positive data, Robust learning -- rich and poor, Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations, The dimensions of individual strings and sequences, Enumerators of lambda terms are reducing constructively, On the difficulty of making social choices, Characterization of realizable space complexities, Back and forth relations for reduced abelian \(p\)-groups, Some results on numerical systems in \(\lambda\)-calculus, Operations and compositions in transrecursive operators, Decidable and undecidable logics with a binary modality, Relations between certain reducibilities, Categoricity of finitely generated algebraic systems in HF-logic, One strengthening of \(Q\)-reducibility, Logic and probabilistic systems, The intrinsic difficulty of recursive functions, Fuzzy logic and arithmetical hierarchy, Effective inseparability in a topological setting, Recursion theoretic models of learning: Some results and intuitions, The expressiveness of locally stratified programs, On computability by logic programs, Complexity limitations on quantum computation, Computable preference and utility, Time paradoxes reviewed, Turing reducibility as algebraic embeddability, Some reducibilities and splittings of recursively enumerable sets, On the time complexity of partial real functions, Heterogeneous active agents. III: Polynomially implementable agents, On degrees of recursively enumerable sets, Computable processes and bisimulation equivalence, Non-computable rational expectations equilibria, Effective choice of constructivizations and recursive consistency of problems on constructive models, Positive algebras with countable congruence lattices, Semantic universality of theories over a superlist, Bounded truth table does not reduce the one-query tautologies to a random oracle, On arithmetic in the Cantor-Łukasiewicz fuzzy set theory, Towards a theory of semantics and compilers for programming languages, Beziehungen zwischen gewissen Klassen effektiv topologischer Räume, What makes some language theory problems undecidable, The Shoenfield absoluteness lemma, On index sets, An answer to a question by P. R. Young, Two theorems on recursively enumerable sets, The enumerability and invariance of complexity classes, On the structure of subrecursive degrees, Three theorems concerning principal AFLs, Subrecursive programming languages. II. On program size, On the reducibility of \(\Pi_ 1^ 1\) sets, Hyper-hypersimple \(m\)-degrees, Abstract computational complexity and cycling computations, On a hierarchy of sets. III, The use of lists in the study of undecidable problems in automata theory, On \(m\)-degrees of recursively enumerable sets, Complexity of winning strategies, Effective operators with no strong gaps, Free and almost-free subsemigroups of a free semigroup, Combinatorial systems. I: Cylindrical problems, Valutazione comparativa di una classe di metodi iterativi per equazioni in spazi di Banach, Subrecursive program schemata I P II. I: Undecidable equivalence problems. II: Decidable equivalence problems, Significance arithmetic: The carrying algorithm, On effectively hypersimple sets, Maximal sets in \(\alpha\)-recursion theory, On the subalgebras of R. Robinson's algebras, The index sets of m-degrees, Sets without subsets of higher many-one degree, On learning to coordinate: random bits help, insightful normal forms, and competency isomorphisms, All superlinear inverse schemes are coNP-hard, On \(R\)-universal functions, Learning erasing pattern languages with queries, Relations between Gold-style learning and query learning, 2000 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium 2000, On the structures inside truth-table degrees, Can partial indexings be totalized?, On computable automorphisms of the rational numbers, Noncappable enumeration degrees below 0_e^′, Splitting properties of n-c.e. enumeration degrees, Is the Mandelbrot set computable?, Hierarchies in?-spaces and applications, On revision operators, Embedding the diamond in the Σ₂ enumeration degrees, On the weak Kleene scheme in Kripke's theory of truth, Presburger arithmetic with unary predicates is Π₁¹ complete, A universal inductive inference machine, A construction for recursive linear orderings, Π₀¹-classes and Rado's selection principle, Herbrand semantics, the potential infinite, and ontology-free logic, Simultaneous strong separations of probabilistic and unambiguous complexity classes, Generalized kolmogorov complexity and other dual complexity measures, Undecidability of the identity problem for finite semigroups, Spring Meeting of the Association for Symbolic Logic, San Francisco, 1991, What is an inference rule?, A noninitial segment of index sets, Periodicity in generations of automata, Systems of notations and the ramified analytical hierarchy, Cores of Π₁¹ sets of reals, On subcreative sets and S-reducibility, Degrees of unsolvability associated with Markov algorithms, Continuity and elementary logic, Note on the Kondo-Addison theorem, Nonrecursive tilings of the plane. I, Learning in the presence of inaccurate information, A theory of nonmonotonic rule systems I, The isomorphism conjecture holds and one-way functions exist relative to an oracle, Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals, Permitting, forcing, and copying of a given recursive relation, Index sets and presentations of complexity classes, On aggregating teams of learning machines, A formal specification of document processing, Higman's embedding theorem in a general setting and its application to existentially closed algebras, Learning-theoretic perspectives of acceptable numberings, Randnomness, computability, and algebraic specifications, Kolmogorov numberings and minimal identification, Binary search and recursive graph problems, Abstract fairness and semantics, Universality of the chip-firing game, Monadic logic programs and functional complexity, Positive equivalences, Upward closure and cohesive degrees, On the intrinsic complexity of learning recursive functions, Decidability results for primitive recursive algorithms, Borel hierarchy and omega context free languages., P-immune sets with holes lack self-reducibility properties., Random elements in effective topological spaces with measure., Homomorphisms and quotients of degree structures, A blend of methods of recursion theory and topology., Computability-theoretic and proof-theoretic aspects of partial and linear orderings, Some connections between bounded query classes and non-uniform complexity., Learning how to separate., Separation of uniform learning classes., Watson-Crick D0L systems: Generative power and undecidable problems., Learning by switching type of information., Algorithmic complexity of recursive and inductive algorithms, Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines, Experience, generations, and limits in machine learning, Robust learning aided by context, Quasi-minimal enumeration degrees and minimal Turing degrees, Learning languages and functions by erasing, Computability on continuous, lower semi-continuous and upper semi-continuous real functions, A second step towards complexity-theoretic analogs of Rice's Theorem, Ordinal mind change complexity of language identification, \(e\)-immune sets, \(L(A)=L(B)\)? decidability results from complete formal systems, Predicting zero coefficients in formal power series computations., Mind change complexity of learning logic programs, Modelization of deterministic rational relations, Language learning from texts: Degrees of intrinsic complexity and their characterizations, \(\forall \exists^{5}\)-equational theory of context unification is undecidable, Effective metric spaces and representations of the reals., Effective simultaneous approximability of reals., Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees, A blend of methods of recursion theory and topology: a \(\Pi_1^0\) tree of shadow points, A Banach-Mazur computable but not Markov computable function on the computable real numbers, Weakly useful sequences, The constructive reals as a Java library, Increasing the power of uniform inductive learners, Predictive complexity and information, Models of arithmetic in \(A\)-isols, Upper semilattice of recursively enumerable sQ-degrees, Refined hierarchy of formulas, Is independence an exception?, Reasoning about strings in databases, A revenge-immune solution to the semantic paradoxes, Possible-worlds semantics for modal notions conceived as predicates, Computable classes of constructive models with non-limit-equivalent indexations, Complexity of the calculus of continued fraction representation of real numbers, A universal partial recursive function, The calculi of emergence: Computation, dynamics and induction, On the computational complexity of Longley's \(H\) functional, Some orbits for \({\mathcal E}\), Constructivizability of superatomic Boolean algebras, A generalized constructable continuum, Many-one degrees associated with semi-Thue systems, Recursively enumerable many-one degrees, Su certe teorie non enumerabili. (Sulle limitazioni dei sistemi formali. I.), Some aspects of generalized computability, Some problems of completeness of arithmetic, Orbits of computably enumerable sets: Low sets can avoid an upper cone, Some conservation results on weak König's lemma, Learning classes of approximations to non-recursive functions., The synthesis of language learners., Incremental concept learning for bounded data mining., Recursive computational depth., Robust behaviorally correct learning., The complexity of universal text-learners., On a generalized notion of mistake bounds, Suboptimal measures of predictive complexity for absolute loss function, Learning by the process of elimination, Degrees of Dowd-type generic oracles, On complexity of easy predictable sequences, Tractable reasoning via approximation, Levesque's axiomatization of only knowing is incomplete, Complexity of the \(r\)-query tautologies in the presence of a generic oracle, The complexity of predicate default logic over a countable domain, Thue trees, Advanced elementary formal systems., Decision lists over regular patterns., Refutable language learning with a neighbor system., On learning of functions refutably., On the expressiveness of choice quantification, Automatic graphs and D0L-sequences of finite graphs, Algebraically closed groups, A comparison of polynomial time reducibilities, Completely enumerated sets, Maximal and everywhere-defined functionals, Some properties of the constructivization of Boolean algebras, Translational lemmas, polynomial time, and \((\log n)^j\)-space, An operator embedding theorem for complexity classes of recursive functions, Polynomial and abstract subrecursive classes, The halt problem and theory of hierarchies, Comparing complexity classes, Deterministic Lindenmayer languages, nonterminals and homomorphisms, On the density of honest subrecursive classes, Nonexistence of program optimizers in several abstract settings, Efficient linear orders, Computability concepts for programming language semantics, Techniques for separating space complexity classes, The polynomial-time hierarchy, On expandability of models of Peano arithmetic. I, Complexity-class-encoding sets, Non-self-equivalent constructivization of atomic Boolean algebras, Enumerations of families of general recursive functions, Partial degrees and \(r\)-degrees, Two theorems on finite unions of regressive immune sets, Das Entscheidungsproblem der Klasse von Formeln, die höchstens zwei Primformeln enthalten, Algorithmic entropy of sets, Two theorems on computable numberings, On an effective hierarchy of communicating processes: Separation principle and testing, Investigations on measure-one identification of classes of languages, Decidability of the finiteness of ranges of tree transductions, Initial segments of effectively finite orders, Achilles and the tortoise climbing up the hyper-arithmetical hierarchy, A domain-theoretic approach to computability on the real line, Relatively recursive reals and real functions, Ergodic theorems for individual random sequences, Non-stochastic infinite and finite sequences, On interpreting Chaitin's incompleteness theorem, Complexity properties of recursively enumerable sets and \(sQ\)-completeness, Learning with refutation, Recursively compressible sets, Computability on subsets of Euclidean space. I: Closed and compact subsets, Computable Banach spaces via domain theory, On approximate and algebraic computability over the real numbers, An effective Riemann Mapping Theorem, Markov's constructive analysis; a participant's view, Effectiveness of the global modulus of continuity on metric spaces, Computability structure of the Sobolev spaces and its applications, What's in a function?, Branching in the enumeration degrees of the \(\Sigma_2^0\) sets, Communication, computability, and common interest games, What's the difference, Approximation methods in inductive inference, Computable isomorphisms, degree spectra of relations, and Scott families, Point-free topological spaces, functions and recursive points; filter foundation for recursive analysis. I, Sets of generator and automorphism bases for the enumeration degrees, Forecasting errors and bounded rationality: An example, Recursive and nonextendible functions over the reals; filter foundation for recursive analysis. II, Topological queries in spatial databases, Maximal machine learnable classes, \(\Pi_ 1^ 1\)-universality of some propositional logics of concurrent programs, Constructive proofs of the range property in lambda calculus, Computational foundations of basic recursive function theory, Set-theoretical and other elementary models of the \(\lambda\)-calculus, Composition is almost (but not quite) as good as \(s-1-1\), Splitting theorems in recursion theory, Hyperarithmetical relations in expansions of recursive structures, Effective choice for relations and reducibilities in classes of constructive and positive models, Homomorphisms onto negative algebras, Primitive Jordan algebras, Finitely generated groups with the M. Hall property, The concept of a binary relation over partial enumerated sets, Locally finite simple groups as a product of two inert subgroups, Local characterizations of infinite alternating and Lie type groups, A semiorthogonal sum of monocomposition algebras with unity, A finitary realizable list of properties, Admissible sets in group theory, Superdecomposable pure injective modules over commutative valuation rings, Gap-definable counting classes, Recursive versus recursively enumerable binary relations, Proving partial order properties, A theory of timed automata, Logical and schematic characterization of complexity classes, Dynamical system where proving chaos is equivalent to proving Fermat's conjecture, Certain properties of deducibility operators, Inseparability in recursive copies, On speedable and levelable vector spaces, Recursive unary algebras and trees, Kolmogorov complexity arguments in combinatorics, Some descriptive-set-theoretical problems in complexity theory, Gödel's incompleteness theorem, On the solvability of domino snake problems, Characterizing language identification by standardizing operations, Computational depth and reducibility, Progress measures, immediate determinacy, and a subset construction for tree automata, On problems with short certificates, The structure of the honest polynomial m-degrees, On the danger of half-truths, Power set recursion, Generalized computations with binary oracles, Small universal register machines, On proving that a graph has no large clique: A connection with Ramsey theory, Learning all subfunctions of a function, On the classification of recursive languages, Tarski's theory of definability: Common themes in descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic, Applying, extending, and specializing pseudorecursiveness, Frequency computation and bounded queries, Anomalous learning helps succinctness, Computing with infinitary logic, Effective category and measure in abstract complexity theory, P-selectivity: Intersections and indices, Some undecidable termination problems for semi-Thue systems, Computable concurrent processes, Training digraphs, On a question about learning nearly minimal programs, Case-based representation and learning of pattern languages, Towards a mathematical theory of machine discovery from facts, Tarskian and Kripkean truth, The self-embedding theorem of \(\text{WKL}_ 0\) and a non-standard method, Characterizing language identification in terms of computable numberings, The analytical completeness of Dzhaparidze's polymodal logics, On the non-existence of maximal inference degrees for language identification, Algebraic and calculus query languages for recursively typed complex objects, Peano arithmetic as axiomatization of the time frame in logics of programs and in dynamic logics, Recursive properties of relations on models, If not empty, NP-P is topologically large, Effective moduli from ineffective uniqueness proofs. An unwinding of de La Vallée Poussin's proof for Chebycheff approximation, The distribution of the generic recursively enumerable degrees, Recursiveness and preference orderings, Elementary definability of symmetry groups, Some algorithmic problems for relatively free groups, An improved zero-one law for algorithmically random sequences, A notion of information related to computation, Rudimentary relations and primitive recursion: A toolbox, On the relative sizes of learnable sets, On sets polynomially enumerable by iteration, Undecidability and incompleteness in classical mechanics, On the effective content of asymptotic verifications of Edgeworth's Conjecture, The Mapmaker's dilemma, Uncountable degree spectra, On p-creative sets and p-completely creative sets, Algebraic specifiability of data types with minimal computable parameters, Learning in the presence of partial explanations, Sufficiency conditions for theories with recursive models, Generic oracles, uniform machines, and codes, Automorphisms of the lattice of recursively enumerable sets: Orbits, Fuzzy grammars and recursively enumerable fuzzy languages, Aggregating inductive expertise on partial recursive functions, Fuzzy sets as named sets, Positive algebras with congruences of finite index, Myhill's work in recursion theory, How complicated is the set of stable models of a recursive logic program?, Fuzzy subsets: A constructive approach, On the strength of König's duality theorem for infinite bipartite graphs, Proof systems for infinite behaviours, Fairness, distances and degrees, Completions of perpetual logic programs, On uniform learnability of language families, Recursively presented games and strategies, On Turing degrees of Walrasian models and a general impossibility result in the theory of decision-making, Some aspects of effectively constructive mathematics that are relevant to the foundations of neoclassical mathematical economics and the theory of games, Hamiltonian paths in infinite graphs, Independence of the induction principle and the axiom of choice in the pure calculus of constructions, Final algebras, cosemicomputable algebras and degrees of unsolvability, Diagonalization, uniformity, and fixed-point theorems, Minimum-complexity pairing functions, Foreground automata, Nondiamond theorems for polynomial time reducibility, Logic, ontology, mathematical practice, The \(n\)-rea enumeration degrees are dense, \(E\)-hyperimmune sets, Mal'cev's correspondence and unsolvability, The number of algebras over simple sets, Generalizations of enumeration reducibility using recursive infinitary propositional sentences, Countable thin \(\Pi^0_1\) classes, A new method for undecidability proofs of first order theories, Total sets and objects in domain theory, Some effectively infinite classes of enumerations, On the power of inductive inference from good examples, The extent and density of sequences within the minimal-program complexity hierarchies, Index sets in 0', On different kinds of indefinite, On computability with functionals, Two existence theorems for computable numerations, Approximations to the halting problem, WCS-analysis of the context-sensitive, Three theorems on elementary theories and tt-reducibility, Gruppen mit vorgeschriebenem Wortproblem, The forcing companions of number theories, Recursive function theory and numerical analysis, btt-reducibility, On btt-reducibilities. II, On complete btt-degrees, Closure operations on measures of computational complexity, The Turing degree of the inherent ambiguity problem for context-free languages, A note on extending equivalence theories of algorithms, Generalized computability and the descriptive theory of sets, Significato e verita nell'aritmetica peaniana, Ambiguity in the developmental systems of Lindenmayer, Index sets of degrees of unsolvability, Truth tabular degrees of recursively enumerable sets, On frequency-enumerable sets, NP-Creative sets: A new class of creative sets in NP, Strong self-reducibility precludes strong immunity, The complexity of ODD_n^A, The distribution of properly Σ₂⁰ e-degrees, The relation of A to Prov ˹A˺ in the Lindenbaum sentence algebra, Splittings of effectively speedable sets and effectively levelable sets, Parsimony hierarchies for inductive inference, Degrees of unsolvability of continuous functions, Π₁¹ relations and paths through, Every polynomial-time 1-degree collapses if and only if P = PSPACE, Arithmetical independence results using higher recursion theory, UNSOLVABILITY LEVELS OF OPERATION PROBLEMS FOR SUBCLASSES OF CONTEXT-FREE LANGUAGES, Uniformly introreducible sets, The degrees of hyperhyperimmune sets, Sets with no subset of higher degree, Constructive order types on cuts, A note on degrees of subsets¹, [https://portal.mardi4nfdi.de/wiki/Software:5581622 Eine Bemerkung zum Begriff der zuf�lligen Folge], Effectively retractable theories and degrees of undecidability, Index sets of finite classes of recursively enumerable sets, On primitive recursive permutations and their inverses, A note on the hyperarithmetical hierarchy, Definability in the monadic second-order theory of successor, Speed-Ups by changing the order in which sets are enumerated, On analytic well-orderings, Hierarchies of Boolean algebras, Some contrasts between degrees and the arithmetical hierarchy, Recursively enumerable sets which are uniform for finite extensions, Subrecursiveness: Machine-independent notions of computability in restricted time and storage, Minimum models of analysis, Computational speed-up by effective operators, Decision problems for tag systems, The strong homogeneity conjecture, A discrete chain of degrees of index sets, Ramsey's theorem and recursion theory, Recursion in Partial Type‐1 Objects With Well‐Behaved Oracles, Recursive Structures and Ershov's Hierarchy, Intrinsically Hyperarithmetical Sets, A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS, Random reals and possibly infinite computations Part I: Randomness in ∅′, Weakly computable real numbers, Semantics of constructions. I: The traditional approach, Achilles and the tortoise climbing up the arithmetical hierarchy, Robust learning with infinite additional information, Costs of general purpose learning, On the learnability of recursively enumerable languages from good examples, Probabilistic inductive inference: A survey, Complexity properties of recursively enumerable sets and \(bsQ\)-completeness, Robust learning is rich, Cooperation and computability in \(n\)-player games, Arithmetic complexity of the predicate logics of certain complete arithmetic theories, Hyper-polynomial hierarchies and the polynomial jump, Representations versus numberings: On the relationship of two computability notions, Control structures in hypothesis spaces: The influence on learning, Predictive learning models for concept drift, Closedness properties in ex-identification, On the asymptotic behaviour of primitive recursive algorithms, Cupping and noncupping in the enumeration degrees of \(\Sigma_ 2^ 0\) sets, Infinitary self-reference in learning theory, Spatial/kinematic domain and lattice computers, Ignoring data may be the only way to learn efficiently, Non-p-generic and strongly nonbranching degree, On the strength of König's duality theorem for countable bipartite graphs, The degrees of conditional problems, A quantitative analysis of modal logic, EXTENSIONAL PROCESSING OF PROBABILITY MEASURES, An observation on probability versus randomness with applications to complexity classes, Statistical properties of finite sequences with high Kolmogorov complexity, Machine learning of higher-order programs, Recursiveness of ω‐Operations, System function languages, The basis decision problem in λ‐calculus, A New Reducibility between Turing‐ and wtt‐Reducibility, Jump Theorems for REA Operators, A variant of the Notion of Semicreative set, Non-p-generic and strongly nonbranching degree, Almost weakly 2-generic sets, Diophantine equivalence and countable rings, On first-order theories with provability operator, Effective Structures, On Nondeterminism, Enumeration Reducibility and Polynomial Bounds, Knowledge representation as domain, Embeddings in the Strong Reducibilities Between 1 and npm, Computability of String Functions Over Algebraic Structures Armin Hemmerling, The structure of intrinsic complexity of learning, Domains for Computation in Mathematics, Physics and Exact Real Arithmetic, Unnamed Item, On effective topological spaces, Recursive elements and constructive extensions of computable local integral domains, Post's problem and his hypersimple set, Encodability of Kleene's O, 2002 European Summer Meeting of the Association for Symbolic Logic Logic Colloquium '02, Regular enumerations, Some strongly undecidable natural arithmetical problems, with an application to intuitionistic theories, DEFINABILITY OF THE JUMP OPERATOR IN THE ENUMERATION DEGREES, Wadge Degrees ofω-Languages of Deterministic Turing Machines, Nonlinear phenomena in spaces of algorithms, Embedding finite lattices into the Σ₂⁰ enumeration degrees, Unnamed Item, Barwise: Infinitary Logic and Admissible Sets, On the robustness of ALMOST-$\mathcal {R}$, Theoretical Pearls:Representing ‘undefined’ in lambda calculus, On centain decompositions of Gödel numberings, Decidability of the “almost all” theory of degrees, Index sets in Ershov's hierarchy, Mitotic recursively enumerable sets, On an open problem in classification of languages, Boolean reducibility, Generalization versus classification, Prudence in vacillatory language identification, Requirement systems, Fine hierarchies and Boolean terms, Feasible Graphs and Colorings, Some New Lattice Constructions in High R. E. Degrees, How to Compute Antiderivatives, Intrinsically II Relations, A Note on Closed Degrees of Difficulty of the Medvedev Lattice, Effectively and Noneffectively Nowhere Simple Sets, An enlarged family of packing polynomials on multidimensional lattices, Asymptotic conditional probabilities: The non-unary case, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Computational complexity of formal translations, Minimal-program complexity of pseudo-recursive and pseudo-random sequences, Σ_n sets which are Δ_n-incomparable (uniformly), A characterization ofR-maximal sets, Embedding relations in the lattice of recursively enumerable sets, The nonderivability in intuitionistic formal systems of theorems on the continuity of effective operations, Optimal enumerations and optimal gödel numberings, Uniform enumeration operations, On two complete sets in the analytical and the arithmetical hierarchies, A survey of partial degrees, On models of arithmetic—Answers to two problems raised by H. Gaifman, Honest bounds for complexity classes of recursive functions, Independent Gödel sentences and independent sets, Recursively presentable prime models, On complexity properties of recursively enumerable sets, Borel sets and hyperdegrees, “Helping”: several formalizations, Banach–Mazur games, comeager sets and degrees of unsolvability, On degrees of unsolvability and complexity properties, Descending sequences of degrees, On the complexity of finite, pushdown, and stack automata, Δ 2 0 -Mengen, Syntax and semantics of universal programming languages, Total complexity and the inference of best programs, A note on the number of zeros of polynomials and exponential polynomials, Unnamed Item, Unnamed Item, Derivatives of Computable Functions, Explicit mathematics with the monotone fixed point principle, Some Special Pairs of Σ2 e-Degrees, Incompleteness, Mechanism, and Optimism, Truth Definitions, Skolem Functions and Axiomatic Set Theory, Towards the Actual Relationship Between NP and Exponential Time, Uniform inseparability in explicit mathematics