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

learn more… | top users | synonyms (1)

1
vote
0answers
87 views

Oracle Turing machine - $E_{\text{TM}}$ and $PCP$.

$$E_{\text{TM}}=\{\langle M\rangle|M\text{ is a TM and $L(M)=\emptyset$}\}.$$ $E_{\text{TM}}$ is undecidable $$PCP=\{\langle P\rangle|P\text{ is an instance of the Post Correspondence Problem with a ...
0
votes
2answers
92 views

An effective enumeration of recursive sets in increasing order

Definition: We call a set recursive if its characteristic function is recursive. Claim: If the set $A\subset\mathbb N$ is recursive then $A=Range(f)$ for some recursive and increasing function. ...
1
vote
1answer
151 views

All infinite recursive sets can be enumerated by an injective function

Definition: We call a set recursive if its characteristic function is recursive. Claim: If the recursive set $A\subset\mathbb N$ is infinite then $A=Range(f)$ for some primitive recursive injective ...
2
votes
1answer
46 views

Reducing A$_\text{TM}$ to REGULAR$_\text{TM}$

We can solve A$_\text{TM}$ problem using REGULAR$_\text{TM}$. Assume $R$ is a Turing machine that decides REGULAR$_\text{TM}$. We construct $S$ to decide A$_\text{TM}$ as follows On input ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
2answers
109 views

Non computable real numbers

A real number $r$ belonging to $[0,1]$ is said to be computable if there is a simple TM such that for each binary encoding of $n$ ($n$ is a natural number), returns the $n$th bit in the binary ...
3
votes
0answers
62 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
1
vote
1answer
40 views

Two indexes $c$ and $b$, such that $Dom(\varphi_a)=\{b\}$ and $Dom(\varphi_b)=\{c\}$

Problem: Assume $\{\varphi_i\}_{i=1}^\infty$ is an effective enumeration of the computable functions. Find two indexes $c$ and $b$, such that $Dom(\varphi_c)=\{b\}$ and $Dom(\varphi_b)=\{c\}$. ...
3
votes
1answer
80 views

On the existence of an injective recursive function such that all its values are also its indexes.

Kleene's second recursion theorem easily yields a self-referential program. What is more, it gives a program $P_a$ that computes any computable function of its index $a$ and its input. But does an ...
2
votes
1answer
58 views

Effective Enumeration of Set when Membership is Semi-Decidable

I have a set $S$, where $x \in S$ is semidecidable, i.e. there is a function $f(\cdot)$ that returns 1 in finite time if $x \in S$ but will not halt if $x \notin S$*. I also have an effective ...
1
vote
0answers
16 views

The $k$-th term in the graded lexicographical order is recursive

I recently constructed a proof that a computable universal function exists for the class of polynomials of $n$-variables. To this end, I adopted the graded lexicographical monomial order. However, I ...
0
votes
1answer
23 views

The universal function for the class of functions defined on a finite set is computable; (Lagrange interpolation polynomials).

Theorem: A computable universal function for the class of functions of $n$ variables exists that are defined on a finite subset of $\mathbb N^n$. Attempt at proof: Each such function is completely ...
1
vote
1answer
62 views

A computable universal function for any countable set of computable functions exists.

Assume $\{f_i:\mathbb N^k\to\mathbb N\}^\infty$ is a countable set of computable functions. Prove that a computable universal function exists for this class. This more general question stems from the ...
0
votes
1answer
40 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. ...
1
vote
1answer
56 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 ...
0
votes
1answer
42 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 ...
0
votes
1answer
60 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 ...
1
vote
1answer
39 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 ...
2
votes
1answer
213 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 ...
0
votes
1answer
46 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 ...
1
vote
0answers
59 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 ...
0
votes
1answer
36 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 ...
0
votes
0answers
59 views

Concatenation, reversal and sum are primitive recursive

Let $\mathbb N^*$ be the language of finite words with alphabet $\mathbb N$. Assume $k:\mathbb N^*\to\mathbb N$ is an effective coding. That is $k$ is a bijection whose length and member functions are ...
1
vote
2answers
99 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. ...
3
votes
1answer
85 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))$. ...
0
votes
1answer
43 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 ...
0
votes
1answer
41 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 ...
0
votes
0answers
34 views

Expressing total functions in a single equation

Suppose $f(x),g(x)$ are total functions. Give a single equation $h$ in terms of $f$ and $g$ using $+,.,$ truncated substitution and the functions $sg$, $\bar{sg}$ $h(x)= x$ if $f(x)=0$ and $g(x)=0$ ...
1
vote
0answers
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 ...
2
votes
0answers
49 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 ...
1
vote
1answer
76 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 ...
0
votes
1answer
62 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)?
2
votes
1answer
82 views

Primitive recursive functions with a restriction on the arity of projections

The set of primitive recursive function is defined inductively, starting with a countably infinite set consisting of the constant zero, the successor and all projections $P^n_i$, with $n \ge 1$ and $1 ...
2
votes
1answer
68 views

Genericity and category

This paper by Ambos-Spies and Mayordomo on the theory of algorithmic randomness introduces the notion of genericity saying that it is based on Baire category while the usual notion of randomness is ...
2
votes
1answer
116 views

If P = NP, then 3-SAT can be solved in P

Prove that if $P = NP$, then there is an algorithm that can find a boolean assignment for a 3-SAT problem in P time if it exists. $P = NP$ only says that we can decide whether a 3-SAT problem is ...
0
votes
1answer
39 views

Prove a language is NP-Complete

$A$ is NP-complete. $B$ is P. $A \cap B = \emptyset $ $A \cup B \neq \sum^{*}$ Prove that $A \cup B $ is NP-complete. How can I prove this ? I think if anything can be P-reducible to A then it ...
0
votes
1answer
50 views

Futamura Projections- Compatibility - Interpreter and Compiler

I've just learnt a week ago in my compatibility class about fotomora. These are three rules/tricks you can do with interpreter and compiler. I'm looking for a bit more information about the subject ...
1
vote
3answers
280 views

Project Euler's Problem Number 88

I am tackling Project Euler's problem number 88, which in a nutshell reads: Let $S_n$ be the set of sequences of natural numbers $(s_1,s_2,...,s_n)$ where $s_1\leqslant s_2\leqslant\cdots\leqslant ...
1
vote
0answers
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 ...
3
votes
1answer
48 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 ...
1
vote
1answer
267 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 ...
1
vote
1answer
51 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 ...
0
votes
0answers
47 views

Proving a function is primitive recursive

Assume $f$, $r$, and $s$ are primitive recursive. Prove that $$h(\overline x,y) = \begin{cases} f(\overline x,y,h(\overline x,r(y))) & r(y)<y \\ s(\overline x,y) & \text{otherwise} ...
0
votes
1answer
125 views

“Nested” recursion preserves primitive recursive functions

Problem: Assume the functions $f$, $\pi$, and $g$ are given. They take one, two, and three arguments respectively. Prove a unique function $h$ exists such that: $$h(0,y)\cong f(y)$$ $$h(x+1,y)\cong ...
0
votes
2answers
127 views

Termination of a Fast Exponentiation problem

Here's the problem I am stuck on. There exists a fast exponentiation program like the following: Given inputs a in the set of all Real numbers, b in the set of Natural numbers, initialize ...
0
votes
1answer
63 views

Is DFA (Deterministic Finite Automata) a kind of predicate?

When I read a book on computation theory, I found a interesting thing: A Language L was defined by a DFA(Deterministic Finite Automata) like this, L = {$\omega$ | the last input of $\omega$ causes ...
3
votes
0answers
110 views

Simplifying Relations in a Group

Let $K$ be the group generated by four elements $x_1,\cdots,x_4$ with relations that any simple commutator with repeated generator is trivial; for example, $[[x_2,[x_1,x_3]],x_3]=1$. As I have asked ...
1
vote
1answer
60 views

Ackermann function and primitive recursiveness

If we define $b_n(m) := a(n,m)$ for all $n$ and $m \in \mathbb{N}$. For which $n$ is the function $b_n$ primitive recursive and for which $n$ it is not a primitive recursive function? Can anyone ...
2
votes
1answer
57 views

Decidable language closed under complement

Why are decidable languages closed under complement? So if L is decidable why is the complement of L also decidable.