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)

-5
votes
2answers
51 views

Inverting surjective functions as proof that P≠NP [on hold]

Edit: I've found a more appropriate StackExchange site to ask this question on, thank you.
0
votes
0answers
14 views

Converting Fourier Series into elementary expression

If a Fourier series corresponds to an elementary function, is there any algorithm that will produce the elementary expression of this function?
1
vote
1answer
30 views

Multiplicity of roots of polynomial with rational coefficients decidable?

From the standpoint of intuitionistic logic, multiplicity of roots of generic polynomial is uncomputable due to the inability to compare two real numbers. Even though the roots themselves are ...
3
votes
0answers
24 views

Can all computable numeric functions on church numerals in ski-combinator calculus be expressed using only completely evaluated terms?

Let a term in ski-combinator calculus be called "complete" if every primitive is partially applied (so all S's are applied to at most two arguments, all K's to at most 1, and all I's are not applied). ...
0
votes
0answers
136 views

Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?

In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computability theory, I asked: we treat all inputs and intermediate results and final outputs as ...
2
votes
2answers
60 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
33 views

Every function that is representable in Robinson arithmetic, $\mathsf{Q}$, is computable

I am reading through the proof of this theorem, in particular the one presented in the Open Logic project, where it appears as Lemma 20.3 currently. The definitions in this text are as follows: A ...
10
votes
4answers
352 views

Countable choice and term extraction

The constructive Axiom of Countable Choice (ACC) is widely accepted due to its computational content. It states that: $$ \forall n\in \mathbb{N} . \exists x \in X . \varphi [n, x] \implies \exists f: ...
1
vote
1answer
100 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 ...
11
votes
1answer
420 views

Approximate spectral decomposition

A detailed attempt below. Wanted: complex analysts I am interested in effective and constructive computations for finding approximate spectral decompositions in some suitable format. Namely, let $A: ...
1
vote
0answers
26 views

Interpolating discrete data with completely monotone analytic functions

Suppose we have a positive integer $n$ and a finite list of real numbers $\{a_1,\,a_2,\,\dots,\,a_n\}$. We want to find a real-analytic function $f:[1,n]\to\mathbb R$ such that $f(m)=a_m$ for all ...
0
votes
1answer
15 views

Demonstrate that a language is semi-decidable

I need some help to demonstrate that this set below is decidable, semi-decidable, or undecidable. Here's the set: H = {p| |Images(fp)| >= 10} explanation: an ...
1
vote
1answer
32 views

Infinite recursive languages and infinite regular languages.

Could the following statement be correct? "Every infinite recursive language has as a subset an infinite regular language."
1
vote
0answers
34 views

Non-computable infinite subsets

Is there a computably enumerable set $A$ such that every infinite subset of $A$ is noncomputable? I think that it's a set $K = \{n\ \ |\ \ U(n,n) \text{ is defined}\}$ (which is noncomputable, ...
1
vote
0answers
24 views

(Semi-)decidable sets and infinite sets

I’m confused about the notion of (semi-)decidable sets in the context of transition systems. Suppose we have some transition relation $\rightarrow$ over some infinite set of states $\Sigma$. Let’s ...
1
vote
1answer
27 views

Primitive recursive functions definition (understanding “composition” and “primitive recursion”)

$\newcommand{\N}{\Bbb{N}}$ I am trying to understand the concept of primitive recursive functions, using the definition in the Open Logic Text (Definition 14.3): The set of primitive recursive ...
0
votes
0answers
22 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 ...
-1
votes
1answer
15 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 ...
22
votes
8answers
3k views

There is a subset of positive integers which no computer program can print

It's said that a computer program "prints" a set A ($A \subset \mathbb N$, positive integers.) if it prints every element in A in ascending order (Even if A is infinite.). For example, the program can ...
0
votes
1answer
24 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$? ...
2
votes
2answers
85 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
31 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
20 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
1answer
27 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
73 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
57 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
24 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
52 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
38 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
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
47 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
21 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
45 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
83 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
20 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
35 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
40 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 ...
1
vote
2answers
35 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
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
35 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
110 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
47 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
51 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
228 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
27 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
21 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?