2
votes
1answer
77 views

$\textbf{Q}$ fails to prove some correct $\forall$-rudimentary sentence

Show that the existence of a semirecursive set that is not recursive implies that any consistent, axiomatizable extension of Q fails to prove some correct $\forall$-rudimentary sentence. I ...
1
vote
1answer
43 views

A Question About Tennebaum's Theorem?

Tennenbaum's theorem proves there are no countable recursive nonstandard models of Peano arithmetic. It is a proof by contradiction. If our countable, nonstandard model is recursive, then, given a ...
-1
votes
0answers
39 views

Number of Recursively Inseparable Sets [closed]

Is it true there are an uncountable number of pairs of recursively inseparable sets of standard natural numbers? Edit to refine question: Is there a uncountable set of non-recursive sets of ...
2
votes
0answers
56 views

Ackermann function is not primitive recursive

The function of the Ackermann function is defined as $$ A_{0}(y)= y+1$$ $$ A_{x+1}(0)= A_{x}(1)$$ $$ A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$ I want to show that the function of ackermann is primitive ...
0
votes
0answers
62 views

A is recursive iff A is the range of an increasing function which is recursive

Working a problem stated in Enderton, but stated better and apparently stronger in Soare. All citations hereon are for Soare (1987). Would appreciate help on the proof. I know there has to be a more ...
1
vote
1answer
32 views

Kolmogorov (Kolmogoroff- ) Complexity of infinite sequences, Request for Proof

Let $\xi \in X^{\omega}$ be an infinite sequence and denote by $\xi[1\ldots n]$ its length $n$ initial segment. Then (due to Martin-Löf) the following holds: For every $\xi \in X^{\omega}$ there ...
1
vote
1answer
29 views

Direct proof that $K \leq_\mathrm{T} Rec$

Soare's Recursively Enumerable Sets and Degrees (1987) shows that $Rec = \left\{ e : W_e \text{ is recursive} \right\}$ is $\Sigma^0_3$-complete via its relationship to other index sets, namely $Cof$ ...
0
votes
1answer
31 views

Kolmogorov (Kolmogoroff-) Complexity, Contradiction with Invariance Theorem.

Fix some programming languages $S$ which is rich enough such that one can write interpreters for $S$ in $S$. Define $$ K(w) := \mbox{length of a shortest program producing $w$}. $$ Now fix some ...
7
votes
1answer
81 views

Proof-theoretic characterization of the primitive recursive functions?

The total recursive functions are exactly those number-theoretic functions that can be represented by a $\Sigma_1$ formula of first-order arithmetic. Is there a similar characterization of the ...
1
vote
3answers
63 views

How does one generally use partial function in logical statements?

How does one generally use partial function in logical statements? How it's done in practice? Specifically, let $M$ by a Turing machine, $f_M:\{0,1\}^*\to\{0,1\}$ the characteristic function which ...
1
vote
1answer
62 views

Problem from Cutland's Computability: 3.2. problem 3

The problem goes as follows. Let f: N --> N, such that f is partial, N is the natural numbers, and let m $\in$ N. Construct a non-computable function g such that g(x) = f(x) for x$\le$m. Proof: By ...
0
votes
1answer
56 views

Complexity of Recursively Inseparable Sets

I am interested in examples of recursively inseparable sets. A standard example is the set of positive integers encoding a Turing machine that halts in an odd number of steps on blank input versus ...
1
vote
1answer
47 views

Non-computable c.e. sets are Kurtz random

I'm trying to directly show that non-computable c.e. sets are Kurtz random, without using the concept of genericity, but to little success. I assume by way of contradiction that $\emptyset'$ (for ...
14
votes
3answers
237 views

Mathematical Notation and its importance

You can see how mathematical notation evolved during the last centuries here. I think everyone here knows that a bad notation can change an otherwise elementar problem into a difficult problem. Just ...
5
votes
0answers
102 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 ...
0
votes
1answer
33 views

Are these sets recursive, r.e. or none

Are the sets a) $\{x | \exists y \phi_x(y) = 0\}$ b) $\{x | \phi_x(5) \uparrow \land x \leq 5\}$ recursive, recursively enumerable (r.e.) or none of them? Please explain your solution. $\phi_x$ ...
2
votes
2answers
64 views

Can we find a formula defining a recursively enumerable set?

By Post's Theorem we know that a set $A\subseteq\mathbf{N}$ is recursively enumerable iff it is definable by a $\Sigma_1$-formula, i.e. there exists a $\Sigma_1$-formula $\varphi(x)$ with $x$ free ...
3
votes
1answer
58 views

Computably enumerable sets are not algorithmically random

I am informed that no computably enumerable sets are algorithmically random. I tried to show it by constructing an ML test, and looked up the proof in Downey & Hirschfeldt, but in vain. I would ...
2
votes
1answer
43 views

Steps for applying Rice's theorem to any sets

I know that this set: $$\{i\ |\ \ \phi_i(n) \text{ converges } \}$$ is not recursive and that this can be shown by Rice's theorem. But everywhere I look i just found that it's not recursive ...
0
votes
1answer
79 views

Proving sets to be (not) recursive or r.e.

I am stuck proving the following sets to be recursive or recursive enumerable (or none of the both). first set: $$\{i\ |\ \exists n, \phi_i(n) \text{ converges and } \phi_i(n+1) \text{ converges}\}$$ ...
3
votes
3answers
105 views

Is it possible to create a string with known Kolmogorov Complexity?

I wish to compare compressors using strings with known Kolmogorov Complexity, but I haven't got the theoretical background and tools to understand how to do that. I'm just starting in this area and ...
1
vote
2answers
50 views

The universal turing relation

I'm just starting to learn computability. Some treatments of the subject use a relation they call $T$, which I think is called the universal recursive relation. It's defined something like this ...
3
votes
1answer
186 views

Are there more true statements than false ones?

Let us enumerate all statements of PA or ZFC by length, upto n characters, then in the limit as $n\rightarrow\infty$, what proportion of statements are provably true, provably false, or independent? ...
4
votes
2answers
131 views

About theorem's proof length in propositional calculus

In PC(propositional calculus) system, how long will a formula's proof be? That is to say if there exists a computable function $f$ such that for any formula $A$, if $\vdash_{\mathrm{PC}}A$ then $A$ ...
3
votes
1answer
61 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, ...
2
votes
0answers
65 views

Check that constructed recursive function proves that set is recursive.

Let $\forall\exists$-formula be any formula that looks like $\forall x_1...\forall x_m$$\exists y_1...\exists y_n \phi$, where $x_1...x_m, y_1...y_n$ - variables, $m,n \ge 0$ , $\phi$ - unquantified. ...
3
votes
0answers
49 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
2
votes
1answer
54 views

Effective Enumeration of Set when Membership is Semi-Decidable

I have a set $S$, where $x \in S$ is semidecidable, i.e. there is a function $f(\cdot)$ that returns 1 in finite time if $x \in S$ but will not halt if $x \notin S$*. I also have an effective ...
2
votes
1answer
64 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 ...
0
votes
1answer
60 views

Is DFA (Deterministic Finite Automata) a kind of predicate?

When I read a book on computation theory, I found a interesting thing: A Language L was defined by a DFA(Deterministic Finite Automata) like this, L = {$\omega$ | the last input of $\omega$ causes ...
2
votes
1answer
82 views

Is the Church-Kleene Ordinal describable with Kleene's $O$?

Kleene's $O$ is an ordinal notation system that uses certain natural numbers to represent transfinite ordinals. It is a recursive notation system (although it's not decidable whether a number ...
4
votes
1answer
71 views

Is ordinal analysis a non-recursive project?

A recursive ordinal is an ordinal that is the order-type for some recursive relation (i.e. a recursive well-ordering). We can represent recursive ordinals as natural numbers using Kleene's $O$, an ...
0
votes
0answers
93 views

Definitions of different kinds of recursive reducability.

So this is just a definition check. In recursion theory we have many kinds of reduction, according to my notes we have $\leq_1,\leq_m,\leq_{tt},\leq_{wtt},\leq_{TT},\leq_{T}$. Now I can't for the ...
0
votes
1answer
56 views

Enumerating relations that are true infinitely often

Let us concentrate on relations on natural numbers. Is it possible to enumerate all computable unary relations that are true infinitely often? I would guess no but I can't see a direct way to prove ...
5
votes
3answers
495 views

Prove that transcendental numbers exist: Are there less paniful ways of doing it?

I've found this exercise on Boolos' Logic and Computability: A real number $x$ is called algebraic if it is a solution to some equation of the form: $$c_{\small d}x^{\small ...
2
votes
1answer
43 views

A diophantine program for a basic For Loop

By Matiyasevich, every computable function has a diophantine representation. I am wondering if there is a general way to represent a simple iterative for loop. Specifically: Let $f(x)$ be any ...
4
votes
1answer
95 views

Decidable & Recursive predicates

Let $C$ be a decidable predicate in the language of arithmetic HA, that is $$ \vdash (\forall \underline x)\: C(x) \vee \neg C(x).$$ $C$ is recursive if there exists a computable characteristic ...
3
votes
1answer
80 views

Looking for counterexamples where the output of a computable function always has a computably checkable property, but PA cannot prove this

Suppose we have a computable function $f$, say over the naturals, and a decidable set $S$ of naturals, such that $f(x) \in S$ for all $x$. In this case, for any specific $x$, there is some specific ...
1
vote
1answer
67 views

Why SKI when SK is complete

Why people talk about SKI calculus when S and K combinators can be used to create any other combinator including I?
0
votes
0answers
47 views

A diophantine definition of the Kleene star

Let $f(x \, | \, y_1, \dots, y_n)$ be a Diophantine polynomial that generates the Diophantine set $F$. By Matiyasevich, the set $F^*$ (Kleene star of $F$) is also Diophantine. My question: how can ...
5
votes
2answers
119 views

Running programs in nonstandard models of PA

I came across the following problem in several places, to paraphrase: Let $T$ be a recursively axiomatizable, consistent extension of PA. Then there exists some $e$ such that the $e'$th program ...
2
votes
2answers
80 views

Theory vs. Deductive Theory

Looking through some notes on model and computability theory, I noticed that the definition of the term 'theory' changed between them; in particular, the model theory (based on Hodges' text) defined a ...
0
votes
2answers
132 views

Universal Turing Machine with an Oracle

(Note: For convenience, I'm phrasing this in terms of computer programs rather than Turing machines.) Consider computer program P which does the following: It asks the user to enter the code of a ...
2
votes
1answer
86 views

A few basic questions about the arithmetical hierarchy, mostly about terminology.

I was reading about the arithmetical hierarchy, and I have a few questions, mostly notational. For completeness, here's the definition given over at Wikipedia. The classifications $\Sigma_n$ and ...
1
vote
1answer
55 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 ...
6
votes
1answer
79 views

Ackermann function and $f_\omega$

The Wikipedia page of Ackermann function states that Ackermann function is "roughly comparable" to $f_\omega$ in fast-growing hierarchy. Is there some standard way to make the "roughly comparable" ...
3
votes
1answer
141 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 ...
0
votes
1answer
64 views

Let F be a function from $N ^{n} \longrightarrow N$. Show that if F is computable/ recursive then its graph is computable

Let F be a function from $N ^{n} \longrightarrow N$. Show that if F is computable then its graph is computable. According to the definition of computable/recursive I am looking at, a relation is ...
1
vote
1answer
68 views

Density of PA degrees

As suggested by Carl Mummert, I will ask a separate question (this question was posted but then deleted). The following letters $a, b, e,\ldots$ denote Turing degrees. We say $a\gg b$ if there exists ...
4
votes
1answer
145 views

How to prove primitive recursive functions are definable in Peano Arithmetic?

Background: I'm working on a talk that presents Godel's first Incompleteness Theorem from a computability-theoretic perspective. The idea is to show that the first incompleteness theorem follows from ...