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)

0
votes
1answer
29 views

Hardness of index sets for computable structures

Suppose we have a computable structure $M$ and we want to show that its index set $I(M)$ is (many-one) $\Gamma$-hard for some complexity class $\Gamma$ (like $\Sigma^0_2$). To do this, we need to show ...
0
votes
0answers
53 views

Show that they are recursively enumerable

I found a question I have difficulties to solve. Show that the domain and the range of a recursive function are recursively enumerable. Can you give me a hint how I can show it? Recursively ...
3
votes
0answers
89 views

What does “Turing-complete” really mean?

People talk about various programming languages or computational models being "Turing-complete." But what does that technically mean? The technical definition is buried under tons of informal ...
2
votes
1answer
35 views

Why is $f(x)=x^{2}+1$ a primitive recursive function?

I'm trying to find out why $f:\mathbb{N}\rightarrow\mathbb{N},f(x)=x^{2}+1$ is a primitive recursive function. For $f(S(y))$ I can't seem to get it to fit the axioms known to me about primitive ...
5
votes
0answers
43 views

Primitive recursion and $\Delta^0_0$

Until recently I assumed that primitive recursive relations are exactly $\Delta^0_0$ (i.e. bounded) ones, but I learned they're different (the former is a proper superclass of the latter). I have ...
2
votes
1answer
58 views

Does semantic inconsistency guarantee syntactic inconsistency?

I'm wondering about the possibility of circumventing the problem of incompleteness posed by Roger Penrose in his book "Shadows of the Mind". It occurred to me (and, Googling has revealed to me, ...
0
votes
0answers
9 views

Generalizing equal turing machine problem

I know that $EQ_{TM} = \{<M_1,M_2> | L(M_1)=L(M_2)\} \notin RE \cup CO-RE$ Can I generalize and say that $L' = \{<M> | L(M) = C \} \notin RE \cup CO-RE$ Where C is the language of any ...
0
votes
0answers
9 views

Turing Machine Membership problem and how to prove its undecidable

ATM = {$<m, w>$ | M is a Turing Machine that accepts string w}. How can I prove that ATM is undecidable? Here's what I have so far: Any decidable problem is accepted by a Turing Machine. It ...
0
votes
0answers
11 views

Question about the effect of the basic primitive recursive projection function.

Projections are said to allow us to use "any argument in any order", and the function below can be proved to be a PR function by projections and the composition rule. Let $ i_0,\cdots,i_{m-1} \in n = ...
1
vote
1answer
50 views

What is the meaning of 'recursive' in Boolos, Burgess and Jeffreys? (Computability and Logic)

In the book Computability and Logic by Boolos, Burgess and Jeffrey (page 71 - 5th edition) it defines a recursive function as follows: The functions that can be obtained from the basic functions ...
0
votes
1answer
39 views

Unclear why (first order) satisfiability undecidable and not semi-decidable.

Hoping this will just be a terminology question, otherwise I have a bigger problem of harboring a misunderstanding re: decidability. We know that (first order) satisfiability (for the general case of ...
0
votes
0answers
31 views

What are non-monotonous computable convergent sequences of rationals with non-computable rate of convergence?

A computable convergent sequence of rationals can have a non-computable rate of convergence. By a rate of convergence of a sequence $(q_k)_k$, I mean a function $f : \omega \rightarrow \omega$ such ...
0
votes
0answers
29 views

How to predict intuitively the recurrence relations of josephus problem?

i have studied the Josephus problem from the concrete mathematics book.I have understand all related calculations discussed on that book.However i have some difficulties regarding to recurrence ...
2
votes
1answer
39 views

Understanding difference between reduction methods

In Sipser's book "Introduction to the theory of computation" there are 2 methods for proving that $\rm HALT_{TM}$ is undecidable by a reduction from $\rm A_{TM}$ I am trying to figure out the ...
0
votes
1answer
54 views

The result of substituting recursive total functions in a recursive relation.

In the book Computability and Logic by Boolos, Burgess and Jeffrey it defines a recursive function as follows: The functions that can be obtained from the basic functions $z, s, id^i_n$ by the ...
1
vote
1answer
35 views

A c.e. equivalence relation is computable if each equivalence class is of a fixed finite cardinality with finitely many exceptions

I've been working on the following quiz: Let $E \subseteq \omega \times \omega$ be a c.e. equivalence relation and $n \in \omega$. Suppose all of $E$'s equivalence classes but finitely many ...
0
votes
1answer
71 views

Computability problems — can't solve

I have a pair of exercises I can't solve (tomorrow I'll have a test). I need some kind of solution so I can apply it to other exercises...thanks to all! In the following $W_n$ means the domain of the ...
2
votes
2answers
69 views

Are untyped and simply typed lambda calculus mutually exclusive?

In "Proposition as Types" by Philip Wadler we can read that: The two applications of lambda calculus, to represent computation and to represent logic, are in a sense mutually exclusive. If ...
2
votes
1answer
39 views

Encode lambda calculus in arithmetic?

There is plenty of information about how to encode arithmetic given the lambda calculus. The wikipedia article on Church Encoding seems complete to my inexpert eye. My question is "how about the ...
13
votes
1answer
94 views

When is Chaitin's constant normal?

Chaitin's constant is not one constant, but depends on an effective prefix-free encoding $d$ of Turing machines as bit strings. Once such an encoding is chosen, the corresponding Chaitin's constant is ...
2
votes
2answers
57 views

Extended version of the theory of reals and its decidability

It is well-known due to Tarski that the theory of reals $(\mathbb{R},+,\cdot,<,=)$ is decidable. I was asking my self whether one would lose the decidability by adding all real constants. More ...
0
votes
0answers
11 views

Prove that $ALL_{CFG}$ is undecidable by reducing from PCP

I'm studying for a Computability exam that I have in a few weeks, and have come across this question which I'm having a hard time solving: Prove that $ALL_{CFG}=\left\{ \left\langle ...
9
votes
2answers
1k views

Show that the question “Is there life beyond earth?” is decidable

I was given a question to prove that there exists a turing machine that solves the question Is there life beyond earth? and is decidable. I actually don't understand how to show a turing ...
0
votes
1answer
77 views

Hanf Numbers and Decidability

Currently reading J.L. Bell's Models and Ultraproducts and at the end of Chapter 4 section 4 the authors comment that "In spite of the fact that most languages can easily be shown to possess Hanf ...
1
vote
1answer
48 views

Show $(\mathbb{Z}, +, \cdot, 1, 0 )$ is not R-decidable

Show $(\mathbb{Z}, +, \cdot, 1, 0 )$ is not R-decidable It gives the hint to use $x \in \mathbb{N} \leftrightarrow \exists x_0 \exists x_1 \exists x_2 \exists x_3(x \equiv x_0 \cdot x_0 \wedge x_1 ...
1
vote
2answers
45 views

show the set of valid second-order $\emptyset$-sentences is not R-enumerable

show the set of valid second-order $\emptyset$-sentences is not R-enumerable this would have the empty symbol set i.e. $S = \emptyset$ so it would be sentences that are universally or existentially ...
9
votes
0answers
159 views

The ethics of Borel determinacy

I was speaking with a friend the other day, and I happened to say "morally, Borel determinacy is as strong as ZF." I was riffing on the well-known result of Harvey Friedman, that we need ...
0
votes
2answers
55 views

Example of recursively enumerable languages that under intersection are $\emptyset$

I am trying to think about an example of a recursively enumerable languages $L_1,L_2 \in RE $ and $L_1,L_2 \notin R $ that satisfy: $L_1 \cap L_2 \in R $ I know that it will be probably something to ...
1
vote
2answers
42 views

Proving that $a \dot{-} (b+1) = (a \dot{-} b) \dot{-} 1$

This should be an easy exercise from Hodel's Introduction to Mathematical Logic, but for some reason I'm not getting it right. Define $a \dot{-} b$ as $a-b$ if $a \geq b$ and as $0$ otherwise. ...
1
vote
2answers
39 views

Little confused about the constraint of Injective Functions and Surjective.

From my understanding, A Function is called to be Injective, if different elements of the first set are mapped to different elements of the second set. Let set A = {a,b,c} and set B = {1,2,3} Are ...
1
vote
0answers
28 views

Is the computable numbers equal to the set of all the limits of finite length algebraic expressions?

Let's call $C$ the set of computable real numbers and $L$ the set of all the (existing) limits of finite length algebraic expressions. By $L$ I mean the set of all converging limits $\lim_{x_1 \to ...
4
votes
4answers
90 views

Why is the numbering of computable functions significant?

My course is about computability theory, and I'm having troubles with one of the main concepts. This might be a really newb question, but I've been struggling with understanding it's significance (and ...
7
votes
1answer
115 views

Comparing different relativizations in computability

Most, but not all, theorems in computability relativize. In principle, we should go through the original proof to check that a relativized version of a theorem holds. In practice, we often just wave ...
0
votes
0answers
23 views

To prove a language is not recursive

Prove the language $$L_1=\{\sigma\in\{0,1\}^*|\sigma \text{ codes a TM which accepts at least one word }\}$$ is not recursive. I think it has something to do with $$L=\{\sigma\in\{0,1\}^*|\sigma ...
2
votes
2answers
77 views

Ackermann's function is $\mu$-recursive

In my book there is the following proof that Ackermann's function is $\mu$-recursive: We propose to show that Ackermann's funcition is $\mu$-recursive. The first part of the job is to devise a ...
0
votes
0answers
33 views

Church’s Thesis with regard to R-decidability and R-enumerability.

Church’s Thesis with regard to R-decidability and R-enumerability: If some set is enumerable/decidable, then there exists a program, i.e., a register machine, with respect to which the set is ...
1
vote
0answers
50 views

Primitive recursivness of a function. How does the function work?

So, I need some help with an homework assignment. Firstly: understanding the following function: $h(x) = \prod_{m=0}^{f(x)} m*f(m)$ From my limited knowledge of the product of sequences my guess is ...
3
votes
2answers
38 views

Decidability of predicate calculus with equality only

I read in some books that propositional calculus is decidable (e.g. with truth tables), and predicate calculus is not decidable (as proved by Church and Turing). Unfortunately, I do not exactly ...
1
vote
1answer
48 views

$\mu-$recursive functions

In my book there is the following: Although the class of primitive recursive functions contains a great many functions of practical interest, it does not include all the Turing-computable or ...
4
votes
2answers
56 views

Can you solve the halting problem for a single, non-universal Turing machine?

So, I'm familiar with the halting problem and its proof. However, I also understand that the proof is for any universal machine $U$; that is, the set ...
1
vote
0answers
31 views

Are all finite languages regular?

I've been thinking about this for a while and still cannot come up with a way to show that all finite languages are regular. I know that all finite languages consist of finite number of strings that ...
2
votes
0answers
30 views

Is there any research on Diophantine Approximation with computable numbers

I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
0
votes
1answer
49 views

A formula that, when plotted, yields its own display

I've just seen a video on Tupper's self-referential formula. When I heard that this formula was not at all self-referential but merely a simple way to generate every possible $17\times 107$ dot matrix ...
6
votes
4answers
104 views

Is the logarithm of $\aleph_0$ infinite?

In classical mathematics $2^{\aleph_0}=\aleph_1$, right? So if $2^x=\aleph_0$, what does $x$ equal? In other words, can we define a logarithm for $\aleph_0$, and what should it be. Is it infinite? ...
0
votes
0answers
12 views

Approximation of set cover with randomized algorithms

I know that it is np hard to approximate set cover with a factor o(log(n)). Is there a similar result of hardness to approximate using a ranomized algorithm? Is there any article about that?
2
votes
0answers
52 views

Properties of Ackermann's function

I want to show the following properties of Ackermann's function: $A(x,y)>y$. $A(x,y+1)>A(x,y)$. If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$. $A(x+1, y) \geq A(x,y+1)$. $A(x,y)>x$. If ...
20
votes
7answers
2k views

Example of uncomputable but definable number

Every computable number is definable. However, the converse is not true. What is an example of a real number that is definable but that is NOT computable? I guess if it is there, we can "define" ...
2
votes
2answers
103 views

How to understand this informal description of the levels of the arithmetical hierarchy?

In my class notes I do not understand why the following statement is true, nor what it means: Informally, the lowest level in the Arithmetical Hierarchy in which $n$-ary relation $R$ is definable ...
0
votes
2answers
31 views

Examples of undecidable languages contained in 1*?

I've been given the following question Show that there is an undecidable language contained in $1^*$. But I can't think of any undecidable languages that are contained! Can someone please lend a ...
1
vote
1answer
46 views

Proof that mappings $K$ and $L$ are primitive recursive.

Let $J$ be the function: \begin{equation*} J(m,n)= \begin{cases} n^2+m \text { if } m\le n \\ m^2 + m + (m-n) \text { if } m > n \\ \end{cases} \end{equation*} Let $K, L$ such that $K(k)$ is ...