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
17 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 ...
7
votes
1answer
230 views
+100

Approximate spectral decomposition

See 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 Hermitian ...
0
votes
0answers
18 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) ...
0
votes
0answers
26 views

Approximate SVD

Let $A$ be a complex matrix. A singular value decomposition (SVD) tells us that $A$ can be written as: $$ A = U \Sigma V^*, $$ where $U$ and $V$ are unitary matrices formed by bases of spans of left ...
0
votes
1answer
23 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
69 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 ...
0
votes
0answers
54 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 ...
2
votes
2answers
22 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 ...
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' ...
3
votes
2answers
50 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
35 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 ...
0
votes
0answers
40 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
46 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
18 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
43 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
63 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
18 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
1answer
32 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 ...
2
votes
1answer
37 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 ...
0
votes
0answers
20 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
0answers
8 views

Showing a function that makes only substitutions in a sequence is primitive recursive?

Show that there is a primitive recursive function $sub(s,c,d)$ such that if $s$ codes a sequence, then $sub(s,c,d)$ is the code for the sequence that results from replacing all occurrences of $c$ ...
1
vote
2answers
31 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 ...
1
vote
0answers
20 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
31 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 ...
1
vote
1answer
103 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
0
votes
0answers
45 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 ...
1
vote
1answer
47 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 ...
3
votes
1answer
224 views

How to show that a function is computable?

Is the following function $$g(x) = \begin{cases} 1 & \mbox{if } \phi_x(x) \downarrow \mbox{or } x \geq 1 \\ 0 & \mbox{otherwise } \end{cases}$$ computable? Please note that $\phi_i(x) ...
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
1answer
26 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
20 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
1answer
43 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
1answer
86 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
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
0answers
44 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 ...
1
vote
1answer
64 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
1answer
35 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
1answer
133 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
0answers
22 views

To find order of an element in group of large size

G be multiplicative group of positive integers less than prime p. a be any arbitrary element of G .Is there any efficient algorithm to find order of a in G?
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 ...
3
votes
2answers
268 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
46 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?
0
votes
1answer
61 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
2answers
21 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.
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 ...
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
26 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 ...
7
votes
1answer
126 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 ...