Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).

learn more… | top users | synonyms (1)

37
votes
0answers
826 views

What properties of busy beaver numbers are computable?

The busy beaver function $\text{BB}(n)$ describes the maximum number of steps that an $n$-state Turing machine can execute before it halts (assuming it halts at all). It is not a computable function ...
9
votes
0answers
148 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 ...
6
votes
0answers
33 views

An Undecidable but not Universal Turing Machine?

I have seen many examples of universal Turing machines, all of which are undecidable due to the undecidability of the halting problem. I have also seen proofs that certain really small Turing ...
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 ...
5
votes
0answers
121 views

How is the Kleene normal form theorem for $\Sigma^1_1$ relations proved in RCA0?

All of the following concerns Simpson's Subsystems of Second Order Arithmetic (2nd ed.). In the notes subsequent to lemmas VII.1.6 and VII.1.7 (pp. 245–246), Simpson remarks that both lemmas are ...
4
votes
0answers
227 views

algorithm for solving diagonal quadratic equations over real or complex numbers

I found the following statement in the paper http://www.math.uni-bonn.de/~saxena/papers/cubic-forms.pdf (page 22, in the middle): For $\mathbb F\in\{\mathbb R, \mathbb C\}$ and $b, a_i\in\mathbb ...
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 ...
3
votes
0answers
103 views

Simplifying Relations in a Group

Let $K$ be the group generated by four elements $x_1,\cdots,x_4$ with relations that any simple commutator with repeated generator is trivial; for example, $[[x_2,[x_1,x_3]],x_3]=1$. As I have asked ...
3
votes
0answers
169 views

How to derive Church-Kleene ordinal

Crossing-out: (How does one prove the existence of Church-Kleene ordinal? Also, why is it labeled as $\omega_1^{CK}$? And why is it first ordinal not hyperarithmetical, and is the first admissible ...
3
votes
0answers
57 views

Is the measure induced by the Mandelbrot set computable on rational rectangles?

Is there a computable function that, given a positive rational number $\epsilon$ and a rectangle with rational corners $A$ returns a number $f(A,\epsilon)$ such that $|\mu(A \cap ...
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 ...
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. ...
2
votes
0answers
47 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 ...
2
votes
0answers
56 views

Acceptable numbering of partial computable functions required to be one variable?

Soare in a yet unpublished textbook (I happened to be in a class taught by one of his former graduate students where we were field-testing a rough draft of his new textbook) Computability Theory and ...
2
votes
0answers
77 views

Prove that $\{(x,y): W_x\text{ and }W_y\text{ are recursively separable}\}$ is $\Sigma_3$-complete

Prove that $\{(x,y): W_x\text{ and }W_y\text{ are recursively separable}\}$ is $\Sigma_3$-complete This is a question from Soare's Recursively Enumerable Sets and Degrees. I have little idea how ...
2
votes
0answers
140 views

How to show Simp. and Creat. are $\Sigma^0_2$-Hard

Let Simp={$e:W_e$ is simple} and Creat={$e:W_e$ is creative} I'm having troubles showing these sets are $\Sigma^0_2$-Hard, ie that any $\Sigma^0_2$ set can be many-one reduced to them. I've already ...
2
votes
0answers
99 views

Unsolvability Degree in Turing's Proof 1

I have read that there is some debate over the exact origin of the Halting argument, which begins with Kleene and Davis in the 1950s [Copeland 2004]. Motivated by this I want to clarify the Degree of ...
2
votes
0answers
106 views

constructive ordinal and $\Delta^1_1$ predicate

Everything I know on this subject comes from Sacks book : "Higher recursion theory" Let $\mathcal{O^Y}$ be the set of codes for ordinals constructive in $Y$. We should have the result that $A ...
2
votes
0answers
183 views

Further question on “uncountable” Turing Machine

Having read An "uncountable" Turing Machine? I have further questions that I don't believe it addressed. (I'm a programmer, not a mathematician so I apologize if this is stupid or the ...
1
vote
0answers
78 views

Oracle Turing machine - $E_{\text{TM}}$ and $PCP$.

$$E_{\text{TM}}=\{\langle M\rangle|M\text{ is a TM and $L(M)=\emptyset$}\}.$$ $E_{\text{TM}}$ is undecidable $$PCP=\{\langle P\rangle|P\text{ is an instance of the Post Correspondence Problem with a ...
1
vote
0answers
15 views

The $k$-th term in the graded lexicographical order is recursive

I recently constructed a proof that a computable universal function exists for the class of polynomials of $n$-variables. To this end, I adopted the graded lexicographical monomial order. However, I ...
1
vote
0answers
54 views

Showing particular language is NP-complete

How is FLO NP-complete? Let G be a social network where vertices correspond to people and edges are relationships between people (undirected). Some pairs of people (who are friends) get married. We ...
1
vote
0answers
58 views

Primitive recursive and Turing machines

Can someone give me a hint or the start of a possible proof for the following theorem: A function $f: \mathbb{N}^r \rightarrow \mathbb{N}$ is primitive recursive if and only if there is a ...
1
vote
0answers
8 views

Is the language that consists of machine configurations whose language is a subset of even palindromes semi-decidable?

Let $PAL = \{ww^R\ | w\in\{0,1\}^*\}$. Then let $A = \{\langle M\rangle \ | \textit{M is a Turing Machine and } L(M)\subseteq PAL\}$ Is A semi-decidable (Turing recognizable or recursively ...
1
vote
0answers
39 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 ...
1
vote
0answers
45 views

Systematic way of creating the complement of a regular grammar?

Regular languages are closed under complement. And any regular language can be generated using a regular grammar. Is there a systematic way to create the rewrite rules for the complement of a regular ...
1
vote
0answers
36 views

Regular Functional Algorithms

A language is regular if it is accepted by a read-only Turing machine. I am curious about applying this model to functional problems rather than decision problems. Definition: A functional read-only ...
1
vote
0answers
65 views

Halting problem some properties

I am referring a little bit to my previous question on http://math.stackexchange.com/questions/392843/existence-universal-goto-programm-turing-machine#= Let $f(n)$ be the output of the universal ...
1
vote
0answers
27 views

Computational Complexity of the class of $\Delta_0$ functions (over $V_\omega$)

I would like to know where the class of functions whose graph is $\Delta_0$ (over $V_\omega$) fits in the computational complexity hierarchy. Also is there a nice notion of $\Delta_0$-reducibility ...
1
vote
0answers
65 views

Is discrete ultralogarithm harder than discrete logarithm?

Is computing $g^{xy} \bmod{s}$ from $g^{x} \bmod{s}$ and $g^{y} \bmod{s}$ easier harder or the same level of difficulty as computing $g\uparrow\uparrow(xy) \bmod s$ from from $g\uparrow\uparrow x$ ...
1
vote
0answers
72 views

Kolmogorov complexity and type of string

My question about well-known theorems: Theorem: Kolmogorov complexity is not a computable function. And, related, Chaitin's incompleteness theorem. ...
1
vote
0answers
32 views

Is it really true that $K(x|y) = K(x,y) - K(y)$?

Denote by $y^*$ the shortest program computing the string $y$. In the main textbook and various papers of Li & Vitanyi, I have seen the following statements. The first is well established: the ...
1
vote
0answers
150 views

Recurrence relation for the digits of the integer square root in binary

I was investigating a question on the Electrical Engineering Stack Exchange site, available here: ...
1
vote
0answers
74 views

What would an “algebraic axiomatization of the partial recursive functions” be?

Hartley Rogers in his "Theory of recursive functions and effective computability" (page 55 in the first edition) writes "What resemblance types are also isomorphism types? A final answer to this ...
1
vote
0answers
43 views

Computability of “isomorphism existence” between special cubic number fields

Let $a$ be a rational number such that the polynomial $P_a=X^3-X-a$ is irreducible, let $\alpha_{a}$ denote a root of $P_a$ and let ${\mathbb K}_a={\mathbb Q}(\alpha_{a})$. Similarly, let $b$ be a ...
0
votes
0answers
23 views

Not every polynomial in $\Bbb{Z}_p[x]$ can be factored, but can you do next best?

If $f \in R = \Bbb{Z}_p[x]$ is irreducible or doesn't have many factors then it could be hard to compute? Possibly, I'm not saying, but... any way, what if $f = h - g$ where $h, g$ are heavily ...
0
votes
0answers
39 views

Let A, B be infinite recursive sets with infinite complements. Show that A≡B.

My question is from Hartley Rogers' textbook (1967). Here's how I'm thinking about this so far. I know given infinite recursive sets A, B with infinite complements by theorem II of the current ...
0
votes
0answers
19 views

Prove that div(x,y) is primitive recursive (integer division

Prove that div(x,y) is primitive recursive (integer division). I tried thinking about it, I just don't know how to write it formally. it is kinda obvious that I should subtract y from x several times ...
0
votes
0answers
57 views

A Question Regarding Ordinal Turing Machines

Consider the following theorem of Koepke: 'A set x of ordinals is ordinal computable from a finite set of ordinal parameters if and only if it is an element of the constructible universe L". Taking ...
0
votes
0answers
74 views

When is a Decidable Set Decidable?

Can the same set be decidable in a strong theory and undecidable in a weaker theory? Some possible examples. Goodstein's theorem says every Goodstein sequence, $g(n)$, eventually terminates. ...
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 ...
0
votes
0answers
24 views

A turing machine which computes the same language as a “stay put” turing machine

Im not sure I really understand how stay put machines work. I know they are just like turing machines but with states. So they can "stay put". But what confuses me is when you define a FSA for a ...
0
votes
0answers
24 views

Polytime implementation of Discrete Log using primitive recursive functions

The primitive recursive functions are defined by Godel as: $z() = 0$ $s(x) = x+1$ $\pi_i(x_1, \dots, x_k) = x_i$ Plus closure under Composition: $h(x_1, \dots, x_m) = f(g_1(x_1, \dots, x_m), ...
0
votes
0answers
106 views

A turing machine for binary addition

How would I write a turing machine which has configurations which does 2 bit binary addition?
0
votes
0answers
47 views

Concatenation, reversal and sum are primitive recursive

Let $\mathbb N^*$ be the language of finite words with alphabet $\mathbb N$. Assume $k:\mathbb N^*\to\mathbb N$ is an effective coding. That is $k$ is a bijection whose length and member functions are ...
0
votes
0answers
34 views

Expressing total functions in a single equation

Suppose $f(x),g(x)$ are total functions. Give a single equation $h$ in terms of $f$ and $g$ using $+,.,$ truncated substitution and the functions $sg$, $\bar{sg}$ $h(x)= x$ if $f(x)=0$ and $g(x)=0$ ...
0
votes
0answers
47 views

Proving a function is primitive recursive

Assume $f$, $r$, and $s$ are primitive recursive. Prove that $$h(\overline x,y) = \begin{cases} f(\overline x,y,h(\overline x,r(y))) & r(y)<y \\ s(\overline x,y) & \text{otherwise} ...
0
votes
0answers
26 views

Is a sum of an elementary chain on low models low?

We have an elementary chain of low models $(\mathcal{A}_i)_{i\in\omega}$ such that for every $n\in\omega$ the model $\mathcal{A}_{i+1}$ is a model obtained by Low Basis Theorem from the set $A_i$ that ...
0
votes
0answers
27 views

Positive Arithmetic Complexity

Define the binary operator $[k]$ as an operator that takes an integer $k$ and operates between two integers $a,b$ such that: $$a[k]b = (...((((a)[k-1]a)[k-1]a)[k-1]...a)[k-1]a$$ (b times) And: ...
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 ...