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
57 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
46 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
35 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
43 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
40 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
55 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
36 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
73 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 ...
3
votes
2answers
76 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
46 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
98 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
62 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
13 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
80 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
50 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
48 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 ...
10
votes
0answers
181 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
56 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
47 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
29 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
93 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
119 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
25 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
106 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
55 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
40 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
55 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
67 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
32 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
34 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
55 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
111 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
13 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
62 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 ...
21
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
105 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
34 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
51 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 ...
0
votes
3answers
80 views

Can we simplify analysis by getting rid of the uncountable reals? [duplicate]

Since the entire observable part of the universe can only be in a finite number of physically distinguishable states, it seems rather strange that an efficient formal description of the universe would ...
6
votes
0answers
140 views

Recursive and Primitive recursive functions

According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as follows: The constant, projection, and successor functions are all $\mu-$recursive. If $g_1, ...
2
votes
1answer
58 views

Proving the principle of definition by generalized recursion using the inductive closure of an induction system

I'm working through Hinman's Fundamentals of Mathematical Logic in order to review some things, and got stuck in an exercise from section 1.2. Specifically, he asks us to prove (what he calls) the ...
0
votes
0answers
130 views

Decidability of determining the definition of a function

Let's say a property is an SMT formula. Let's say a function has a property iff, with addition of the function symbol to a monadic predicate calculus formula over the signature of Presburger ...
3
votes
2answers
72 views

What's the significance of the Church-Turing Thesis?

My understanding is that the thesis is essentially a definition of the term "computable" to mean something that is computable on a Turing Machine. Is this really all there is to it? If so, what makes ...
2
votes
1answer
74 views

Pointclass of $\text{dom}(F)$ where $F:\omega^\omega\rightarrow\omega^\omega$ is partial recursive.

The definition I am working with: A partial function $F:\omega^\omega\rightarrow\omega^\omega$ is said to be partial recursive iff the partial function $G:\omega^\omega\times\omega\rightarrow\omega$ ...
0
votes
1answer
50 views

Finding the sum of special multiplications

Let $n$ be an integer and $a_1, \dots, a_n$ positive reals. $\forall 1 \leq i < j \leq n$ let $a_{i, j}$ be a positive number. Let $k \leq n$ be a positive integer. I would like to find an ...
4
votes
1answer
92 views

Is there an algorithm that probably solves the Halting problem?

Such an algorithm takes as input any program and returns a probability that it halts. In the limit of many programs, it must answer on average in the correct proportion. But im interested in other ...
4
votes
2answers
112 views

How should the relativized Kleene pointclass $\Sigma^1_1(A)$ be defined?

How should the relativized Kleene pointclass $\Sigma^1_1(A)$ be defined, when $A$ is a set of reals ($A \subset \omega^\omega$)? I assume that there is a standard definition, but I can't seem to find ...