For decidability purposes, it is equivalent to present the Turing machine with a DFA, an NFA, or a regular expression because the machine can convert one form of encoding to another.
A set is countable if either it is finite or it has the same size as .
Example: Let be the set of natural numbers and let be the set of even natural numbers .
The correspondence mapping to is simply . Using Cantor’s definition of size, we can see that and have the same size. We can visualize f more easily with the help of a table.
对角化方法
❓
If we have two infinit sets, how can we tell whether one is larger than the other or whether they are of the same size?
If we let be the set of positive rational numbers, seems to be much larger than . Yet these two sets are the same size according to our definition. We give a correspondence with to show that is countable.
Now we turn this matrix into a list. One (bad) way to attempt it would be to begin the list with all the elements in the first row. That isn’t a good approach because the first row is infinite, so the list would never get to the second row.
Instead we list the elements on the diagonals. We avoid causing a repetition (such as ) by skipping an element.
Continuing in this way, we obtain a list of all the elements of .
不可数性
After seeing the correspondence of and , you might think that any two , you might think that any two infinite sets can be shown to have the same size. However, for some infinite sets, no correspondence with exists. These sets are simply too big. Such sets are called uncountable.
🧻
is uncountable.
We show that no correspondence exists between and . The proof is by contradiction.
Suppose that a correspondence existed between and . Our job is to show that fails to work as it should.
We construct the desired .
Our objective is to ensure that for any .
The following table shows a few values of a hypothetical correspondence .
例子
证明可识别
Turing-Recognizable Languages are also called Recursively Enumerable Languages.
