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

23 views

### Examples of problems in second order arithmetic that can only be solved in third order arithmetic

So I was reading about Goodstein Sequences: https://en.wikipedia.org/wiki/Goodstein%27s_theorem where it is given as an example of a theorem that is not decidable in PA but decidable in second order ...
28 views

11 views

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

34 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(...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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?
34 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 ...
29 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). ...
31 views

### Every function that is representable in Robinson arithmetic, $\mathsf{Q}$, is computable
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 ...