The Floyd Cohort Minecraft Blog

The Floyd Cohort Minecraft Blog: Send your Minecraft user name to our Ask box, and we'll add you to our server!  

[floydsmp]

Diagonalization

A collection of objects or things is called a set. For example, we can put all of the cats in your neighborhood in a set, using their name to represent each one as an element of the set. This kind of set would be called a finite set, meaning that we can count every element (or cat!) in the set and eventually run out of cats to count. However, we can also have a set that doesn’t end, also called an infinite set. If we made our set of cats into an infinite set and tried to count it, we would be counting cats forever.

We can also say that a set is countable or uncountable. A set is countable if there is a 1-to-1 mapping from the set S to the Natural Numbers. We can demonstrate countability by representing elements from the set S with the natural numbers, which is also an infinite set. We can call both finite and infinite sets countable, but all uncountable sets are infinite. Infinite sets are countable when we can assign an element from the (infinite) natural number set to each element in the infinite set. But how do we show that an infinite set is uncountable?

Diagonalization is used to show that there are infinite sets that are uncountable, which means that the set does not have 1-1 matching with the set of natural numbers, which are infinite. This technique is famously known as Cantor’s Proof. 

Look at every line and row in this 8x8 grid above. If we take each “on” light to represent a 1 and each “off” light to represent a 0, we can see how this grid could be translated into binary. We can also imagine each row and column extends infinitely, like they would if we had a set of infinite bit-strings in an infinite set. All the strings shown in the grid of rows and columns are countable, even if they are infinite, since we can assign an element from the natural numbers to each of them.

When looking at our representation, we can see that there are bits that make up a diagonal through the center of the grid. These highlighted bits create a new bit-string that is different from the counted bit-strings, meaning it’s not represented in the rows or columns. (This is the same string that we see in the 1x8 grid next to the large grid.) Since we can see that we can find an uncounted string from an already counted infinite set, this means that the superset of this set is uncountable.

In this way, we can see that it’s possible for an infinite set to be uncountable!

[floydsmp]

Application of Logic Gates

Now we can understand the different types of gates and their outputs, we can put them together and build what is called a circuit. A circuit is a connection of gates that we can use to create outputs that depend on the values that we input. For example, a type of circuit we can build is an adder, which adds numbers together. There are two types of adders: half and full.

A half adder is used to add two single bit numbers, outputting the sum, or added result of the inputs, and a carry bit, which can be used to help us calculate the next digits of the equation if more calculation is required. A full adder is able to add three single bit binary numbers.

We can make a half adder using one XOR gate and one AND gate. This is represented in Minecraft below:

We can create a full adder using one OR gate, two AND gates, and two XOR gates. It’s easy to see how the half adder and full adder structures are similar.

Below is a full adder with an automatic carry:

Note: This carry is always active and follows the process of a half-adder carry (Only when both inputs are 1 then the carry is active; otherwise, it is not)

Then we also have a full adder with a manual carry:

[floydsmp]

Introduction to Equivalence in Computing

NAND to AON Equivalence

Below is a NAND gate implementation in Minecraft. The red stone lamp is the output and switches are the input for the NAND gate. By definition, a NAND gate will output 0 only if both inputs are 1. So the red stone lamp will only light up when both switches are off. All other switch states will leave the redstone lamp off.

We call NAND gate universal gates because we could implement all logic gates using NAND gates as components. We could see from the image below that the AND gates are made with two NAND gates, OR gate and NOT gate are also made using NAND gates that are shown above. 

AON to NAND Equivalence

We could also use AON gates to build NAND gates. In the picture below, we used AND and NOT gates together to build a NAND gate. Since NAND gates just display the opposite result of AND gates, we just need to negate the result of AND gates. As we can see, the NAND gate is just a NOT gate on top of AND gates.

We could see that AON could be built using NAND gates and NAND gates could be built using AON gates. Therefore, AON and NAND are equivalent in that they have the same computing power. 

[floydsmp]

Introduction to Gates

There are two types of gates that we will talk about. They are AON (which is an acronym for the three gates AND, OR, and NOT) and NAND!

AON

Gates are ways in which we are able to represent logic. Logic is a formal tool we use to evaluate the truth of statements. For example, when we say “and”, we are usually indicating that both things on either side of the “and” are true. We use this logic in computers to compute problems. We use inputs such as 1 and 0 where 1 means on and 0 means off. This input and the output produced by our computation (also in 0′s and 1′s) is encoded in a language called binary. If we wanted to formalize the idea of an idea from logic, such as “and”, we can create something called a gate, which will always produced the output we would want from this logic gate. The only difference is that we’re communicating in binary, not English! For example, we can formalize “and” into a special type of logic gate called AND. We’ll discuss AND and other gates in our next post.

NAND

NAND is a logic gate that represents NOT-AND which outputs 1 only when both inputs are 0. Upon first glance, this might seem like an unhelpful way to orient our gate. In reality, NAND is what’s known as a “Universal Gate” and can be used to build other gates! We’ll show how we can create our previous AND, OR, NOT gates using NAND gates in our next post. When we show that we can create the AND, OR, NOT gates, we show that NAND is equivalent in computing power to AON.

[floydsmp]

Binary Representation

You might think that binary representation is a bunch of 0’s and 1’s organized haphazardly. But understanding how numbers are represented in binary is much easier than you’d think! When you think of an integer, say 1 or 2, you’re really seeing this number in it’s base-10, or decimal, form. If we change the power of the base that we use to represent a number, we can rewrite it into a different form.

Binary representation is in base-2 form. This means that every number is represented by 2 to the power of the number of its place in the string. For example, let’s say we would like to convert the integer 13 into binary. We know that 2^3 + 2^2 + 0 + 2^0 = 13. If we replace all of these ‘2^x’ statements with a bit (represented by a 0 or 1), we can convert 13 into binary as 1101. The ‘0’ in a binary string is put in place of a ‘2^x’ space in the string that is not used to create the number we desire. With this same example, if we were to flip the ‘0’ digit in 13’s binary representation, we could create 1111, which would be a representation of 15.

Look at this representation in Minecraft of a possible binary string. Every lantern turned “on” can be used to represent a 1, and each lantern turned “off” can be used to represent a 0. From right to left, we can consider the first lantern to be in the 2^0 space, the second lantern in the 2^1 space, and so on.

This is how we can represent 21 in binary using Minecraft. We can see that the 2^0, 2^2, and 2^4 spaces are lit up: