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)

0
votes
1answer
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. ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
2
votes
2answers
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. ...
4
votes
1answer
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))$. ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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)?
2
votes
1answer
165 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
95 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
339 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
53 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
162 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 ...
2
votes
3answers
726 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
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 ...
3
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
275 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 g(...
0
votes
2answers
150 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
111 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
158 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
91 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
76 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.
1
vote
1answer
89 views

Generating a context free grammar

How do I generate a context free grammar for a language $$\left\{a^ib^jc^k:i=j\text{ or }j=k,\text{ and }i,j,k\ge 0\right\}\;?$$ Thanks.
2
votes
1answer
183 views

Is the Church-Kleene Ordinal describable with Kleene's $O$?

Kleene's $O$ is an ordinal notation system that uses certain natural numbers to represent transfinite ordinals. It is a recursive notation system (although it's not decidable whether a number ...
1
vote
1answer
44 views

Is recursive join of a sequence of low sets also low?

A set $A$ is low when $\deg(A)'\leq 0'$. Suppose we have a sequence of low sets $(A_i)_{i\in\omega}$ such that for every $n\in\omega$ we have $$\deg(\bigoplus_{i<n}A_i)'\leq 0'$$ Let $A=\...
4
votes
1answer
95 views

A function agreeing with a primitive recursive function at all but finitely many points is primitive recursive

Show that if $f:\mathbb{N} \rightarrow \mathbb{N}$ is primitive recursive, $A \subseteq \mathbb{N}$ is a finite set, and $g$ is a total function agreeing with $f$ at every point not in $A$, then $...
4
votes
1answer
171 views

Is ordinal analysis a non-recursive project?

A recursive ordinal is an ordinal that is the order-type for some recursive relation (i.e. a recursive well-ordering). We can represent recursive ordinals as natural numbers using Kleene's $O$, an ...
4
votes
2answers
242 views

context free grammar problem

$L$ is the context free grammar over $\{a, b\}$ $S \rightarrow aSb \; | \;bR \; |\;Ra$ $R \rightarrow bR \;|\;aR\;|\;\epsilon$ Briefly describe this CFG with English sentences and prove your ...
0
votes
1answer
310 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, ...
0
votes
2answers
74 views

context free grammar design

Design a context free grammar and PDA for the following language. $$\Sigma = \{0,1\},\qquad L = \left\{uv \mid u \in \sum^{*} \;v\in \sum^{*}1\sum^{*} \text{ with }|u| \geq |v| \right\}$$ I'm not ...
0
votes
1answer
71 views

Enumerating relations that are true infinitely often

Let us concentrate on relations on natural numbers. Is it possible to enumerate all computable unary relations that are true infinitely often? I would guess no but I can't see a direct way to prove it....
5
votes
0answers
322 views

How is the Kleene normal form theorem for $\Sigma^1_1$ relations proved in RCA0?

All of the following concerns Simpson's Subsystems of Second Order Arithmetic (2nd ed.). In the notes subsequent to lemmas VII.1.6 and VII.1.7 (pp. 245–246), Simpson remarks that both lemmas are ...
5
votes
3answers
1k views

Prove that transcendental numbers exist: Are there less paniful ways of doing it?

I've found this exercise on Boolos' Logic and Computability: A real number $x$ is called algebraic if it is a solution to some equation of the form: $$c_{\small d}x^{\small d}+c_{\...
2
votes
0answers
61 views

Why is positional number system natural?

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^*\...
1
vote
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} \}$. ...
4
votes
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 ...
0
votes
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\...
3
votes
1answer
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 ...
3
votes
1answer
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: (...