21
votes
How to determine if a set is countable or uncountable?
Some common approaches to prove that some set is countable:
Give an enumeration, i.e. a list that contains all of the elements of the set. It's fine if the list contains duplicates.
Show that it is a ...
- 23.1k
6
votes
Can a universal worst case problem instance exist?
TL;DR: No, I don't think there's much hope of picking a problem instance that is maximally hard for all algorithms.
The question is tricky. It's tricky even to identify a well-formed statement of the ...
D.W.♦
- 164k
5
votes
How to determine if a set is countable or uncountable?
Consider an infinite set $A$. Then, $A$ is countable (or countably infinite) iff there is a bijection $f$ from $\mathbb{N}$ to $A$. This is why we use the term "countable" as intuitively we ...
- 4,735
3
votes
Accepted
Myhill-Nerode sentence and the relation $R_L$
Note that $u, v$ and $w$ can contain any letter. Therefore, $L$ is the language of all words that contain some letter at least twice. In particular, a word that contains some letter 3 times is in $L$. ...
- 4,735
3
votes
Accepted
result of a union between a decidable language and not recognizable one - disjoint
The union is not Turing recognizable. A simple reduction from $A$ to $A\cup B$ operates as follows. Given input $x$, the reduction checks if $x$ is in $B$ ( this is possible as $B$ is decidable) and ...
- 4,735
3
votes
Can a universal worst case problem instance exist?
As mentioned in @D.W.'s answer, I think a meaningful question would not consider a worst case instance, but a worst case family of instances in an attempt to provide an asymptotic lower-bound for the ...
- 4,735
2
votes
In class P, does decidability implies searchability?
I guess you are alluding to the "decision vs search" problems.
Often, we refer to problems in 𝑃 as problems that we can
"efficiently search a solution for" (where efficiently ...
- 4,735
2
votes
Accepted
The number of words that M doesn't accept is finite
You can define a reduction $f$ from $\overline{A_{TM}}$. The basic idea to let $f$, upon reading an input $\langle M, w\rangle$, output $\langle T\rangle$, where $T$ is a TM that operates as follows. ...
- 4,735
2
votes
Accepted
set of words w such that M halts on w is decidable
You cannot let $M'$ recognize $A_{TM}$ by letting it "accept $\langle M, w\rangle$". You need to define the behaviour of $M'$ on $x$, which you completely ignored.
What you wanted to achieve ...
- 4,735
2
votes
Is the difference between an unrecognizable language and a finite language decidable? recognizable?
The answer is "yes", this can be seen using a proof by contradiction.
Hint: All finite languages are recognizable and $\texttt{RE}$ is closed under union and intersection.
- 1,549
2
votes
Accepted
Is UNIQUE(N) Turing-recognizable?
Consider a (deterministic) TM $D$ that recognizes the language $\text{HALT}_{\text{TM}} = \{ \langle M, w\rangle: \text{$M$ halts on $w$} \}$, and let $N$ be a (nondeterministic) TM that, given input $...
- 4,735
1
vote
Accepted
Polynomial reduction function for languages in NPC, reduction from DHP to given language
Why not simply do the following. Given the graph $G=(V,E)$, the reduction outptus the same graph with additional new vertices $u$ and $v$, as you suggested, and then adds the following new directed ...
- 4,735
1
vote
In class P, does decidability implies searchability?
One counterexample is integer factorisation:
given an postive integer $n$, are there integers $a,b$ with $n>a>b>1$,
such that $n = a*b$.
the decision problem is in $P$ (primary test); but it ...
1
vote
How could "the mind" be uncomputable if it's due to neurons processing information?
The basic issue is not that the brain doesn't process information in the general sense.
The issue is that the brain does not "compute" the information in any familiar sense (like the ...
- 592
1
vote
Proving Non-Semi-Decidability of Language L - Seeking Reduction Strategy
You can, for example, let $f(\langle M, x\rangle)$ be the code of a Turing machine $M'$ that, for an input $y$,
runs $M$ on $x$ for $|y|$ steps,
if $M$ halted, keeps running forever, otherwise stops.
...
- 276
Only top scored, non community-wiki answers of a minimum length are eligible