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
0answers
17 views

Computability of certain functions

Suppose we are working in the first-order language with equality with one relation symbol R. And suppose I have a closed formula P that describes a property R may or may not have. We can define a ...
0
votes
1answer
25 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
22 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
0answers
8 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
31 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 ...
0
votes
0answers
24 views

Minimum of two numbers with a Turing Machine

I'm having sme issues to construct a turing machine that gives the minimum of two numbers. I've seen a few turing machines in books that allow use $*$ or similar sings with the machine to keep track ...
1
vote
0answers
19 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
14 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
49 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
34 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
0answers
9 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
82 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 ...
2
votes
1answer
59 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
135 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
42 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
18 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
30 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
36 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
24 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
vote
1answer
63 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
43 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
28 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 ...
2
votes
0answers
24 views

Strange Turing Machine Definition [closed]

i prepare for Autotmata Course Final Exam. in one of lecture, our professor draw this Turing Machine, and wrote DELTA is Neutral element of TM. it'w wrote: Language of this TM is: {$W \in ...
0
votes
1answer
23 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 ...
0
votes
0answers
21 views

Generalization of standard technique for proving that an undecidable language is unrecognizable

Suppose $L = \{P:P(x) \; outputs \; x^2 \;for\; all\; x\}$ Then $\bar L = \{P: P(x)\; does\; not\; output\; x^2 for\; all\; x \}$. By Rice's Theorem or by reduction from the Halting Problem, let's say ...
-1
votes
1answer
35 views

$L \in RE$ Question in Computation [closed]

Let L be a language. Suppose a TM exists that halts on all words in L. Which of the following statements is true? a) if L is r.e we have such TM. b) if L is r.e and complement of L is r.e then we ...
4
votes
2answers
121 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
176 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
15 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
17 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
21 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
89 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
0answers
44 views

predicate logic with assumption NP $\neq$ CO-NP?

Anyone could describe why: Set of All Tautology in propositional logic with assumption NP $\neq$ CO-NP is CO-NP Complete. Thanks. I ask it here before: Is the language of tautologies NP-complete? ...
0
votes
1answer
27 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
77 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 ...
-2
votes
1answer
73 views

D={ $ deg_T (A) | A \subseteq N$} Problem [closed]

Dear friends I wanted to ask the question that already asked 2 times but it's on-hold and after few days deleted, but I didn't get any answer. I try to solve it but confused. I don't know anything and ...
1
vote
1answer
64 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
49 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
36 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 ...
2
votes
1answer
81 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 ...
0
votes
1answer
75 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 ...
-1
votes
1answer
67 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 ...
0
votes
0answers
140 views

range of one increasing computation function?

We know that that the range of any recursive partial function is recursively enumerable. Also we know the fact: Set A is recursive if and only if it is range of some increasing section partial ...
0
votes
1answer
40 views

Problems On Many-one Reducible [closed]

In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. ...
-1
votes
1answer
39 views

Set of Logical Result Problem [closed]

If we have a set of predicate formulas $A$, and there is an algorithm such that for every predicate formula $X$, (with input $X$), output YES iff $X \in A$. My question is about set of logical result ...
1
vote
0answers
37 views

Is a set $\{ e \in \mathbb{N} | \#\{x \in \mathbb{N} | \phi_e(x) \downarrow \} = \#\mathbb{N}\}$ computable?

Denote every partial computable function $f$ with its Godel number $e \in \mathbb{N}$ by $\phi_e$. Then let the halting set of $\phi_e$ be $W_e=\{x \in \mathbb{N} | \phi_e(x) \downarrow \}$ where ...
1
vote
2answers
58 views

How many recursively definable groups are there on $\mathbb{N}$?

How many non-isomorphic, (non-free), non-trivial, recursively definable groups are there on $\mathbb{N}$? I know we can at least get 1. Let $F:\mathbb{N} \to \mathbb{Z}$ be the "natural bijection". By ...
2
votes
1answer
35 views

Primitive-recursive functions and polynomial equations

I am looking for examples of primitive-recursive functions $f:\mathbb{N}\rightarrow\mathbb{N}$ that can not be written as a pair of polynomials, i.e. $$f(n) = m \Leftrightarrow P(n,m) = Q(n,m)$$ ...
4
votes
2answers
73 views

Uncomputability of subset relation

I suppose this obvious question should already be answered in plenty of places, but for some reasons I cannot find a proof of this anywhere. Prove or disprove that their exist a set $X$ that is ...
2
votes
1answer
63 views

Bijection between computable reals and rationals?

This wikipedia article http://en.m.wikipedia.org/wiki/Computable_number#Properties suggests that there is such a bijection. How does it look like? And how to map computable transcedentals like pi to ...