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

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 ...
170 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 ...
114 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 ...
243 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 ...
157 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 ...
414 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

58 views

### A diophantine program for a basic For Loop

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

### Can this simple functional language be simplified further without losing any computational power?

Here is a definition of a very simplistic programming language (it is not Turing complete). Input to a function is any natural number. The following functions are primitive to the language: (...
130 views

### Decidable & Recursive predicates

Let $C$ be a decidable predicate in the language of arithmetic HA, that is $$\vdash (\forall \underline x)\: C(x) \vee \neg C(x).$$ $C$ is recursive if there exists a computable characteristic ...
250 views

### How does 3-sat work in laymen's terms?

I know only basic math like so: (+,-,x,\,). And I studied a little bit of programming up to the point of knowing a little bit about Boolean values.I desperately want to understand the 3-sat question ...
63 views

### Partially correct algorithm for a decidable problem

$D$ is decision problem whose inputs are the natural numbers. Suppose $A$ is an algorithm to solve $D$ in which we know that it is: partially correct for all inputs halts on all inputs >= 1000. ...
114 views

### Looking for counterexamples where the output of a computable function always has a computably checkable property, but PA cannot prove this

Suppose we have a computable function $f$, say over the naturals, and a decidable set $S$ of naturals, such that $f(x) \in S$ for all $x$. In this case, for any specific $x$, there is some specific ...
89 views

### Why SKI when SK is complete

Why people talk about SKI calculus when S and K combinators can be used to create any other combinator including I?
Let $f(x \, | \, y_1, \dots, y_n)$ be a Diophantine polynomial that generates the Diophantine set $F$. By Matiyasevich, the set $F^*$ (Kleene star of $F$) is also Diophantine. My question: how can ...
### Showing the Rec is $\Sigma_3^0$-complete
In Soare's Computability Theory and Applications, he gives a very quick proof that the following set is $\Sigma_3^0$-complete: $$\text{Rec} := \{e \mid W_e \text{ is recursive}\}$$ It's fairly ...