# Tag Info

### 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

### 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 ...
• 164k

### 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
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
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

### 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

### 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
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
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

### 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