26
votes
Accepted
Are there any countable sets that are not computably enumerable?
Are there any examples of countable sets that are not enumerable?
Yes. All subsets of the natural numbers are countable but not all of them are enumerable. (Proof: there are uncountably many ...
- 82.1k
19
votes
Are there any countable sets that are not computably enumerable?
Yes, every undecidable (not semi-decidable) language has this property.
For example, consider the set $L = \{(x,M) \mid M \text{ does not halt on input } x \}$.
Suppose we have an algorithm that can ...
- 29.9k
16
votes
Accepted
Why is the halting problem semi-decidable?
Tl;dr: "(say) whether or not it halts" and "(say) if it halts" are not the same thing. Use mathematics to avoid confusion induced by language ambiguity.
Halting problem says that for a given input ...
- 72.8k
12
votes
Accepted
Dovetailing in Turing Machines?
Dovetailing is when you simulate two or more Turing machines in parallel on a single Turing machine. Your operating system uses this technique all the time.
Why is dovetailing useful? Here is one ...
- 278k
9
votes
Definition of an immune set
Standard construction of a (co-c.e.) immune set
Let us follow the standard construction by Emile Post from his famous 1944 paper (see section 5) introducing reducibilities in computability theory.
...
- 31k
8
votes
Accepted
Partial recursive function with no total recursive extension
Take the function that interprets its input as the description of a Turing machine, and outputs the number of steps it takes the machine to halt, if it halts, and is undefined otherwise. This function ...
- 278k
8
votes
Why doesn't infinite run time violate Turing completeness? Shouldn't "completeness" include halting?
You do not yet understand what Turing completeness means.
Turing completeness is the ability to perform arbitrary finite computations.
To simplify matters, we say an arbitrary finite computation is ...
- 5,776
7
votes
Is the Rice Theorem applicable for these problems?
Rice's theorem cannot be used to show the undecidability of these two languages.
Most of the incorrect attempts that I have come across, are based on the misunderstanding that the notion of property ...
- 2,516
7
votes
Are there any countable sets that are not computably enumerable?
In computability theory we deal with subsets of $\Sigma^*$, where $\Sigma = \{0,1\}$. This language is countably infinite, and so any subset $L \subseteq \Sigma^*$ is countable. Furthermore, there are ...
- 9,877
7
votes
Accepted
How to show that the NECESSARY_CFG is Turing-recognizable but undecidable?
An approach for the undecidability
Let $G$ be a context-free grammar. We can add to $G$ new context-free generation rules that employs new variables without using any variables in $G$ (except the ...
- 39.1k
6
votes
Definition of an immune set
An interesting example of immune set is the set of random numbers in
Kolmogorov complexity.
The Kolmogorov complexity $k(n)$ of a number $n$
is the smallest $i$ such that $\varphi_i(0) = n$.
The idea ...
- 504
6
votes
How to show that the NECESSARY_CFG is Turing-recognizable but undecidable?
Let $G$ be a context-free grammar over an alphabet $\Sigma$ with initial variable $S$. Create a new grammar $G'$ with a new initial variable $S'$, a new variable $A$, and transitions $S' \to S \mid A$,...
- 278k
5
votes
Accepted
The Church-Turing-Thesis in proofs
A Turing machine provides a formal definition of a "computable" function, while the Church-Turing-Thesis says that intuitive notion of "computable" coincides with the formal definition of "computable",...
- 9,877
5
votes
Accepted
Proof that total computable functions are not enumerable
$g$ is total computable by definition.
By assumption $f : \mathbb{N}^2 \to \mathbb{N}$ is total computable.
$1$ certainly is.
$+$ certainly is.
The concatenation of $+$ and $f$ is computable by ...
- 72.8k
5
votes
Accepted
Determining if given languages are regular or recursively enumerable
Your intuition is entirely correct; this solution is nonsense. $L_1$ isn't a regular language; it's not even a decidable language, by Rice's Theorem, and also not recognizable (aka recursively ...
- 7,176
5
votes
Accepted
Is it decidable whether a Turing machine M will reach state q on input s?
Do we ever take into consideration a word with infinite length during such analysis?
Never say never. However, it is a safe bet that in the course of your undergraduate or even graduate study you can ...
- 39.1k
5
votes
Accepted
Can I reduce a non semi decidable and undecidable language to a semi decidable and undecidable langauge? many-one reduction
It depends on the reduction.
Using a Turing reduction, it is possible. For example, any problem $A$ is Turing-reducible to its complement $\overline{A}$, by puting a negation on an answer given by an ...
- 16k
4
votes
How to prove that a language is not recursively enumerable
Some common techniques include:
We start by picking any $L'$ which is known to be non RE, e.g. we let $L'$ to be the complement of the halting problem. Then we prove the m-reduction $L' \leq_m L$. If ...
- 14.6k
4
votes
Closure of Turing-recognizable languages under homomorphism
A class of languages $\mathcal{L}$ is closed against concatenation if for every pair of languages $L_1, L_2 \in \mathcal{L}$ we also have $L_1 \cdot L_2 \in \mathcal{L}$.
Here, $A \cdot B = \{ v \...
- 72.8k
4
votes
Proof that total computable functions are not enumerable
The problem really is in how you're approaching the proof by contradiction. You're objecting to one conclusion ("$g$ is computable and total") by drawing a different conclusion ("$g$ isn't total ...
- 2,980
4
votes
is there a constructive proof of the existence of a language which isn't recursive (without invoking infinities)?
We can write a computer program that will enumerate all halting computer programs. It seems that you are happy to accept accumulating the output of program into a (potentially infinite) set. Thus, you ...
- 3,213
4
votes
Are decidable set/languages EQUIVALENT to type 1 grammars (non-contracting)?
Yuval's answer is absolutely right, but note that there's a more general principle in play here as well: diagonalization. Any time we have a class of decidable languages for which we have a "...
- 2,980
4
votes
Accelerating semidecision of halting problem
There is a family of explicit programs for which acceleration cannot exist, as proven by the time hierarchy theorem.
Let's unpack the proof of the time hierarchy theorem. Let $T(n)$ be any time-...
- 41
3
votes
Accepted
Unrecognizable languages relationship to NP-hard languages
There are NP-hard languages arbitrarily high in the arithmetical hierarchy.
To answer your specific question, the complement of the halting problem is NP-hard and it's in $\mathrm{coRE}\setminus\...
- 82.1k
3
votes
Accepted
which of the following languages are Recursively Enumerable?
$B$ is r.e, but $A$ is not.
You can construct a TM which takes as input $M$ and simulates $M$ on every string of $0$ and $1$ in canonical order for each step $n$. In other words, if $s_1, s_2,...$ ...
- 9,877
3
votes
Accepted
Given language consisting Turing machines is decidable or not?
In other words, $L=\{\langle M \rangle:L(M)\notin \{\phi,\Sigma^*\}\}$. you can show explicit reduction from a language you already know is not in $RE$. for example $\overline{HP}$ (it is a very ...
- 628
3
votes
Accepted
How can I prove that there is a decidable language which is not in P?
Unfortunately, this doesn't work at all. What you're proposing to do is to simulate a Turing machine on some input, and ask whether it accepts/rejects that input in polynomial time, and that question ...
- 82.1k
3
votes
Accepted
Language of TMs that accept some x in less than 50 steps. Is it in co-RE?
Maybe that will help ?
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec09.pdf
Page 42
...
- 62
3
votes
Accepted
Enumerable disjoint subsets whose union is equal to the union of the sets
This answer assumes that enumerable means recursively enumerable.
Here is an enumerator for $C$:
Run enumerators for $A,B$ in parallel.
Whenever the enumerator for $A$ outputs a word, check whether ...
- 278k
3
votes
Accepted
If a problem is "not semi-decidable" and "not decidable" can we say it is "undecidable"?
Undecidable isn't wrong: "undecidable" means exactly the same thing as "not decidable". However, your TA is saying that you can make the strictly stronger statement that the set is not even semi-...
- 82.1k
Only top scored, non community-wiki answers of a minimum length are eligible