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)

2
votes
0answers
25 views

probabilistic method for random algorithm that decide language membership

$A$ is an random algorithm that decide membership to language $L$. It outputs on input $x \in \{0,1\}^n$ and a string of random bits $r \in \{0,1\}^n$ in the following way: $if \{x \in L\} \Rightarrow ...
19
votes
5answers
769 views

How can Busy beaver($10 \uparrow \uparrow 10$) have no provable upper bound?

This wikipedia article claims that the number of steps for a $10 \uparrow \uparrow 10$ state (halting) Turing Machine to halt has no provable upper bound: "... in the context of ordinary ...
5
votes
2answers
96 views

Meta proof-searching

Suppose you have a particular theory (ex: $ZFC$) in which you want to prove a statement $\phi$. One can attempt to find a proof of $\phi$ that can be verified, but another tactic can be to find a ...
1
vote
2answers
71 views

Notation for representing ANY number?

i'm working on a mathematics/number-manipulation program, and i was wondering if you could practically have a representation that could holds the value of any number. This would need to include ...
0
votes
1answer
32 views

Does this certain modular property hold for functions on recursive ordinals?

Let $f$ be a function with the following properties. 1) The domain and codomain of $f$ are the recursive ordinals. 2) $f$ is nondecreasing. 3) The set of fixed points of $f$ is unbound. ...
0
votes
1answer
43 views

Do all computable functions on ordinals satisfy this certain modular property?

Consider the following property of a non decreasing function $f$ whose domain and codomain are each the set of ordinals less than the Church-Kleene ordinal, and whose set of fixed points is unbound. ...
1
vote
1answer
37 views

Can every decision algorithm be expressed as a first order predicate?

Suppose we have a decision algorithm over, let's say, the set of natural numbers. Can this algorithm always be expressed as a first order predicate A(x) over the natural numbers, using only the ...
1
vote
1answer
31 views

By what measure does the busy beaver function grow faster than any computable function?

It has been proven that the busy beaver function grows faster than any computable function. But I wouldn't think that speed of growth is well-defined. What is the definition? Is there some index?
-1
votes
0answers
24 views

The relativised Church–Turing thesis

Barry Cooper states in his computability theory "The relativised Church–Turing thesis" on page 142 as follows: All formalisations of "$B$ computable from $A$" which are sufficiently reasonable ...
0
votes
1answer
14 views

Is $\{\langle M \rangle \mid \exists P \;\text{(p is polynom)}\; \forall w\; \text{M(w) halt with less than p(|w|) steps}\} \in RE$?

Is $L=\{\langle M \rangle \mid \exists P \;\text{(p is polynom)}\; \forall w\; \text{M(w) halt with less than p(|w|) steps}\} \in RE$? I can prove that $L \notin coRE$, but I don't know what to do ...
0
votes
1answer
12 views

Is $\{\langle M \rangle \mid \exists K \forall w\; \text{M(w) halt with less than K steps}\} \in RE$?

Is $L=\{\langle M \rangle \mid \exists K \forall w\; \text{M(w) halt with less than K steps}\} \in RE$ ? I can prove that $L \notin coRE$, but I don't know what to do about $RE$... ($L \in coRE \...
4
votes
0answers
96 views

How are weakly universal Turing machines actually defined?

For what I know, the definition of a universal Turing machine is something along the lines of the following (of course, details might vary from source to source): A Turing machine $M$ is called ...
0
votes
1answer
19 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
1answer
11 views

Existence of a injective and recursive(but not primitve recursive) fucntion that has a primitve recursive inverse.

The Question is as follows: For a one-to-one function f:N -> N, it's inverse is defined as: $$ f^{-1}(n) = \begin{cases} m+1 & \text{if }f(m)=n \\ 0 & \text{if } \forall m\in\mathbb N:...
3
votes
1answer
124 views

Is my logic here correct? Primitive recursion and diagonalization proof

I'm trying to understand diagonalization as it applies to proving that not all total functions are primitive recursive functions. For example, say that we enumerate all primitive recursive functions ...
3
votes
0answers
32 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 ...
0
votes
1answer
34 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 ...
5
votes
1answer
137 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
40 views

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.
1
vote
2answers
165 views

Sequences of a computable function

Is there any computable function $f(n)$, which given any integer $n$ has been proven to return either $0$ or $1$ in finite time, and for which the statement "$f(1), f(2), f(3),\ldots$ contains ...
0
votes
1answer
23 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
22 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
0answers
33 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
19 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
67 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 ...
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?
1
vote
2answers
38 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 ...
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 (...
-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 ...
1
vote
1answer
30 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
1answer
19 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 ...
3
votes
2answers
137 views

Is there a Turing Machine that can distinguish the Halting problem among others?

Can there be a Turing machine, that given two oracles, if one of them is the Halting problem, then this machine can output the Halting problem itself? Clearly, if the first oracle is always the ...
2
votes
0answers
61 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 ...
7
votes
2answers
129 views

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal?

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal? If so, is there a nice proof of this?
0
votes
1answer
44 views

Dominating function easier to understand

Is there a pair of function $f$ and $g$ (both $\mathbb{N}\rightarrow\mathbb{N}$ and definable in the language of first-order Peano arithmetic) such that asymptotically $f$ dominates $g$, and $f$ has ...
0
votes
1answer
37 views

A subset of $ \mathbb{N}$ is recursively enumerable iff it is the range of some recursive function from $\mathbb{N }$ to $\mathbb{N}$.

I know how to prove the converse of the statement, but given a recursively enumerable set, I don't know how to find such a recursive function. Also, how to prove that the function can be chosen as ...
0
votes
1answer
14 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
70 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 ...
1
vote
2answers
92 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
36 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
28 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
34 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 ...
0
votes
1answer
33 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
28 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 ...
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 ...
1
vote
1answer
31 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?