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)

2
votes
0answers
118 views

$n^{\text{th}}$ digit of $\sqrt{2}$ decimal representation is primitive recursive function

An exercise from Maltsev's "Algorithms and recursive functions". Problem: Let $\sqrt{2} = a_0,a_1a_2\dots a_n\dots$ be the decimal representation of $\sqrt{2}$. Show that the function $f(n) = a_n$ ...
0
votes
1answer
93 views

Partial / Total / Primitive recursive functions and recursive enumerability

After having compiled several sources from handbooks or the web, and read some answers posted here, I'm still confused with the question of non recursive enumerability of total recursive functions, ...
1
vote
0answers
27 views

Question about Computability

Q:Suppose $U(n,x)$ is Gödel Universal Function, show that there is $n$ such that $U(n,x)=n+x$ for all $x$ I did some proof but I am mot sure if I am right. Let's consider a computable binary function ...
0
votes
1answer
43 views

show that inverses $\pi_{1},\pi_{2}$ are recursive?

show that one can define inverses $\pi_{1},\pi_{2}$ for $ \langle.,.\rangle$ with$\pi_{1}(\langle m,n \rangle)=m,\pi_{2}(\langle m,n \rangle)=n\ \ \forall n,m$ wich are also recursive?
3
votes
1answer
63 views

Is there a recursive injective and surjective function f:N→PRF?

It is well known and easy to see that it is possible to effectively number Turing Machine codes. That is, there is an injective and surjective recursive mapping $g:\mathbb N\to {\rm TM}$: each Turing ...
1
vote
7answers
250 views

Text books on computability

I collected the following "top eight" text books on computability (in alphabetical order): Boolos et al., Computability and Logic Cooper, Computability Theory Davis, Computability and unsolvability ...
1
vote
0answers
44 views

It is undecidable if The Intersection between Context Free Language and Context Sensitive Language is the empty set

I'm trying to show that the following problem is undecidable: The intersection between a Context Free Language (CFL) and a Context Sensitive Language(CSL) is the empty set. I know that is undecidable ...
0
votes
1answer
31 views

Proving non-regularity of a language

How can I prove $L = (01^n2^n | n\geq 0)$ is not regular? Would it be sufficient to say that $01^p2^p$ is in $L$ and by pumping lemma, $01^p2^p$ can be written as $xyz$ such that $|y|>0, ...
3
votes
1answer
167 views

Undefinable Real Numbers

Disclamer: I'm sure my definition of "definable" may be different than the/a established mathematical one, I am more than interested in learning why/how this is so, but that is not my question Part ...
2
votes
1answer
39 views

Non-decidable $\Pi^0_1$ (effectively closed) classes

Are there non-decidable $\Pi^0_1$ (effectively closed) classes? According to a draft of Effectively closed sets by Cenzer and Remmel, the class $$ P = \{ 0^n1^\omega \mid n \in B\} $$ is a ...
0
votes
0answers
102 views

Proving the intersection and union of two simple sets is simple.

Question: Suppose $A$ and $B$ are simple. Prove that $A \cap B$ is simple and $A \cup B$ is either simple or cofinite. I need to verify that $A \cap B$ and $A \cup B$ are computably enumerable ...
2
votes
0answers
90 views

Challenge on Some Definition on Formal Language & Recursive & Automata

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. Suppose $\Sigma$ be an arbitrary finite alphabet. I summarize my inference: a) Each arbitrary Language on ...
1
vote
1answer
29 views

Gathering nonconsecutive 1's by a Turing machine

S. Barry Cooper comments his output convention for $\mathbb{N}\rightarrow\mathbb{N}$ Turing machines like this: Outputting $n$ as $n$ possibly nonconsecutive $1$'s is very natural. [...] We can ...
0
votes
2answers
146 views

Input and output of a Turing machine

For some machine models of computation there is no question what their input and output is: it's just the contents of some specific "cells", e.g. on a "tape" isomorphic to $\mathbb{N}$. Consider for ...
0
votes
0answers
59 views

Existence of a basis in constructive vector spaces

As I was trying to review forgotten knowledge on Vector Spaces in wikipedia, I read that the existence of a basis follows from Zorn lemma, hence equivalently from the axiom of choice. Actually, the ...
0
votes
1answer
96 views

What mathematical structure best entails self-modifying programs?

If a program description can be represented as a sequence, then what is the best structure to entail program descriptions which self-modify? There must exist a relationship between the structure in ...
1
vote
1answer
34 views

Show that whether or not an arbitrary Turing machine ever executes a particular one of its instructions is unsolvable

Show that whether or not an arbitrary Turing machine ever executes a particular one of its instructions is unsolvable. (This is the same as the problem of detecting unreachable code in a program.)
0
votes
1answer
24 views

What do $A \upharpoonright x$ and $\mu s \ge x$ denote?

I am reading Computability Theory by Cooper and I do not understand the notation in the definition on the page 230: Let $\{A^s\}_{s \ge 0}$ be a $\Delta_2$-approximating sequence for $A \in ...
1
vote
0answers
69 views

An algorithmic approach to constructing the real numbers

To specify a real number, we can describe a rule which, given any rational number, tells you whether it's Too Big or Too Small. The rule should be self-consistent, in the sense that if $a$ is Too Big ...
1
vote
0answers
25 views

Decidability involving functions

I'm trying to figure out how to resolve this exercise. $$ \Sigma = \{a,b\} $$ is a set while $$ \mathcal{P}(\Sigma^*) $$ is the partition of sigma star. I have a function f: $$ f: ...
1
vote
1answer
19 views

An $n+1$-c.e. set which is not $n$-c.e.

A set $X\subseteq \mathbb{N}$ is $n$-c.e. if there is a total recursive guessing procedure $g(x,s)$ so that $$ g(x,0) = 0,\ \lim_s g(x,s) = X(x) $$ and the number of times $g$ changes its mind on a ...
0
votes
1answer
56 views

Why is this relation recursive?

A relation $R \subset \mathbb{N}^d$ is called recursive if there exists a primitive recursive function f with $$ (x_1 ,\dots,x_d) \in R \Leftrightarrow f(x_1,\dots,x_d)=0.$$ In Kurt Gödel's article ...
1
vote
1answer
51 views

Is the function $f(n)=\begin{cases} 0,& \text{If $CH$} \\ 1,& \text{If $\lnot CH$} \end{cases}$ $\mu$-recursive?

Using a Turing machine model of computation one can show that the function $f:\mathbb{N}\rightarrow \mathbb{N}$, given by: $$f(n)=\begin{cases} 0,& \text{If $CH$} \\ 1,& \text{If $\lnot CH$} ...
0
votes
1answer
58 views

countable subset of surreal games

Surreal numbers are the largest possible structure to have a complete order. Games are an extension of the Surreals which only admits a partial order. Along with being larger, smaller or equal to each ...
2
votes
3answers
93 views

Showing that a certain recursive set cannot exist?

I'm having a lot of trouble with problem 17.2 of Computability and Logic (Boolos, Burgess, Jeffrey). Here's the problem: Let $T$ be a consistent, axiomatizable theory (in the language of ...
0
votes
1answer
109 views

Turing Machine Problem

We know, A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules I Draw a TM for input $x=(0+1)^*$ i want to implement ...
2
votes
1answer
206 views

Turing machines that compute $\pi$

For each $K > 0$ there is a brut force Turing machine $\pi_K$ that "computes" the first $K$ digits of $\pi$ starting on the blank tape (all $b$s) with $K+1$ states $S \in \mathsf{S} = ...
0
votes
0answers
55 views

Arithmetic Turing machines

Consider the family $T_{1}$ of Turing machines with two tape symbols $b,1$ ($b$ the blank symbol). The family $T_{1}$ is Turing complete. Identify the tape with $\mathbb{Z}$ and let $0\in \mathbb{Z}$ ...
0
votes
1answer
80 views

infinitely long input for a turing machine

I have a question about Turing machines. Is it allowed to give them infinitely long input? Can I give a Turing machine for example all of natural numbers as input?
1
vote
0answers
59 views

Proof that Finite Turing Machine is reducible to Regular Turing Machine

I know that Finite Turing Machine and Regular Turing Machine are undecidable through Rice's theorem, but I may find a reduction among them? Finite TM = {< M > | L(M) is finite on {a}} Regular TM ...
3
votes
2answers
44 views

Number of $1$s in the binary representation of $n$

Trying to define the function $b(n)$ which counts the number of $1$s in the binary representation of $n$ arithmetically I came up with the following definition: $$b(n)=m :\equiv (\exists k_1\dots ...
0
votes
1answer
37 views

TOTAL is not Recursively Enumerable

$\overline{HALT}=$ { (M, w) : M does not halt on w } $TOTAL=$ { M : M halts on every input } The following is the proof from Hopcoft that TOTAL is not R.E. Let R(x) be the following machine: ...
-1
votes
1answer
94 views

Countable Set & Formal Grammar

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. I try to summarize my though. I think the following proposition is true. suppose $\Sigma$ is arbitrary ...
2
votes
1answer
57 views

Binary representation of real numbers without dots

How can I represent a real number using only 0's and 1's? I do not want to use any extra symbol like '.' to separate the integer part and the mantissa.
1
vote
1answer
95 views

In general, are subsets of recursively enumerable sets recursive sets?

I recently became interested in the solution to Hilbert's tenth problem, in reading about the succession of results that lead up to the proof I came across the notion of recursive sets and ...
0
votes
1answer
222 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
4
votes
2answers
199 views

What if a conjecture were provably unprovable?

Suppose we found a proof that "The Twin Prime Conjecture cannot be proven", without any conclusion as to the conjecture itself being true or false. Is it then possible for the conjecture to be true? ...
9
votes
2answers
236 views

The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...
0
votes
1answer
29 views

Algorithm that takes input desc. of two PDAs and outputs intersection of langs. recognized by two PDAs

Does there exist an algorithm which takes as input the descriptions of two pushdown automata, $P1$ and $P2$, and prints the description of another pushdown automaton which recognizes the intersection ...
0
votes
1answer
25 views

Deciding TM which fails to halt whenever the length of its input string is a prime number

I have the following Statement: "A TM called $A$ which fails to halt (i.e runs forever) whenever the length of its input string is a prime number, and eventually halts for all other input strings" ...
-1
votes
1answer
55 views

disproving union of infinitely many regular languages

I want to disprove the following statement: "if $L$ is the union of infinitely many regular languages, then $L$ is guaranteed to be a regular language." I don't know where to start. Any hint will be ...
4
votes
0answers
102 views

Is it decidable whether the iterates of a polynomial map are bounded?

Let $f:\mathbb{Q}^n\to \mathbb{Q}^n$ be a polynomial map with rational coefficients. Let $p\in \mathbb{Q}^n$. Is there a known algorithm that given this data determines whether or not the iterates ...
0
votes
1answer
80 views

Computable Function and Predicate Question

I See on Our Lecture note on Theory of Computation Course that: .... The basic characteristic of a computable function is that there must be a finite procedure (an algorithm) telling how to compute ...
6
votes
1answer
94 views

Who first discovered that some R.E. sets are not recursive?

Who first discovered that some recursively enumerable sets are not recursive, or equivalently that some semidecidable sets are undecidable? And in what context? Was the earliest formulation of this ...
1
vote
1answer
78 views

set theory, Incompleteness and axiomatic systems

Is the number of theorems that can be proved (decidable) within a certain set of axioms (for instance ZFC) is finite or infinite ? in other words, are we going to fully exhaust that set of axioms ...
1
vote
1answer
115 views

Is the given Language decidable or recognizable?

Let M be a machine that takes a natural number as input and outputs a natural number. Let L = $\{M:\;M(n)\;outputs\;a\;prime\;greater\;than\;n\;for\;every\;n\}$ Is L decidable? Is L recognizable? ...
2
votes
0answers
44 views

Decidability of a language

Let $C$ be a conjecture about natural numbers. Let $$S = \{n\in N: n > m \text{ where $m$ is the first number found for which $C$ is false} \} $$ Is $S$ decidable? If $C$ is true for all ...
-1
votes
1answer
116 views

Many to one Reducible & Polynomial time

we know that If $A \le_p B$, then $A$ can be reduced to $B$ in polynomial time. we know that If $A \le_m B$, then $A$ is many to one reduction to $B$ . can we deduce that: if $A \le_m B$ then $A ...
-2
votes
1answer
102 views

Why is $x\mapsto x$-th prime number a partial recursive function?

I think that partial recursive functions correspond to all computable functions. Thus, if we can write a computer program to represent a function, the function is partial recursive. In computability ...
-2
votes
1answer
94 views

Undecidability of First Order Logic [closed]

friends! I read in Ebraham's Outline of Logic that first order logic is undecidable because it lacks an algorithmic procedure which reliably detects invalidity in every case. It is undecidable ...