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
3answers
667 views

Complete theories - dense linear order

There are two things I would like to prove. DLO - Dense linear order is complete, that means that when $\psi$ is a sentence of the language $\{<\}$ then $DLO\vDash\psi$ or $DLO\vDash\neg\psi$ ...
1
vote
1answer
102 views

First order sentences and Halting problem recursively enumerable

I am just finding searching for some examples of recurisvely enumerbale models and I do not know how to prove that the following ones satisfy this property. Consider the set of first order ...
0
votes
1answer
179 views

Recursively enumerable properties

In my textbook are three interesting properties listed (which I would like to prove) (1) A is recursively enumerable iff A is the domain of a partial computable function (2) A is recursievly ...
11
votes
0answers
209 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 ...
0
votes
1answer
71 views

Tally method to build a machine (on paper, Turing Machine

Consider function $q$: For any even integer $x\ge0$ (including $0$): $q(x) = 4x$ I want to design a machine (on paper of course) to compute q under the Tally system. Another restriction is that when ...
3
votes
3answers
368 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 ...
31
votes
4answers
1k views

Why do we believe the Church-Turing Thesis?

The Church-Turing Thesis, which says that the Turing Machine model is at least as powerful as any computer that can be built in practice, seems to be pretty unquestioningly accepted in my exposure to ...
3
votes
1answer
233 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 ...
2
votes
1answer
111 views

Application Church-Turing thesis

I would like to give examples of problems which are solvable with an algorithm, for example the function $f$ which maps the tuple $(n,m)$ to the greatest common divisor. This map is recursive. I would ...
1
vote
0answers
81 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 ...
7
votes
4answers
518 views

What is the relationship between “recursive” or “recursively enumerable” sets and the concept of recursion?

I understand that "recursive" sets are those that can be completely decided by an algorithm, while "recursively enumerable" sets can be listed by an algorithm (but not necessarily decided). I am ...
1
vote
1answer
89 views

Recursive function with code $n$, whose output is the number $n$ itself

There is a recursive function with code $n$, whose output is the number $n$ itself. That is $\phi_n$ is the constant function with value $n$. I've been toying with the idea of using s-m-n ...
1
vote
0answers
34 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
2answers
1k views

Existence Universal goto-programm (turing machine)

May you can help me out with my problems with source codes. Well first of all we proved that for recursive functions $N:\mathbb N^2\rightarrow \mathbb N$ and $A^k: \mathbb N^k\rightarrow \mathbb N$ ...
3
votes
4answers
287 views

properties of recursively enumerable sets

$A \times B$ is an r.e.(recursively enumerable) set, I want to show that $A$ (or $B$) is r.e. ($A$ and $B$ are nonempty) I need to find a formula. I've got an idea that I should use the symbolic ...
3
votes
1answer
117 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
78 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
169 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
225 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
139 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
132 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
211 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,\\ ...
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
86 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
115 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
138 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
184 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
127 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
318 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
133 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 computabiltiy theory, I asked: we treat all inputs and intermediate results and final outputs as ...
0
votes
2answers
105 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
105 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 ...
3
votes
2answers
344 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
63 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
134 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 ...
3
votes
1answer
47 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
512 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
565 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
738 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
202 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 ...