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
0answers
20 views

Online Encyclopedia of continuous and/or computable real valued functions?

Background: Oeis OEIS, the online encyclopedia of integer sequences tabularizes functions from the natural numbers to the integers. It looks like most sequences they list are computable. Some are ...
2
votes
0answers
114 views

Asymptotic bound to all computable functions lower than the Busy Beaver function

The busy beaver function $BB$ asymptotically bounds any computable function. It is easy to show that there are lower bounds, for example, $log(BB)$. Is there a function $f$ that asymptotically bounds ...
0
votes
1answer
20 views

Does the recursion theorem give practical means of constructing the indices mentioned in it?

I'm going through a textbook and the recursion theorem was introduced. The proof is a bit all over the place and kind of hard to follow so I thought I'd ask my question here. The theorem, as stated in ...
0
votes
0answers
16 views

Primitive recursive function, constructing a proof

I've came upon an example in the book that is not that clear to me. The disparity function is proved to be primitive recursive in the following way: $$disparity(x_0,x_1)=(x_0-x_1)-(x_1-x_0) = add(...
0
votes
0answers
21 views

Define primitive recursive function

(it's not homework, this question is supposed to be supplementary material for students to understand the lecture material better!) I have specific function that needs to be proved to be primitive ...
0
votes
1answer
36 views
+50

A question about many-one reducibility of two sets

We want to show that $ \big\{x:W_{x}$ is finite }$=Fin \leq _m Cof=\big\{x : W_{x}$ is cofinite}. But I really have not any idea. Would be grateful for your help.
0
votes
0answers
31 views

How to show that a function is primitive recursive?

If we have a function $g ~:~ \mathbb{N}^{k+1} \rightarrow \mathbb{N}$ which is primitive-recursive. How to show that the function $f ~:~ \mathbb{N}^{k+1} \rightarrow \mathbb{N} $ with $f(x_1, ~...~, ...
0
votes
1answer
18 views

the set of extendable p.c. functions is not N

Show that the set $Ext:= \big\{x\in N : \varphi_{x}$ is extendable to a total recursive function $\big\}$ is not equal to the set of non negative integers $N$. Would be grateful for your help.
0
votes
2answers
66 views

Turing Machine halts for at least $1024$ strings as input [closed]

Consider the language $$L = \{\text{"}M\text{"} \mid \text{Turing Machine } M \text{ halts for at least }1024\text{ input-strings}\}.$$ Is L a recursively enumerable language? My answer is no based ...
-1
votes
1answer
44 views

Injectivity in functions

Sorry, I know that it has to be a very simple problem, but I'm frustrated because of it. Let $f,g:\mathbb{N}^3→\mathbb{N}f$: $f(x,y,z)=3^x⋅5^y⋅7^z$ and $g(x,y,z)=3^x+5^y+7^z$ Prove that: $1.f$ is ...
0
votes
1answer
54 views

Turing Machine & Recursively enumerable languages. [closed]

Suppose Turing Machine(TM) M and language L. L = { "M" | M has as input strings which $∈$ $\{0,1\}^{*}$ and terminate at a maximum of $512^{512}$ steps} Is L a recursively enumerable language?
0
votes
1answer
38 views

Prove a relation is primitive recursive, x is prime?

Is $\{x \in \mathbb{N}| \mbox{ x is prime}\}$ primitive recursive? Hello, $x \in \{x \in \mathbb{N}| \mbox{ x is prime}\} $ if and only if $ \forall y : y \le x \Rightarrow (y=1 \vee y=x \vee \neg (...
0
votes
0answers
22 views

reductions from $SAT$ to $DSAT$ and $DSAT$ to $SAT$

can someone help me to prove or disprove the 3 claims about reductionsbetween $SAT$ and $DSAT$, where: $SAT=\{<\phi> | \text{$\phi$ is bolean formula in $CNF$ and there is an interpretation ...
1
vote
1answer
29 views

What does it mean to say that an automaton construction is “effective”?

Let $L, K \subseteq X^{\ast}$ be languages, then we set $$ K^{-1}L := \{ u \in X^{\ast} \mid vu \in L \mbox{ for some } v \in K \} = \bigcup_{v\in K} v^{-1}L $$ with $u^{-1}L := \{ w \in X^{...
0
votes
0answers
25 views

What is the proof that boolean circuit can be arranged as alternating OR and AND gates

In circuit complexity, a branch of compuatation comlexity theory, a theorem is that any boolean circuit can be written equivalently as a hierarchical structure, in which the first layer consists of OR(...
1
vote
2answers
37 views

What is a totally defined partial recursive function?

Alright, so I've always thought that a partial function was a function from $A$ to $B$ whose domain is only a subset of $A$. A total function, on the other hand, I took to be a function whose domain ...
1
vote
1answer
17 views

Help With a proof involving the Ackermann function!

So, I'm continuing on with this computability text by Cutland, and I've reached the Ackermann function. Cutland says he will give a more rigorous proof that the function is computable later on, but ...
2
votes
0answers
57 views

Is there a “nice” “constructive” field of numbers?

I am wondering about this. I've had some interest in “constructive” mathematics, although also some rather strong opinions against those who want to insist that everything else is “wrong” in favor of ...
0
votes
1answer
13 views

Decidability of quantifier-free formulae in Peano- and True Arithmetic

It is well-known that validity in Peano Arithmetic is undecidable. It is less well-known that validity is already undecidable in True Arithmetic (the theory of the standard model of Peano Arithmetic). ...
0
votes
0answers
23 views

Computability: SAT Formula with Fixed Number of Clauses

Define $SAT_{2016} = \{\psi | \psi$ is a CNF formula with at most $2016$ clauses$\}$. Assuming $P \neq NP$, is $SAT_{2016}$ NP-complete? Since the number of literals in each clause isn't bounded, it'...
3
votes
1answer
68 views

explicit upper bound of TREE(3)

TREE(3) is the famously absurdly large number that is the length of a longest list of rooted, 3-colored trees whose $i$th element has at most $i$ vertices, and for which no tree's vertices can be ...
0
votes
1answer
26 views

What are “definable integer sequences”

According to Wikipedia, An integer sequence is a definable sequence, if there exists some statement P(x) which is true for that integer sequence x and false for all other integer sequences. ...
2
votes
1answer
33 views

Countable State Automata

Consider an automaton with a countably infinite number of states. This machine could, given it's current state and a symbol from the input alphabet, move to another arbitrary state in a finite amount ...
1
vote
2answers
91 views

How large must $S(5)$ be at least , if it is not $47,176,870\ $?

See here : https://en.wikipedia.org/wiki/Busy_beaver for more details about the maximum-shifts-function It is said that about $40$ machines with $5$ states have unknown status (it is not known ...
1
vote
1answer
35 views

A Question about Computable Functions

Barry Copper states following in his Computability theory book which I have a question about them. Exe.4.5.1: Show that if $\varphi_e(x) \downarrow $ is a computable relation, then so is ...
0
votes
1answer
26 views

Determine whether a language belong to R,RE\R,coRE\R or other

For the following language, determine to which class it belongs $$L_3=\left\{\langle M\rangle\Big\vert|\langle M\rangle|\le 2016\text{ and M is a TM that accepts }\varepsilon \right\}$$ I've ...
0
votes
0answers
27 views

Are these functions computable - Understanding computable functions

There is a theorem in computability theory which states: B.Cooper: If $A\subseteq N$ is computable, then $A$ is also computably enumerable. In the proof of this theorem -which is an ...
1
vote
1answer
29 views

What is the slowest growing function that is total but not primitive recursive?

For what I have in mind is the Ackermann-Buck function. If there isn't a slowest growing function do you have examples of other function slower growing than Ackermann-Buck's function?
0
votes
1answer
25 views

A Question About Recursive Functions

We want to find a recursive function $f(x,y)$ in order to have this equality: $$ \mathbf \varphi_{f(x,y)} = \varphi_x + \varphi_y$$ I know we should use "s-m-n" theorem, but I can't find the ...
0
votes
0answers
15 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
33 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
27 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). ...
1
vote
0answers
27 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 $m\...
0
votes
1answer
20 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
37 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
37 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, $U(...
0
votes
1answer
37 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 ...
1
vote
0answers
26 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
29 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 ...
-1
votes
1answer
17 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
25 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
67 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
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$? ...
1
vote
1answer
120 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
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
33 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
30 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
27 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 ...