Abstract We prove that the set of all recursive functions cannot be inferred using first-order queries in the query language containing extra symbols [+ , <]. The proof of this theorem involves a new decidability result about Presburger arithmetic which is of independent interest. Using our machinery, we show that the set of all primitive recursive functions cannot be inferred with a bounded number of mind changes, again using queries in [+, <]. Additionally, we resolve an open question in [7] about passive versus active learning.

Let We be the eth recursively enumerable (r.e.) set in a standard enumeration. The fixed point form of Kleene's recursion theorem asserts that for every recursive function f there exists e which is a fixed point of f in the sense that We = Wf(e). In this paper our main concern is to study the degrees of functions with no fixed points. We consider both fixed points in the strict sense above and fixed points modulo various equivalence relations on recursively enumerable sets. Our starting point for the investigation of the degrees of functions without (strict) fixed points is the following result due to M. M. Arslanov [A1, Theorem 1] and known as the Arslanov completeness criterion. Proofs of this result may also be found in [So1, Theorem 1.3] and [So2, Chapter 12], and we will give a game version of the proof in §5 of this paper. Theorem 1.1 (Arslanov). Let A be an r.e. set. Then A is complete (i.e. A has degree0′) iff there is a function f recursive in A with no fixed point.

Abstract Hofstadter has introduced the notion of an explicit Henkin sentence. Roughly speaking, an explicit Henkin sentence not only asserts its own provability, as ordinary Henkin sentences do, but explicitly provides a detailed description of a proof. We provide, in this paper, a precise formalization of Hofstadter's notion and then show that true explicit Henkin sentences exist.

Previous article Full AccessErratum: A Fast Monte-Carlo Test for PrimalityR. Solovay and V. StrassenR. Solovay and V. Strassenhttps://doi.org/10.1137/0207009PDFBibTexSections ToolsAdd to favoritesDownload CitationsTrack CitationsEmail SectionsAbout"Erratum: A Fast Monte-Carlo Test for Primality." SIAM Journal on Computing, 7(1), p. 118 Previous article FiguresRelatedReferencesCited ByDetails Improved circuits for a random pulse computer2020 43rd International Convention on Information, Communication and Electronic Technology (MIPRO) | 28 Sep 2020 Cross Ref Experimentally probing the algorithmic randomness and incomputability of quantum randomnessPhysica Scripta, Vol. 94, No. 4 | 1 February 2019 Cross Ref The Error Probability of the Miller–Rabin Primality TestLobachevskii Journal of Mathematics, Vol. 39, No. 7 | 20 September 2018 Cross Ref Deep or Wide? Learning Policy and Value Neural Networks for Combinatorial GamesComputer Games | 29 April 2017 Cross Ref HistoryProbability Logics | 25 October 2016 Cross Ref Computing (and Life) Is All about TradeoffsSpace-Efficient Data Structures, Streams, and Algorithms | 1 Jan 2013 Cross Ref Time in the Analysis of AlgorithmsModeling Time in Computing | 29 August 2012 Cross Ref Experimental evidence of quantum randomness incomputabilityPhysical Review A, Vol. 82, No. 2 | 6 August 2010 Cross Ref Smale's 17th problem: Average polynomial time to compute affine and projective solutionsJournal of the American Mathematical Society, Vol. 22, No. 2 | 6 November 2008 Cross Ref Primality Testing and Prime GenerationPrimality Testing and Integer Factorization in Public-Key Cryptography | 1 Jan 2004 Cross Ref Predicting Zero Coefficients in Formal Power Series ComputationsJournal of Symbolic Computation, Vol. 33, No. 3 | 1 Mar 2002 Cross Ref Realisation of a minimum-knowledge identification and signature schemeComputers & Security, Vol. 17, No. 3 | 1 Jan 1998 Cross Ref On randomization in sequential and distributed algorithmsACM Computing Surveys, Vol. 26, No. 1 | 1 Mar 1994 Cross Ref Interactive proof systems and alternating time—space complexityTheoretical Computer Science, Vol. 113, No. 1 | 1 May 1993 Cross Ref Chapter 9 Computational complexityComputing | 1 Jan 1992 Cross Ref Number Theory, ComplementsMathematics for Computer Algebra | 1 Jan 1992 Cross Ref Algorithms in Number TheoryAlgorithms and Complexity | 1 Jan 1990 Cross Ref Algorithms and RandomnessTheory of Probability & Its Applications, Vol. 32, No. 3 | 17 July 2006AbstractPDF (3481 KB)Reductions among number theoretic problemsInformation and Computation, Vol. 72, No. 3 | 1 Mar 1987 Cross Ref Randomized algorithms: An annotated bibliographyAnnals of Operations Research, Vol. 1, No. 3 | 1 Oct 1984 Cross Ref Information and ComputationAdvances in Computers Volume 23 | 1 Jan 1984 Cross Ref On Primality TestsDaniel J. LehmannSIAM Journal on Computing, Vol. 11, No. 2 | 31 July 2006AbstractPDF (253 KB)Discrete extremal problemsJournal of Soviet Mathematics, Vol. 15, No. 2 | 1 Jan 1981 Cross Ref On counting problems and the polynomial-time hierarchyTheoretical Computer Science, Vol. 12, No. 2 | 1 Oct 1980 Cross Ref Konzepte der Komplexitätstheorie illustriert am Beispiel des SortierensGI — 9. Jahrestagung | 1 Jan 1979 Cross Ref Recent directions in algorithmic researchTheoretical Computer Science Cross Ref Volume 7, Issue 1| Feb 1978SIAM Journal on Computing History Submitted:02 June 1977Published online:13 July 2006 Article & Publication DataArticle DOI:10.1137/0207009Article page range:pp. 118-118ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

Nonprincipal ultrafilters are harder to define in ZFC, and harder to obtain in ZF + DC, than nonprincipal measures. The function μ from P(X) to the closed interval [0, 1] is a measure on X if μ. is finitely additive on disjoint sets and μ(X) = 1. (P is the power set.) μ is nonprincipal if μ ({x}) = 0 for each x Є X. μ is an ultrafilter if Range μ= {0, 1}. The existence of nonprincipal measures and ultrafilters on any infinite X follows from the axiom of choice. Nonprincipal measures cannot necessarily be defined in ZFC. (ZF is Zermelo–Fraenkel set theory. ZFC is ZF with choice.) In ZF alone they cannot even be proved to exist. This was first established by Solovay [14] using an inaccessible cardinal. In the model of [14] no nonprincipal measure on ω is even ODR (definable from ordinal and real parameters). The HODR (hereditarily ODR) sets of this model form a model of ZF + DC (dependent choice) in which no nonprincipal measure on ω exists. Pincus [8] gave a model with the same properties making no use of an inaccessible. (This model was also known to Solovay.) The second model can be combined with ideas of A. Blass [1] to give a model of ZF + DC in which no nonprincipal measures exist on any set. Using this model one obtains a model of ZFC in which no nonprincipal measure on the set of real numbers is ODR. H. Friedman, in private communication, previously obtained such a model of ZFC by a different method. Our construction will be sketched in 4.1.

Let n be an odd integer. Take a random number a from a uniform distribution on the set $\{1, 2,\cdots, n -1\}$. If a and n are relatively prime, compute the residue $\varepsilon \equiv a^{(n - 1)/2}(\bmod n)$, where $ - 1 \leqq \varepsilon < n - 2$, and the Jacobi symbol $\delta = (a /n)$. If $\varepsilon = 6$, decide that n is prime. If either $\gcd (a,n) > 1$ or $\varepsilon \ne \delta $ decide that n is composite. Obviously, if n is prime, the decision made will be correct. We will show below, that for composite n the probability of an incorrect decision is $\leqq 1 / 2$. The number of multiprecision operations needed for the whole procedure is $< 6\log _2 n$. m-fold repetition using independent random numbers yields a Monte-Carlo test for primality with error probabilities 0 (if n is prime) and $< 2^{-m}$(if n is composite) and with multiprecision arithmetic cost $< 6m\log _2 n$.

Lynch showed that any set many-one reducible in polynomial time to arbitrarily sparse sets is polynomial time computable. We prove the analogous theorem for polynomial time Turing reproducibility.

We shall apply some of the results of Jensen [4] to deduce new combinatorial consequences of the axiom of constructibility, V = L. We shall show, among other things, that if V = L then for each cardinal λ there is a set A ⊆ λ such that neither A nor λ – A contain a closed set of type ω1. This is an extension of a result of Silver who proved it for λ = ω2, providing a partial answer to Problem 68 of Friedman [2]. The main results of this paper were obtained independently by both authors. If λ is an ordinal, E is said to be Mahlo (or stationary) in λ, if λ – E does not contain a closed cofinal subset of λ. Consider the statements: (J1) There is a class E of limit ordinals and a sequence Cλ defined on singular limit ordinals λ such that (i) E ⋂ μ is Mahlo in μ for all regular > ω; (ii) Cλ is closed and unbounded in λ; (iii) if γ < is a limit point of Cλ, then γ is singular, γ ∉ E and Cγ = γ ⋂ Cλ. For each infinite cardinal κ: (J2,κ) There is a set E ⊂ κ+ and a sequence Cλ(Lim(λ), λ < κ+) such that (i) E is Mahlo in κ+; (ii) Cλ is closed and unbounded in λ; (iii) if cf(λ) < κ, then card Cλ < κ; (iv) if γ < λ is a limit point of Cλ then γ ∉ E and Cγ = ϣ ⋂ Cλ.

We investigate relativized versions of the open question of whether every language accepted nondeterministically in polynomial time can be recognized deterministically in polynomial time. For any set X, let $\mathcal{P}^X (\text{resp. }\mathcal{NP}^X )$ be the class of languages accepted in polynomial time by deterministic (resp. nondeterministic) query machines with oracle X. We construct a recursive set A such that $\mathcal{P}^A = \mathcal{NP}^A $. On the other hand, we construct a recursive set B such that $\mathcal{P}^B \ne \mathcal{NP}^B $. Oracles X are constructed to realize all consistent set inclusion relations between the relativized classes $\mathcal{P}^X $, $\mathcal{NP}^X $, and co $\mathcal{NP}^X $, the family of complements of languages in $\mathcal{NP}^X $. Several related open problems are described.