All Questions
Tagged with computability-theory reference-request
93 questions
5
votes
0
answers
158
views
If $\omega_1$ is not inaccessible in $L$, how hard can it be to find a non-measurable $\Sigma^1_3$ set of reals?
In his wonderfully titled paper Can you take Solovay's inaccessible away? Shelah showed that if every $\mathbf{\Sigma}^1_3$ set of reals is Lebesgue measurable, then $\omega_1$ is an inaccessible ...
- 12.4k
5
votes
1
answer
202
views
Turing degrees of lim infs of computable functions
The limit lemma gives a natural characterisation of functions $f : \mathbb{N} \to 2$ with Turing degree below $0'$: they are precisely those that can be written as $f(n) = \lim_k f_k(n)$ where $f_k : \...
- 4,378
3
votes
0
answers
152
views
What is known about the word problem on free algebraic models?
Consider the fragment of first-order logic with equality and universal quantification as the only logical symbols; we call this logic the logic of universal algebra. I am interested in languages $\...
4
votes
0
answers
149
views
Computable subsets of non-standard models of arithmetic
By Tennenbaum's theorem, there exists no computable non-standard model of $\mathsf{PA}$. That is, for any nonstandard model $M$, we cannot define an encoding of the integers $x\in M$ such that $+_M$, $...
- 291
5
votes
1
answer
560
views
Hilbert's and Gödel's expanded definition of "Recursive Function"
There is a very interesting comment in this post:
I must also make one terminological caveat: Hilbert, and later Godel, used the phrase "recursive function" in a way very different from the ...
- 4,897
2
votes
0
answers
151
views
Notes on Lachlan's monster
I have been trying to look for a reference I have seen in a paper called "R. Soare, Notes on Lachlan’s Monster Theorem" without success. I was wondering if anyone had a digital copy of them ...
- 893
4
votes
0
answers
182
views
Some questions on a paper of Gerald Sacks
I've been reading Sacks' Countable admissible ordinals and hyperdegrees as I'm interested in Theorem 5.3 of the paper:
Let $M$ be a countable standard model of $\mathsf{ZF}$ and $V=L$. Suppose $\...
- 2,286
2
votes
0
answers
96
views
Can one extend higher randomness theory to the entire analytical hierarchy under certain large cardinal assumptions?
In the "Recursion Theory" book by C.T Chong, Liang Yu, towards the end of the book they list a few "open" research areas connected to higher computability theory. One such ...
- 893
6
votes
1
answer
201
views
Reference request: generalized randomness
There is a plethora of notions of randomness for Cantor space ($\phantom{}^\omega 2$) (Schnorr randomness, Martin-Löf randomness, weak 2-randomness, the various forms of higher randomness such as $\...
- 1,155
1
vote
0
answers
75
views
Any concrete survey on infinite and finite injury method?
I hope to have a historic outline of infinite and finite injury method and their main technical introdution.Any concrete survey on infinite and finite injury method recommended?
- 3,094
4
votes
1
answer
162
views
Existence of an inseparable minimal pair
An inseparable minimal pair is a pair of sets $A, B \subseteq \mathbb{N}$ which are
inseparable: there is no computable $C \subseteq \mathbb{N}$ such that $A \subseteq C$ and $B \subseteq \mathbb{N} \...
- 48.8k
2
votes
0
answers
118
views
Details on partial oracle computability in Ganov
I'm currently glancing at a couple papers by V. A. Ganov (Recursion on generalized computable ordinals and A generalized constructable continuum), and I'm running into some basic issues. Ganov ...
- 21.2k
3
votes
0
answers
336
views
Different definitions of 'countable set'
There are a number of different definitions of 'countable set', all equivalent given a strong enough (classical) system. The obvious ones (injection to $\mathbb{N}$, bijection to $\mathbb{N}$, ...
- 4,359
5
votes
0
answers
291
views
What is known about when regularity properties only hold for partial boldface pointclasses?
Apologies in advance for a rather vague and open-ended question.
Results about regularity properties of the projective pointclasses tend to have a wholesale flavor. By this I mean one tends to be ...
4
votes
1
answer
439
views
Alternative proof of Tennenbaum's theorem
The standard proof of Tennenbaums's theorem uses the existence of recursively enumerable inseparable sets and is presented e.g. in Kaye [1, 2], Smith [3].
In the following, $\mathcal{M}$ will always ...
- 211
6
votes
1
answer
421
views
Computing the complex roots of a monic polynomial
The map from monic complex polynomials to the unordered tuples of their roots (each appearing according to its multiplicity) is computable. This seems to have been known for a long time, and with ...
- 4,717
0
votes
0
answers
144
views
Where does intuitionistic predicate logic live in the arithmetical hierarchy?
I started reading Plisko's papers on arithmetic complexity on the arithmetic complexity of constructive logic (see for example here or here). In this context, I started wondering about the following ...
- 183
14
votes
1
answer
1k
views
Descriptive set theory for computer scientists?
It seems to me that there are scattered references of deep relationships between descriptive set theory and computability theory. For one, the relationship between the Borel hierarchy and the ...
- 1,221
4
votes
0
answers
431
views
How can I prove that primitive recursion “preserves” representability in Peano Arithmetic?
I'm working on my thesis about Gödel's Incompleteness Theorems, and at some point I need to prove that the $\textsf{PA}$ system is able to represent all the recursive functions.
By recursive function ...
- 49
6
votes
1
answer
331
views
What are these recursively defined sequences called?
Let $F(x,y)$ be a function of two variables, defined for all positive integers $x$ and $y$. Define a sequence $a_n$ recursively by setting $a_1 = 1$ and
$$a_n = \sum_{k=1}^{n-1} F(k, n-k) \cdot a_k ...
- 13.3k
3
votes
0
answers
122
views
Post correspondence problem: Busy beaver variant
The Post correspondence problem (Wikipedia link) is to decide for $k$ pairs of strings $$(a_1,b_1), (a_2, b_2), ..., (a_k,b_k),$$ if there exists a finite sequence of numbers $c_j, 0\le j\le j_\max $ ...
- 2,811
0
votes
0
answers
56
views
Reference about Relation between Probabilistic Turing Machine and Turing Machine of every hierarchy
What are the relation between Probabilistic Turing Machine and Turing Machine of every hierarchy, for instance, are the Probabilistic PDA and NPDA equivalent? the Probabilistic LBA and LBA equivalent?...
- 3,094
11
votes
2
answers
920
views
Where did this presentation of Gödel's theorem appear?
This question was asked and bountied at MSE, with no response.
Many years ago I ran into the following proof of Gödel's first incompleteness theorem
(here $T$ is an "appropriate" theory of ...
- 21.2k
5
votes
0
answers
301
views
The expressiveness of functions computable on trees
Motivation:
Let's define a function computable on a $k$-ary tree as a function composed with simpler computable functions defined at each node such that a function of this kind defined on a binary ...
- 3,871
5
votes
0
answers
196
views
A slight extension of Sacks theorem
Sacks proves the following theorem first.
Theorem 1: If $\alpha$ is a countable admissible ordinal, then there is a real $x$ so that $\omega_1^x=\alpha$.
Anyone knows who proves the following ...
- 4,201
18
votes
2
answers
708
views
Is Post's tag system solved?
Has the 3-tag system investigated by Emil Post $(0\to00, 1\to1101)$ been solved? Is there a decision algorithm to determine which starting strings terminate, which end up in a cycle, and which (if any)...
- 2,811
113
votes
11
answers
18k
views
On mathematical arguments against Quantum computing
Quantum computing is a very active and rapidly expanding field of research. Many companies and research institutes are spending a lot on this futuristic and potentially game-changing technology. Some ...
2
votes
1
answer
74
views
Name for "partially complete" invariants in classification problems?
For any equivalence $\sim$ on some collection of objects $C$ consider the problem of trying to determine if two arbitrary objects $x$ and $y$ in $C$ are equivalent i.e. if $x\sim y$ now by definition ...
- 2,506
9
votes
0
answers
305
views
Moschovakis' discovery of E-recursion
E-recursion is a notion of generalized computability theory which seeks to extend computations to allow arbitrary sets as inputs. In contrast with e.g. $\alpha$-recursion, it disallows unbounded ...
- 21.2k
4
votes
2
answers
591
views
Connection between countable ordinals and Turing degrees
$\omega^{CK}_1$ is the supremum of all the recursive ordinals, where an ordinal $\alpha$ is recursive if there is a computable ordering of a subset of the naturals with order type $\alpha$.
For a ...
- 6,353
0
votes
0
answers
94
views
Name and theory of multi-valued functions $F:\mathbb{N}^k \rightarrow \mathbb{N}^l$
In computability theory there are considered mostly single-valued functions $f:\mathbb{N}^k \rightarrow \mathbb{N}$. (Let $\mathbb{N}$ be a placeholder for $\mathbb{N}$ or any initial segment $[0,n]$ ...
- 9,720
-1
votes
1
answer
417
views
Conversion of logic formula into algebraic formula
We know formula of boolean algebra in canonical disjunctive normal form has or may be converted to Zhegalkin polynomial.
Is there any approach to convert first order formula into algebraic function ...
- 3,094
0
votes
0
answers
234
views
whether the quotient of continued fraction of algebraic irrational number is bounded or not is similar or equivalent to Collatz conjecture?
I vaguely recall that whether the quotient of continued fraction of algebraic irrational number is bounded or not is similar or equivalent to Collatz conjecture, could any one give the reference? or ...
- 3,094
3
votes
2
answers
778
views
Is any Cauchy sequence for completion of rational semicomputable?
For the definition of a semicomputable real, see An Introduction to Kolmogorov Complexity and its Applications by Li and Vitanyi (1997). In fact, it is not true that every Cauchy sequence for ...
- 3,094
5
votes
1
answer
277
views
Program analysis for Turing machines
What is considered the state-of-the-art on program analysis (static and dynamic) for Turing machines? What references can I consult for this problem?
I am thinking of things like determining whether ...
- 2,203
6
votes
1
answer
839
views
Rice's theorem in type theory
From the formula
$$\forall f\colon A\to A\,\exists x\colon A\,(f(x)=x)$$
we can get the scheme
$$\forall x\colon A\,(\phi(x)\vee\neg\phi(x))\Rightarrow\forall x\colon A\,\phi(x)\vee\forall x\colon A\,\...
4
votes
2
answers
489
views
Mapping between Notations
$\DeclareMathOperator{\address}{address}$
As in my other question, it is assumed that the (total) function describing a given notation is denoted as $\address:p \rightarrow \Bbb{N}$ and assumed to be ...
- 881
1
vote
1
answer
308
views
Halting problem about subclass of Turing Machines
As we know, that the halting problem of Turing machines is undecidable. given some restriction on $TM$ set of Turing Machines, we get a subclass $TM_s$, halting problem of what subclasses of $TM$ can ...
- 3,094
4
votes
2
answers
1k
views
Matiyasevich's theorem and Gödel's first incompleteness theorem
In the Wikipedia article Diophantine set there is a section entitled "Further applications" in regards to Matiyasevich's theorem and it states:
Matiyasevich's theorem has since been used to ...
- 482
6
votes
1
answer
433
views
Reference request: a version of $\Sigma^1_1$ bounding for structures
There's a (fairly basic) fact I want to use in a paper I'm writing; it's not entirely trivial, so I don't feel comfortable just stating the result and moving on, but I don't have a citation for it. ...
- 21.2k
2
votes
1
answer
287
views
A "Folkloric" Result for Classes of Computable Functions
In Feferman's paper (located here (pg. 2 of the PDF)), he begins to outline various methods used for attacking the problem of classifying the computable functions by means of hierarchies. In ...
- 314
8
votes
1
answer
1k
views
Recursion theory from the standoint of category theory
It is (I believe) a very easy exercise to prove that the general recursive functions over the natural number object $N$ form a category. But what sort of category is it? From the fact that one can ...
- 6,132
9
votes
2
answers
2k
views
Is simply typed lambda calculus with fixed-point combinator Turing-complete?
There are many sources cite that simply typed lambda calculus extended with fixed-point combinator is Turing complete. For example, Does there exist a Turing complete typed lambda calculus? or the ...
- 101
5
votes
0
answers
329
views
Could there be something like a Grzegorczyk hierarchy in Analysis?
My most prevalent interest in mathematics has always been hyper-operators. I first learned about them when I was in highschool, and quite frankly, they amazed and dazzled me. For those who've yet to ...
user78249
8
votes
2
answers
518
views
History of forcing over admissible sets
In his paper "Forcing in admissible sets", Ershov writes
In unpublished lectures given at Novosibirsk State University in 1976-1977 on the theory of admissible sets, the author
showed that it is ...
- 21.2k
7
votes
1
answer
181
views
Lachlan on topology for priority arguments
There is a set of notes by Lachlan from 1973 on casting priority arguments in topological language; references to these notes are few and far between, but one source refers to them as "Topology for ...
- 21.2k
3
votes
0
answers
203
views
Class forcing over E-closed sets
Short version: does anyone know of any good sources on class-forcing over E-closed, non-admissible sets?
Longer version: A problem I'm working on has reached an interesting conclusion - I've managed ...
- 21.2k
8
votes
1
answer
432
views
Which reals are "hyperarithmetic modulo ordinals"?
The context for this question is the theory ZFC + a measurable cardinal, although answers not in this context would also be interesting to me.
In a project I'm working on, the following class of ...
- 21.2k
3
votes
1
answer
274
views
What is the extension of the truth-table degrees to Baire Space called?
Recall that for sets $A, B \in 2^\omega$ that we say $A \leq_{tt} B$ if there is a total Turing functional $F \colon 2^\omega \to 2^\omega$ such that $F(B)=A$. This is called truth-table reducibility....
- 6,287
7
votes
2
answers
1k
views
Complexity of Turing Machine behavior
If one looks at the code for a Turing Machine (TM) with
$q$ states and, let's say, $2$ symbols, they all look
pretty much the same:
A list of $5$-tuples:
$$
< state, symbol{-}read, symbol{-}to{-}...
- 151k