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)

3
votes
1answer
119 views

Is this language decidable?

Is this language decidable? $$\{x\mid \text{$x$ is the code of a Turing machine that always halts on $y$ in less than $y^3$ steps}\}$$ I think it is, because it halts in a finite number of ...
1
vote
2answers
79 views

decidability of $\{x|W_x \text{is different from K in only finitely many elements}\}$

Is the following language decidable? Please explain your argument as I want to learn how such problems must be solved to do the rest on my own. $$\{x \mid W_x \text{ is different from K in only ...
1
vote
2answers
29 views

difference of 2 partial computable algorithms

I have 2 algorithms Algorithm 1: if( Condition1(input)==true ) print(input); else loop forever; Algorithm 2: ...
2
votes
2answers
170 views

Is the difference of two recursively enumerable sets, reducible to $K$?

Is the difference of two recursively enumerable sets, reducible to $K$? $W_x/W_y=\{z|z \in W_x \& z \notin W_y\}$ $K=\{x|\Phi_x(x) \downarrow\}$ $W_x= \text{dom}(\Phi_x)$
1
vote
2answers
228 views

Decidability and undecidability of a set or language

I want to find out whether the following sets are decidable or not. Generally speaking, what exactly should be done about it? Doing some research, I think a language or set is decidable if a Turing ...
0
votes
1answer
143 views

Rice’s theorem and recursion theorem

Prove Rice’s theorem using recursion theorem. I need some hints as to what must be done about it. Please use Davis' book notation: Computability, Complexity, and Languages, Second Edition: ...
1
vote
2answers
136 views

non-recursive function

Give a direct proof that the set $\{x|\Phi_x(1) \downarrow\}$ (which is a set of program numbers that halt on input $1$) is not recursive. I've got an idea that indirect proof must work. Assuming ...
1
vote
1answer
212 views

Primitive Recursion — Definition by Cases

I would like to know if it is allowed to define bounded maximization by primitive recursion and definition by cases in the following way: \begin{align*} [\mathrm{max}\,R](x, 0) &= 0,\\ [\mathrm{...
6
votes
3answers
139 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 ...
4
votes
1answer
87 views

Determine whether two primitive recursive functions are equal

Is there an algorithm to determine whether two primitive recursive functions are equal (as mathematical functions)?
4
votes
1answer
117 views

Extending the recursive functions to higher classes in the aritmetical hierarchy

It is an important theorem that the recursive functions are exactly those which are definable by $\Delta^0_1$ formulas. We have just finished the part about incompleteness in a course I'm TA'ing, and ...
2
votes
2answers
139 views

Prove domain of partial computable function exists

Prove that there is an n such that $W_n$ = {$2n, . . . , 2n + n^2$} Now I don't know where to start with this question, how can I go about answering it? Would I construct a computable function that ...
2
votes
1answer
185 views

Injection from computable numbers into natural numbers

Each Turing machine which writes an infinite sequence of 1 and 0 can be regarded as representing a (computable) real number (and of course each Turing machine represents a natural number by its ...
1
vote
1answer
37 views

Numbering the Grzegorczyk Hierarchy.

I would like to know if there is a (known and maybe published) way to numbering, in a Gödel style, the functions belonging to every class in the Grzegorczyk Hierarchy and how could it be done.
1
vote
1answer
131 views

Degree structure of $1$-Generic Set

We can construct a $1$-generic set $A\leq_{T}\emptyset'$, using an $\emptyset'$-oracle and finite extension construction as in the Kleene-Post theorem to meet all jump requirements. How can I show ...
0
votes
1answer
186 views

Second incompleteness and Model theorey

If we let $T$ be a consistent theory in the language of arithmetic $\mathcal{L}_A$ theory extending Peano Arithmetic — with specified numbering of formulas $\left[\cdot\right]$ and suppose that $\...
1
vote
2answers
143 views

Infinite number of Proofs in Propositional Calculus?

Reading over a book on computability, it asserts that in P.C., if A is a theorem, then A has arbitrarily many proofs. I can't see how that would work, would you do an infinite loop in the sequence of ...
0
votes
2answers
128 views

How is strong induction recursive?

I know that strong induction is equivalent to induction, and I know that functions that are defined by inductions are recursive. So theoretically, strong induction should also give a recursive ...
1
vote
0answers
72 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$ ...
14
votes
1answer
325 views

Primitive recursive function which isn't $\Delta_0$

What is the simplest/cutest example (and/or example with the most student-friendly proof that it is an example) of a primitive recursive function which isn't representable by a $\Delta_0$ wff?
0
votes
0answers
137 views

Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?

In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computability theory, I asked: we treat all inputs and intermediate results and final outputs as ...
0
votes
2answers
107 views

Can all programs be modeled as operations of elementary arithmetic operations on inputs?

In mathematics and computabiltiy theory, we treat all inputs and intermediate results and final outputs as natural number. While algorithms/programs themselves are considered natural numbers, here we ...
6
votes
1answer
109 views

A question on non-standard ordinals in $\alpha-$recursion

Let $M$ be an admissible set, namely, $M\models KP$ where KP stands for axioms of Kripke–Platek set theory. Denote $\beta=M\cap ORD$ where $ORD$ is the class of ordinals. I wanted to prove $L_\beta\...
3
votes
2answers
351 views

delta-zero formula and power of 2

How can we show that $x=2^k$ for some $k$ is equivalent (in the Naturals) to a $\Delta_0$ formula? So, I'm stuck at showing that 'y divides x' and '2 divides y' are equivalent in the Naturals to $\...
0
votes
3answers
106 views

Binary expansion and correspondence of finite strings

How can we show that there is a one-to one correspondence between finite strings of the symbols 1 and 0 and the naturals $\mathbb{N}$. I was thinking along the lines of maybe using a 2-tuple, but ...
1
vote
1answer
65 views

Post Correspondence Problem

The alphabet consists of just two characters, $0$ and $1$. How do I go about proving that it's undecidable? I was thinking of reducing the general case to binary form meaning if the alphabet has ...
1
vote
3answers
76 views

a finite algorithm mapping from $\omega \times \omega$ to $\omega$ possible?

We know that $\omega \times \omega$ is isomorphic to $\omega$, but I am not sure if there would exist a finite algorithm mapping from $\omega \times \omega$ to $\omega$. An algorithm would of course ...
4
votes
1answer
146 views

The Permitting Method

Define the term late permitting in the following way: $C$ late permits an element $x$ to enter $A_{s+1}$ if for a fixed computable function $f$ with $f(n)>n$, there exists $y\leq x$ such that $y\in ...
1
vote
1answer
138 views

simple sets, cofinite sets, filters

Let $\mathcal S$ be the class of simple sets and $\mathcal C$ the class of cofinite sets. Prove that $\mathcal S\bigcup \mathcal C$ is a filter in $\mathcal E$. Definitions: An infinite set is "...
0
votes
1answer
79 views

Proving Decidable Language

Let $E$ be a Turing machine outputting a list of codes of Turing machines $\{\left \langle M_1 \right \rangle, \left \langle M_2 \right \rangle, ...\}$ where every $M_i$ is deciding some language $L_i$...
3
votes
1answer
84 views

Which diophantine polynomials generate these diophantine sets?

Via Matiyasevich's Theorem, it is easy to prove that the following sets are diophantine: $\{k\}$ $\{0, 1, \dots, k-1, k+1, k+2, \dots \}$ $\{0, 1, \dots, k\}$ $\{k+1, k+2, \dots\}$ Number 1 is ...
6
votes
1answer
524 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 ...
2
votes
1answer
586 views

Is this undecidable language recognizable?

Is this language: $L = \{\langle M\rangle : \text{$M$ is a Turing machine and $L(M)$ is decidable}\}$ which I know that is undecidable, turing-recognizable? Is its complement recognizable? ...
1
vote
2answers
741 views

Turing machine for balancing parentheses on a two letter alphabet

How to construct a Turing machine $M=(Q,\Gamma,b,\Sigma,\delta,q_0,F)$ which decides if a sting on the alphabet $\{(,)\}$ is ''balanced'' (e.g. $(()())$ is balanced and $))(($ or $()(($ is not) with ...
3
votes
1answer
206 views

Recursion schema and the arithmetical hierarchy

In computability we define the following basic functions, the zero function, the successor function, and the functions $I_{n,k}(x_1,\ldots,x_n)=x_k$ for $k\leq n$. Next we define three schemata for ...
4
votes
1answer
88 views

A paradox related to computable reals?

Let O be a computable ordering of all computable reals in ⟨0,1) (eg. first by length of programs computing them and then lexicographically). (it does not matter that they appear there more than one ...
6
votes
1answer
147 views

A topological example from Church's undecidability paper

A. Church, in his classical paper An unsolvable problem in elementary number theory in American Journal of Mathematics Vol. 58 No. 2. (1936), pp. 345-363, (available here), wrote: There is a class ...
3
votes
1answer
116 views

Is my logic here correct? Primitive recursion and diagonalization proof

I'm trying to understand diagonalization as it applies to proving that not all total functions are primitive recursive functions. For example, say that we enumerate all primitive recursive functions ...
2
votes
1answer
73 views

Proving a class of relations is closed under an operation

Given a class of functions $\mathcal{A}$ is closed under substitution and the operation $(\mu y)_{\leq z}$, where $$ (\mu y)_{\leq z}f(y, \vec x) = \begin{cases} \min\{y : y \leq z \land f(y, \vec x)...
3
votes
2answers
99 views

If $L\in REG$ then $M$ has a finite number of distinct rows

Let $L \subseteq \Sigma^{\star}$ and let $M^{\Sigma^{\star} \times \Sigma^{\star}}(\{0,1\})$ an infinite matrix such that for each $x,y\in \Sigma^\star$: $$ m_{x,y}=\begin{cases} 1 & x y\in L\\ 0 &...
0
votes
1answer
111 views

Computability function - how to express it in set theory/arithmetic hierarchy

Let's say that $f$ is computable function such that for particular inputs $x$ and $y$, $f(x) = 0$ and $f(y) = 0$. If we want to express this in logical form (arithmetic hierarchy formula), what would ...
0
votes
1answer
129 views

recursively enumerable of Godel numbering

There are statements for natural number x, like followings m: "x is even natural number" n: "x+1 is odd number and x>1" l: "x is positive integer multiple of two" m, n, l has same boolean value ...
2
votes
1answer
85 views

What's the error in this argument that Fin$\le_m$Inf

There must be an error in the following argument since Fin is not many-one reducible to Inf, I can't seem to find it. Here it is informally (I hope it's straightforward and not confusing): Take any ...
1
vote
1answer
84 views

For a one-to-one function is the pullback of a recursively enumerable set $f^{-1}[W_e] = W_{g(e)}$ where $g$ is one-to-one?

Let $\phi_e : \mathbb{N} \to \mathbb{N}$ be the recursive function coded by $e$ and $W_e = \{ x : \phi_e(x) \text{ is convergent}\}$. A set $A$ is recursively enumerable if $A = W_e$ for some $e$. ...
0
votes
1answer
127 views

completeness and creative

I'm trying to show that any complete $\Sigma_1^0$ set is creative. The definition of creative I understand is: if there is a total recurvise function f s.t. f(e) is an element of A iff f(e) is an ...
0
votes
1answer
71 views

recursive maps and decimal representation

I'm trying to think of an example of a real number $R$ such that the map $n \mapsto R[n]$, where $R[n]$ is the $n$th digit of the decimal representation of $R$, is not recursive. So I was thinking to ...
1
vote
1answer
158 views

recursive and creative theorem

How can we show that if A is creative, then A is not recursive. Only thing I can get out is the fact that if A is creative, if it is rec. enumerable and the complement(A) is productive. Thanks
1
vote
1answer
181 views

How does one prove that 1-generic set is not computable?

Without resorting to diagonalization proof of halting problem, how does one prove that 1-generic set is not computable?
2
votes
0answers
165 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 ...
0
votes
1answer
72 views

Identifying a pattern in an array

Is there a way to identifying a pattern and/or recursive function for an array? If yes, how can I do this. Could anyone please help me with some information and/or resource for this? Any help is ...