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
votes
1answer
18 views

How do we show that $A$ is polynomial time reducible to itself? [duplicate]

How do we show that $A$ is polynomial time reducible to itself, i.e. that $A \le_p A$? I know how to prove that it is transitive, but I don't know how to prove it's reflexive. I'm aware that it's ...
0
votes
0answers
27 views

Reducing Pcp (Post's correspondence problem) to mPcp

Recently I have been studying Post's correspondence problem ($Pcp$), and I have stumbled upon a problem where I need to find a reduction from $Pcp$ to a modified version, $mPcp$. This modified version ...
2
votes
2answers
68 views

Random and non-computable numbers

Let $\alpha \in (0,1): \quad \alpha=0.a_1a_2\cdots a_n \cdots \quad$ where the $a_n$ are numbers generated by a physical generator of genuinely random numbers (if it exists). Than it seems that $\...
0
votes
1answer
25 views

Algorithm with undecidable input set?

I am interested in "Relative Decision Problems" in the following sense: Let $\mathbb{N} \supseteq U \supseteq S$. Is there an algorithm such that on a given input $u \in U$ decides whether $u \in S$? ...
1
vote
1answer
124 views

Does a $\Pi_2^0$ sentence becomes equivalent to a $\Pi_1^0$ sentence after it has been proven?

I heard that the P vs NP question is equivalent to a $\Pi_2^0$ sentence, and that the Riemann hypothesis is equivalent to a $\Pi_1^0$ sentence. Many known mathematical theorems state that some ...
2
votes
2answers
87 views

About the Words “recursion” and “recursive”

According to Wikipedia, Recursion is the process of repeating items in a self-similar way. On the other hand, the word "recursive" is an adjective and is often used as a synonym of "computable" when ...
2
votes
1answer
37 views

Enumerating the primitive recursive functions without repetition

According to this paper (and this one), it is possible to enumerate the primitive recursive functions without duplication, even though equality of primitive recursive functions is not decidable. I am ...
0
votes
0answers
23 views

Help with a proof of the computability of the monus function by recursion

Reading a text on computability by a guy called Cutland, and he basically asserts the following, which is suppose to be a proof by recursion that x ∸ 1 is a computable function: (1) 0 ∸ 1 = 0 (2) (x+...
0
votes
1answer
34 views

Constructing a computably infinite tree with no computable infinite branches using PA

Define an infinite tree as any set of sequences closed under prefix restriction, i.e. any prefix restriction of a sequence in the set is also in the set, where a prefix restriction is a restritcion of ...
3
votes
1answer
77 views

Proof of Kondô-Addison theorem

The proof of the (lightface) Kondô-Addison theorem (aka $\Pi^1_1$ uniformization) that I know goes like this: for a $\Pi^1_1$ set $R \subseteq 2^\omega \times 2^\omega$, define the uniformization of $...
2
votes
2answers
29 views

Is the set of all Turing machines whose language includes the set of all even length strings recursively enumerable?

Is the set of all Turing machines whose language includes the set of all even length strings recursively enumerable? My intuition tells me the answer should be no, but I can't prove it. I know that ...
0
votes
0answers
21 views

simple questions on $TM$s runs lengths

Is it possible that the number of running steps in $TM$ that runs on word $w$ will be $0$? Is it possible that the number of running steps in $TM$ that runs on the empty word $\epsilon$ will be bigger ...
11
votes
1answer
447 views

Approximate spectral decomposition

A detailed attempt below. I am interested in effective and constructive computations for finding approximate spectral decompositions in some suitable format. Namely, let $A: H \rightarrow H$ be a ...
0
votes
0answers
78 views

Faster growing function than the fast growing heiarchy under Church-Kleene?

Is there a computable function that grows faster than any function in a fast growing hierarchy with index less than the Church–Kleene ordinal, where computable fundamental sequences are used? If the ...
0
votes
0answers
7 views

Simulating a k state Turing machine M would require a Turing machine M' that has some f(k) number of states

I am writing a proof for a problem, and in that proof, I am simulating a TM M that has k states and terminates after being started on a blank input. I want to show that to simulate M on a TM M', M' ...
0
votes
0answers
41 views

Prove that a certain intrinsic property of Turing machines is not decidable

Can anyone help me to prove that the following language is nod decidable? $$ A=\{\langle\,M,w,q\,\rangle\mid M \text{ is a $TM$ , $w$ is a word, $q$ is a state in $M$ and while $M$ runs on $w$ it ...
3
votes
2answers
53 views

Multiplicity of real numbers in a tuple with known cardinality decidable?

Given a tuple $(x_1, \ldots, x_n)$ of computable real numbers $x_1, \ldots ,x_n$ and its cardinality $|\{x_1, \ldots x_n\}|=d \leq n$, is it decidable which numbers have which multiplicity? In other ...
0
votes
0answers
42 views

Classifying languages

I'm working on understanding what kind of languages are decidable, recognizable, and co-recognizable. I came across this problem that I think will really help me but I'm still quite unsure of how to ...
1
vote
1answer
59 views

Decidable and Recognizable

I'm trying to work on this problem but I cant seem to find an approach to it: For any language L ⊆ Σ∗ define the language PREFIX(L) := {w ∈ Σ∗ | some prefix of w is in L} (a) Show that if L is ...
0
votes
1answer
24 views

decidable intersect undecidable

Hello I'm kind of having trouble with computability, so my question is I need to define af language A and B such that A is decidable and B is undecidable when I do $A\cap B $ is decidable. also ...
1
vote
1answer
47 views

Does this sketch proof that every formula is equivalent to one in the arithmetical hierarchy work?

In the lecture notes for my course, the arithmetical hierarchy is defined as follows: A formula is $\Sigma_0$ or $\Pi_0$ if every quantifier is bound; A formula is $\Sigma_{n+1}$ if it is of the ...
1
vote
1answer
98 views

Show that the following function is primitive recursive

Let $f$ be a function defined by \begin{array}{l} f(0)=1;\quad f(1)=2;\quad f(2)=3;\quad f(n)=0 \mbox{, for $n>2$} \end{array} How to show that $f$ is primitive recursive?
0
votes
0answers
21 views

Prove set L is recursive iff there is an increasing total computable function which it's range is L.

Set L is recursive iff there is an increasing total computable function which it's range is L. The function is on $\Sigma^{*} \rightarrow \Sigma^{*}$. And by increasing it means that if a comes ...
0
votes
0answers
22 views

Prove uncountability of set L that L and L' neither of which is recursively enumerable.

How do I prove that the set of all languages L on alphabet {0,1} that neither L or L' are recursively enumerable, is uncountable? Proving uncountability can be done through diagonalization like the ...
0
votes
1answer
36 views

proof that languages are/are not in RE (probably with mapping reduce)

Given $2$ languages: Let $u \in \Sigma^*$ (constant word). $A_u=\{<M> \big{|}\,\, u\in L(M) \text{ and M is TM }\}$ $B_u=\{<M> \big{|}\,\, L(M)=\{u\} \text{ and M is TM }\}$ I ...
1
vote
2answers
37 views

A semi-recursive infinite set is the range of some injective recursive total function

The wikipedia article for semi-recursive sets (formally titled "recursively enumerable sets") claims: A set S of natural numbers is called recursively enumerable if there is a partial recursive ...
2
votes
1answer
42 views

Ramsey theorems for the naturals and for general infinite sets

In reverse mathematics and in recursion theory, the infinite Ramsey theorems are usually stated in terms of coloring of $[\Bbb N]^n$. How do these (not) imply the Ramsey theorems for general infinite ...
1
vote
0answers
22 views

turing machine decidable description for the language

L = { | R is a regular expression that produces at least one word in {a, b} * which contains a symbol exactly 3 times} ...
0
votes
1answer
38 views

turing machine decidability language

I must show that this language is decidable but I think it's not {D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ } Here what I think I give a reduction from E(TM). I suppose that this ...
0
votes
0answers
48 views

AllTM is undecidable using recursion theorem

Basically I'm trying to prove that allTM is undecidable using recursion. I know that you basically suppose there is a decdier H for the language, you construct a TM M that get's own code, simulates H ...
0
votes
1answer
28 views

Showing a relation is primitive recursive, recursive, or semirecursive.

I am not sure what strategy to use to I should use to show this is primitive recursive. I believe I am to show all three cases: primitive recursive, recursive, and semi-recursive. The diagonal of $...
1
vote
1answer
27 views

Is image of recursive set under recursive function recursive? [duplicate]

Given $A$ - recursive set and function $f$ which is also recursive. Is $f(A)$ recursive? I think that it isn't recursive, but how to prove it?
0
votes
0answers
16 views

Prove by printing turing machine that RE closed under iteration

I do not know what is the formal name of printing turing machine in english, maybe "counter machine". This machine prints a whole language without any input. for example: counter machine that counts ...
0
votes
1answer
89 views

Prove claims about disjoint union and decidable/undecidable languages

Let $L\subseteq\Sigma^*$ decidable language and $A\subseteq\Sigma^*$. Let $B=A\sqcup L$ (a disjoint union). Prove: $1$. $B\in RE \Rightarrow A\in RE$ $2$. $B\in R \Rightarrow A\in R$ Thanks!
0
votes
0answers
50 views

Prereqisites for: Subsystems of second order arithmetic

As the title suggests, im wondering what the prerequisites for Simpsons book, Subsystems of... are? Unfortunately I cant find it in the preface. My background is a Bachelor in Philosophy and ...
3
votes
1answer
137 views

How are halting oracles related to set theory?

By the Curry Howard isomorphism, constructive type theory and computation are intimately related to mathematical logic and proofs. Moreover, type theory gives us a nice framework for describing ...
0
votes
1answer
38 views

Not all recursively enumerable sets are recursive

Is there a simple explanation which says why this is? I'm not looking for a proof or anything that contains too many technical terms. I've come across the example of the Halting problem but I don't ...
3
votes
2answers
297 views

How can addition be non-recursive?

Tennenbaum's theorem says neither addition nor multiplication can be recursive in a non-standard model of arithmetic. I assume recursive means computable and computable means computable by a Turing ...
0
votes
1answer
57 views

How many Turing degrees are there?

So I know there are precisely $2^{\aleph_0} $ Turing degrees, but is there a proof of this somewhere?
2
votes
0answers
76 views

Relationship between Complexity and Computability

As a response to comments,i'd like to put it in an abstract way,hoping this will make things clearer: f is a well-defined function of countably many inputs:f(a1,...,an,...). For a set of n objects {a1,...
1
vote
1answer
54 views

Omega-model of WWKL consisting of random reals

I've been trying to show, as an exercise, that over $\mathrm{RCA_0}$ weak weak Kőnig's lemma (WWKL) does not imply weak Kőnig' lemma (WKL). I've been working on it by constructing an $\omega$-model ...
1
vote
1answer
81 views

non deterministic turing machine for concatenation

Let $L_1, L_2$ decidable languages on deterministic single-tape TM $M_1$ and $M_2$. How can I build non-deterministic TM that decides $L_1L_2$? What should be the formal definition of $\delta$ (the ...
0
votes
1answer
51 views

Can we know the first few digits of Chaitin's constant?

Chaitin's constant ($\Omega$) is a non-computable real number. Intuitively, it is the probability that a random program will halt. In reality, the actual value of $\Omega$ depends on the encoding ...
0
votes
2answers
24 views

Why are recursive sets also recursively enumerable?

Why is this? I'm not necessarily interested in a full proof, but just a quick, simple explanation that makes sense as to why this is.
1
vote
1answer
75 views

Are all computable functions continuous or vice-versa?

A famous result in intuitionistic mathematics is that all real-valued total functions are continuous. Since the requirements for a function to be admitted intuitionistically is that it must define a ...
0
votes
0answers
20 views

Is there a universal Turing machine on arbitrary number of input variables?

I know that for every $n \geq 1$ there is a partial recursive (p.r.) function $\phi^{(n+1)}_{z_n}(e,x_1,...,x_n)$ such that $\phi_{z_n}^{(n+1)}=\phi_e^{(n)}(x_1,...,x_n)$, where $\phi_e^{(n)}$ is the ...
1
vote
1answer
93 views

confusion about decidability

I just read the following sentence: "[T]here is no effective decision procedure for determining whether or not an argument T/X is valid, where T is any subset of PA or RA and X is any sentence." I ...
0
votes
0answers
23 views

equivalent definitions of recursively enumerable sets

In some textbooks, a n-ary set R is defined as r.e iff there's it is a domain of a recursive function. In others, definition is restricted to case n=1 and a set is called r.e. if it is a range of ...
1
vote
1answer
27 views

Characterization of $\Delta^0_0$ (rudimentary) functions

A $\Delta^0_0$, or rudimentary, functions $\Bbb N^k \rightarrow \Bbb N$ is a function whose graph is definable by a bounded formula. Can this class of functions characterized by means of closure ...
0
votes
1answer
18 views

prove this $L$ is not regular?

Consider the language $L=\{a^{n!}\mid n\in\mathbb{N}\}$. I want to prove that $L$ is not regular using the Pumping Lemma. So far i assumed by contradiction that $L\in REG$, so it has a pumping ...