# Tagged Questions

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).

25 views

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 ...
19 views

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 ...
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 ...
34 views

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.
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 ...
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?
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 ...
38 views

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(...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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). ...
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'...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...