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

58 views

### A universal function exists for the polynomials

Problem: Consider polynomials with natural coefficients of $n$ natural variables. Prove a computable universal function exists for this class. Prove that any such function is not a polynomial. ...
66 views

### The history function preserves recursiveness

Starting with an effective coding of the lists of numbers, I recently proved that concatenation of lists is primitive recursive. On the way I used that if a function is primitive recursive, then its ...
53 views

### The representation of the step function is primitive recusrsive

I've been trying to construct a proof that Unlimited Register Machine (URM) computable functions are partial recursive, which follows from the universal function theorem. I could not prove that the ...
71 views

### Mapping natural numbers to rationals

I'm prepping for an exam, and I came across this: $$x_K = \sum_{n\in K} 2^{-n}$$ (K is the Halting problem) Does there exist a computable function $f_x$ : N$\mapsto$Q where these conditions are ...
45 views

### Infinite regular sets

Would it be true that for all infinite regular subsets, each one contains subsets that are not c.e/r.e (countably enumerable/recursively enumerable)? Intuitively this seems true because of sets that ...
798 views

### Show that the language TOT={<M> | M is a Turing Machine that halts with all inputs} is not recursively enumerable nor its complement.

I've been thinking about how to show this but I'm stuck. I'm required to prove this: "Show that the language TOT={#M# | M is a Turing Machine that halts with all inputs} is not recursively ...
81 views

### Computability and the Halting Problem

This is a branch of another problem that I had asked earlier (and was answered). Found here Let the "merge" of two languages L1,L2⊂{0,1}* be: L1⊥L2 = {x0 | x∈L1}∪{y1|y∈L2} Given the diagonal ...
70 views

### Showing particular language is NP-complete

How is FLO NP-complete? Let G be a social network where vertices correspond to people and edges are relationships between people (undirected). Some pairs of people (who are friends) get married. We ...
46 views

### Basic reductions

I'm trying to learn about reductions and I came across this example in my book: Let the "merge" of two languages L1,L2$\subset${0,1}* be: L1$\bot$L2 = {x0 | x$\in$L1}$\cup${y1|y$\in$L2} I think ...
173 views

### Books about Turing machines and undecidability

I need help with finding literature about Turing machine and undecidability. First book I was suggested is Introduction to Automata Theory, Languages, and Computation by Hopcroft, Motwani and Ullman. ...
98 views

### An effective coding of $\mathbb N^*$

Problem: Assume $\Pi:\mathbb N^2\to\mathbb N\setminus\{0\}$ is a primitive recursive coding of the pairs of numbers, that is also a bijection and $(\forall (x,y)\in\mathbb N^2)(\Pi(x,y)>max(x,y))$. ...
72 views

### Computably enumerable and partial functions

I've been tasked with proving, formally or informally, that these conditions of a language A which is a subset of {0,1}* are equivalent statements. I must first show that A itself is computably ...
52 views

### Suppose $f(x)$ is a total computable function. Use minimlization to show that there is a computable function $g(y)$

Suppose $f(x)$ is a total computable function. Use minimalization to show that there is a computable function $g(y)$ with $dom$ $g = im$ $f$ and $f(g(y))=y$ for all $y \in dom$ $g$ I know this then ...
115 views

### Primitive recursive and Turing machines

Can someone give me a hint or the start of a possible proof for the following theorem: A function $f: \mathbb{N}^r \rightarrow \mathbb{N}$ is primitive recursive if and only if there is a ...
85 views

### Eager vs. lazy interpretation of recursive functions

One of the ways of defining the set of recursive functions is to define first a language $L$ by induction in the following way: $\mathsf{Z}^1 \in L$; $\mathsf{S}^1 \in L$; $\mathsf{P}^n_k \in L$ for ...
250 views

### Is definition by cases a primitive recursive function?

Primitive recursive functions can simulate every single step of a Turing machine. In order to prove this, one has to see that a function defined by state table is primitive recursive. Simply ...
158 views

### Algorithm for valid 3 coloring.

If we have P=NP, how can I show that a polynomial algorithm exists that given any 3 colourable graph produces a valid 3 colouring (no two adjacent vertices share the same colour)?
165 views

21 views

### Is the language that consists of machine configurations whose language is a subset of even palindromes semi-decidable?

Let $PAL = \{ww^R\ | w\in\{0,1\}^*\}$. Then let $A = \{\langle M\rangle \ | \textit{M is a Turing Machine and } L(M)\subseteq PAL\}$ Is A semi-decidable (Turing recognizable or recursively ...
86 views

### Proof of easy direction of van Lambalgen's theorem from Downey & Hirschfeldt

This question regards the "easy" direction of van Lambalgen's theorem as proven on page 258 of Downey & Hirschfeldt's Algorithmic Randomness and Complexity. Specifically, in their proof of the ...
417 views

### Finding the upper bound for this recursion: $T(n) = T(\log n) + O(\log n)$

$T(n) = T(\log n) + O(\log n)$ So I came up with this: $T(n) \le T(\log(\log n)) + C\log n + C\log(\log n)$ And then: $T(n) \le C(\log n + \log(\log n) + \log(\log(\log n)) + ... )$ And so my ...
65 views

### Course-by-values recursion

I have many questions in my textbook of the kind: Assume $g$ is primitive recursive and assume $f(0)=c_0,\dots,f(n-1)=c_{n-1}$ $f(x+n)=g(<f(x),\dots,f(x+n-1)>)$ Prove that $f$ is primitive ...
275 views

61 views

In the theory of computation, one mainly deals with maps $\Sigma^*\rightarrow\Sigma^*$. To discuss computation on other sets $X$ than $\Sigma^*$, one fixes a representation $\gamma:\Sigma^*\... 1answer 227 views ### Proof of undecidability of$FINITE_{\text{TM}}$and$USELESS_{\text{TM}}$I came across these 2 problems about proving of undecidability of languages:$1$.$FINITE_{\text{TM}} = \{\langle M \rangle | M \text{ is a Turing machine and } L(M) \text{ is a finite language} \}$. ... 1answer 720 views ### Why doesn't diagonalization prove that integers are not countable? I understand how Cantor's diagonalization argument works with respect to disproving that a bijection between integers and real numbers can exist. What I don't get is why the same reasoning doesn't ... 1answer 179 views ### Arithmetic Hierarchy problems Is$\Sigma^{0}_n$closed under intersection? I think yes m I correct? Let$L_1$be an$\Sigma^{0}_1$complete language, and$L_2$be a$\Pi^{0}_1$complete language, such that$\emptyset \neq L= L_1\...
By Matiyasevich, every computable function has a diophantine representation. I am wondering if there is a general way to represent a simple iterative for loop. Specifically: Let $f(x)$ be any ...