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)

6
votes
0answers
71 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
33 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. ...
0
votes
0answers
26 views

Sum and recursion [on hold]

In Barry Cooper's Computability theory, the author defines inductively a primitive recursive function as follows (paraphrased). The initial functions are recursive: $\mathbf{0}(n) = 0$ $\forall n ...
1
vote
2answers
38 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
24 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
87 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
0answers
59 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
18 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
63 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
32 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
49 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
33 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 ...
2
votes
1answer
38 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 ...
-1
votes
1answer
37 views

Is characteristic function of the rationals computable? [closed]

is the function $1_{x \in Q}$ computable: Thanks
4
votes
2answers
45 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
25 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
47 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
93 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
45 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
101 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
21 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
42 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
74 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 ...
5
votes
0answers
113 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
39 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
129 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
56 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 ...
5
votes
1answer
80 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
107 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 ...
0
votes
1answer
76 views

Which mistake(s) in my argument re: representability, definability and the halting problem?

I'd like to ask for your help in showing me the (quite likely: several) flaws in my argument below, relating weak and strong representability in a formal system and the halting problem. At least ...
4
votes
1answer
82 views

Do you need true randomness to beat the two-envelope game?

A well-known (non-)paradox in probability involves a two-envelope game played between two players, $A$ and $B$: $A$ selects two distinct (real) numbers, $x$ and $y$, writing each one down on a card ...
1
vote
2answers
20 views

Computability: is there an alternative method to decide this language?

For my computability revision I am trying to decide the language, $$L = \{ \text{all binary strings containing the pattern 001 (not necessarily in consecutive places)} \}.$$ I believe that I can do ...
0
votes
0answers
25 views

Show the following languages are not recursive

Show that the language $$L = \{ M : M \text{ is a Turing Machine that halts on input $M$ } \} $$ is not recursive. Show that the language $$ L = \{M : M \text{ is a Turing Machine such that $L(M)$ ...
1
vote
1answer
54 views

determining recognizable or decidable (TM that accepts a TM)

I'm having an issue determining whether certain languages are decidable, recognizable or neither. The specific languages I'm referring to are of the following form L = {<M> | for every w, M accepts ...
0
votes
1answer
79 views

is differ between distributive lattice vs semi-lattice on Turing Degrees

We know a Posed Closed under suprema but not necessarily under infima is an upper semi-lattice. We now r.e set forms a distributive lattice. But my question is why following statement is hold? I ...
0
votes
1answer
32 views

decidability of a given language

The language EGAL is $\{(A,B): A \text{ and } B \text{ are DFAs with } L(A) = L(B)\}$ How do I prove that such language is decidable by testing every word of $A$ and $B$ until a defined length ? i ...
0
votes
0answers
107 views

Does removing the (1) in $\Phi{(1)}$ affect the proof that $ K_0 \leq_m K$ or not?

The fragment below from Martin Davis' book shows $ K_0 \leq_m K$ and also proves $ K_0 \leq_1 K $. My question is if we remove the $(1)$ of $ \Phi^{(1)}$ in the definition of $Y$ (i.e fifth line in ...
2
votes
1answer
46 views

How to computably reduce the number of colors in (infinite) Ramsey's theorem

Suppose we have an "oracle" that gives a homogeneous set for a 2-coloring $\hat c : [\omega]^2 \rightarrow 2$ of pairs of integers. Using this oracle, can we "compute" a homogeneous set for a ...
1
vote
1answer
59 views

Which way is best to solve: $T(n)=5T(n/5) + n\;?$

I'm not sure which way is best to solve $$T(n)=5T(n/5) + n$$ (recursion tree/master method/recurrence?) I would like some assistance, which way is easier and how can I be sure I got the right answer ...
1
vote
1answer
89 views

Have we found a Turing Machine for which halting/non-halting is unprovable?

The undecidability of the Halting Problem implies that there exist Turing Machines such that you can't prove whether they halt or not in whatever logical system you're using (let's say ZFC)$^1$. Have ...
1
vote
1answer
23 views

strongly hh-immune sets

I'm trying to do exercise X.2.16 from Soare's Recursively Enumerable Sets and Degrees, but I have no idea how ro solve it. Any hints would be appreciated. An infinite set is strongly hh-immune or ...
0
votes
1answer
41 views

Convert the regular expression to a NFA

I have to convert the following regular expressions to a NFA: $$(0 \cup 1)^{\star} 000 (0 \cup 1)^{\star}$$ $$(((00)^{\star} (11)) \cup 01)^{\star}$$ $$\emptyset^{\star}$$ $$a(abb)^{\star} \cup ...
1
vote
2answers
42 views

Convert NFA to DFA

I have to convert the following NFA's into the equivalent DFA's. I have done the following: Could you tell me if it is correct??
0
votes
1answer
297 views

Primitive Recursive on Some Functions?

We took an entrance exam on Set and Complexity Course, The question says: if $g$ be a primitive recursive, $1)$ $f_1(0)=c_1, f_1(1)=c_2, ...