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)

1
vote
1answer
89 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
451 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 ...
1
vote
1answer
24 views

Show how the Diophantine sets are closed under concatenation.

It follows easily from Matiyasevich's Theorem that the Diophantine sets are closed under concatenation. I am trying to figure out the mechanism by which they are closed under concatenation. In other ...
5
votes
1answer
67 views

Omitting Types… recursively

I'm working on the following problem at the moment: Let $\mathcal{L} = \{R\}$, where $R$ is a binary relation symbol. Let $T$ be a consistent, decidable $\cal{L}$-theory, and let $p(x)$ be a ...
3
votes
1answer
65 views

Complexity of index sets in nonprincipal ultrafilters

Let $U$ be a nonprincipal ultrafilter on $\omega$. It can be shown that the set $I = \{e \mid W_e \in U\}$ (where $W_e$ is the $e$th r.e. set in some given enumeration) cannot be $\Delta_2^0$ (in ...
2
votes
1answer
133 views

What does noncomputable really mean?

I believe I understand the definition of a noncomputable problem from an introductory computer science class, but I don't understand what it really means. One of my hypothesis was that a ...
2
votes
1answer
77 views

Regarding playing an infinite number of games that could last infinitely long amounts of time

So after watching the last Stanley cup game, a problem popped up in my head for which I have no solution. Say we have a game, like a hockey game, that has the possibility of going on forever. Of ...
4
votes
2answers
193 views

How do we know that every halting Turing Machine can be expressed as a recursive function?

I've hear many times that a major result in Recursion Theory is the equivalence of Turing and Godel's models: the functions implementable on a Turing machine are precisely the functions that can be ...
6
votes
2answers
198 views

Undecidability of the halting problem

One can prove by reduction from the special halting problem $H_S$ the undecidability of the (general) halting problem $H$. Is the converse also possible? That is, is it possible to prove the ...
8
votes
2answers
157 views

Decidability of the consistency for complete finitely axiomatized theories?

Let $\Phi$ be a finite set of first order formulas over a signature $S$. Assume that (we can prove that) $\Phi$ is complete, i.e. for each first order formula $\phi$ over $S$, we have $\Phi \vdash ...
2
votes
2answers
89 views

Computational power of arithmetically complex sets

When learning basic computability theory we are usually given as examples of arithmetic sets sets which are complete for their level of the arithmetic hierarchy (like the halting set, the set of ...
18
votes
1answer
1k views

How to interpret “computable real numbers are not countable, and are complete”?

On page 12 of this (controversial) polemic http://web.maths.unsw.edu.au/~norman/papers/SetTheory.pdf Wildberger claims that Even the "computable real numbers" are quite misunderstood. Most ...
3
votes
3answers
674 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
103 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
184 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
210 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
72 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
371 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
237 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
82 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
526 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
290 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
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
227 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
141 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
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
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
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
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
321 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
136 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
106 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
107 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 ...