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
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
118 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
52 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
51 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
32 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
23 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
59 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
17 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
46 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
57 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
89 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
103 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
192 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
53 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
56 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
53 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
43 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
82 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
55 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
75 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
164 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
179 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
221 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
27 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
23 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
50 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
97 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
62 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
93 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
100 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
74 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
112 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
41 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
108 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
98 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
89 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
1answer
58 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
48 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
41 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
59 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
41 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
79 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 ...
3
votes
1answer
99 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 ...
1
vote
1answer
91 views

Is there a more general proof for the halting problem?

Note:If this question is better suited for a different site, please tell me in the comments. Summary:Is there a proof for the impossibility of the halting problem that doesn't involve calling it on ...
1
vote
0answers
63 views

Is this proof for the undecidability of $\beta$-normalisation in $\lambda$-calculus valid?

The proofs I have so far seen for the undecidability of $\beta$-normalisation all make use of Gödel numbering in order to first prove the more general Scott-Curry theorem. As an exercise, I have tried ...
-1
votes
1answer
114 views

Many-one Reducibility Understanding Problem [closed]

We know for every set $B$, that be r.e have: $$B\leq_mK$$ (The set $B$ is many-one reducible, or m-reducible, to the set $K$) we know $K$ is r.e and define: $$K=\{ e:e\in W_e\}$$ my challenge is: ...
1
vote
1answer
75 views

Big Questions in First Order Logic

if $\Sigma$ is a r.e set (half decidable) of sentence in first order logic, the set of logical result of $\Sigma$ is Recursively Axiomatizable. why this is false? or maybe it's true? ...