# Tagged Questions

48 views

### Using diagonal argument to prove that H(x)=μyT(x,x,y) has no total computable extension

Hello everyone just like the title says I want to prove that $H(x) = \mu y T(x,x,y)$ has no total computable extension such that if we had a function $BIG(x)$ that is both total and agrees with $H(x)$ ...
54 views

### Reduction between two languages and a common one

My question is as following : Let $A$ and $B$ be some languages, there exist a language $C$ such that $A\le C$ and $B\le C$, where "$\le$" means "reducible to", so $A\le C$ means there is a mapping ...
48 views

### Prove that [x/y] is a primitive recursive function

Prove that [x/y] is a primitive recursive function using this theorem: If $g(x_1,...,x_n)$ is primitive recursive, then $f(x_1,...,x_n)=\sum^{x_n}_{i=0}g(x_1,...,x_{n-1},i)$ is also a primitive ...
80 views

### computability and uncomputability

1) Suppose $f$ is an increasing function from $\mathbb N \to \mathbb N$ $(i.e., if x\ge y, then \space f(x) \ge f(y)).$ Is there necessarily a program which computes $f$? 2) Suppose $f$ is a ...
64 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 ...
11 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 ...
167 views

### Simultaneous recursion

I have no idea how to even start proving the following theorem: If $f_0, f_1: \mathbb{N}^r \rightarrow \mathbb{N}$ and $g_0, g_1: \mathbb{N}^{r+3} \rightarrow \mathbb{N}$ are primitive recursive, ...
95 views

### Prove domain of partial computable function exists

Prove that there is an n such that $W_n$ = {$2n, . . . , 2n + n^2$} Now I don't know where to start with this question, how can I go about answering it? Would I construct a computable function that ...