# Tagged Questions

30 views

### Maximum number of compressed RLE strings under any given length

Given a random string of length L (for instance, "01100010000101" of length "14"), and knowing that this string is only numerical, how many other strings under the form Y one can achieve by ...
85 views

### Distinguishing sets according to more fine-grained notions than cardinality.

I'm interested in distinguishing sets according to more fine-grained notions than cardinality. Now I don't know a thing about computability theory, but it seems to me that considering sets up to ...
134 views

### Consistency strength of Turing measurability

This is probably well-known to recursion theorists, but as google didn't help me, I'll ask it here. Convention: All sets of reals in the following discussion are assumed to be closed under Turing ...
117 views

### Elementary references on Robinson Arithmetic, Prim. Recursive fns etc.

I'm in the middle of revising my freely available and much-downloaded introductory notes Gödel Without (Too Many) Tears. (They are a sort of cut down version of part of my Gödel book, and I'm ...
64 views

### Construction of a Kurtz random sequence that's not Martin-Löf random

How can one construct a Kurtz random sequence that's not Martin-Löf random? I'm also interested in the paper that included the first of such constructions. I suspect it was in Kurtz's dissertation, ...
36 views

### quick guide to understand theory of computation

Can someone tell me some quick guides in understanding theory of computation. I know this is not the place to ask such question
100 views

### Books about Turing machines and undecidability

I need help with finding literature about Turing machine and undecidability. First book I was suggested is Introduction to Automata Theory, Languages, and Computation by Hopcroft, Motwani and Ullman. ...
50 views

### Eager vs. lazy interpretation of recursive functions

One of the ways of defining the set of recursive functions is to define first a language $L$ by induction in the following way: $\mathsf{Z}^1 \in L$; $\mathsf{S}^1 \in L$; $\mathsf{P}^n_k \in L$ for ...
68 views

### Genericity and category

This paper by Ambos-Spies and Mayordomo on the theory of algorithmic randomness introduces the notion of genericity saying that it is based on Baire category while the usual notion of randomness is ...
45 views

### Why is positional number system natural?

In the theory of computation, one mainly deals with maps $\Sigma^*\rightarrow\Sigma^*$. To discuss computation on other sets $X$ than $\Sigma^*$, one fixes a representation ...
57 views

### Computability text emphasizing the arithmetical point of view?

I learned here that A set is recursively enumerable if and only if it is at level $\Sigma^0_1$ of the arithmetical hierarchy. Is there an introductory text in computability theory that takes ...
168 views

### Random reals and Martin-Löf randomness

My questions are about the relationship between the following notions of randomness: A real $r$ is random over the model $M$ if $r\notin B$ for every null Borel set $B$ coded in $M$. A real $r$ is ...
163 views

### Reference on standard types

This question is about what I presume is a basic construction in type theory. The finite types are defined as follows: 0 is a finite type; if $\sigma, \tau$ are finite types, then so is ...
208 views

### Book on lambda calculus logic and type theory

Can someone recommend me a book for self study which will cover topics of logic, lambda calculus and type theory. I know about "Computability and Logic" written by Bolos but it describe recursive ...
135 views

### Books on computational complexity

Can anyone recommend a good book on the subjects of computability and computational complexity? What are the de facto standard texts (say, for graduate students) in this area? I've heard a thing or ...
110 views

### What questions become answerable/computable given an uncountable character set?

Having reached the concluding portion of my first course in real analysis, one subject that I feel was not adequately addressed was the issue of cardinalities. This is a subject I was interested in ...
322 views

### What are $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$?

Sometimes reading on wikipedia or in this site (and in very different context like topology, arithmetic and logic) I have found these symbols $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$. They are ...
71 views

### Sources on a category of ordinals

all I'm reading old papers on generalized recursion theory, and I've run across a paper by Van de Wiele ("Recursive dilators and generalized recursions") that 'lives in' the category ON, whose ...
145 views

### Members of (lightface) Borel sets

I'm fairly certain this question has a very simple answer, and that I've learned it before; I just can't seem to remember it. Suppose I have a nonempty lightface Borel set $X\subseteq 2^\omega$. What ...
95 views

### Space : Kolmogorov complexity :: time and space : ___?

It's well-known that the Kolmogorov complexity is uncomputable, essentially because of the halting problem: you can list all programs of length less than one known to generate a given string, but you ...
313 views

### Good introductory books on primitive recursive functions

I wondered if anyone could recommend any good introductory books on primitive recursive functions. I'm currently working through a Number Theory and Mathematical Logic module, and I'm finding it ...
238 views

### Is there a function that only generates primes?

The title sums it up: does there exist a "nice" injective function $f(n)$ such that $f(n)\in\mathbb P$ for all $n\in\mathbb N$? I'm having difficulty specifying exactly what I want "nice" to mean, ...
154 views

### Projecting onto (lightface) Borel sets

Suppose $A \subseteq \omega^{\omega} \times \omega^{\omega}$ is Borel. If we project $A$ onto $\omega^\omega$, we get a $\mathbf{\Sigma^{1}_{1}}$ set $\{y: \exists x (y,x) \in A\}$. What if we project ...
168 views

### Proof of a Theorem in Gao's 'Invariant Descriptive Set Theory'

Theorem 1.7.5 on p.35 of Gao's Invariant Descriptive Set Theory reads Theorem 1.7.5 (Kleene) If $A\subseteq X \times \omega^{\omega}$ is $\Pi^{1}_{1}$ and x \in B \Longleftrightarrow \exists y ...
176 views

### Formal statement of theorem about perfect numbers?

I cannot seem to find the formal statement of the theorem if there are infinite perfect numbers in Wikipedia or online. I searched this site but the closest is the generalization of perfect numbers ...
293 views

### Does the $k$th forward difference of Radó's $\Sigma$ eventually dominate every computable function?

Let $\Sigma$ be Radó's Busy Beaver function, and let $\Delta[\Sigma]$ denote the forward difference of $\Sigma$, such that $\Delta[\Sigma] \ (n) = \Sigma(n+1) - \Sigma(n)$ for all $n \in \mathbb{N}$. ...
190 views

### Complexity of the set of computable ordinals

According to http://en.wikipedia.org/wiki/Analytical_hierarchy The set of all natural numbers which are indices of computable ordinals is a $\Pi^1_1$ set which is not $\Sigma^1_1$. However, "the ...