Cantor’s diagonal argument

Cantor’s diagonal argument is a beautiful proof of the uncountability of the real numbers.

First we need some definitions.

Two sets are said to be one-to-one if each member of the first set maps to exactly one member of the second set. We say a set maps onto another set if each member of the first set maps onto a unique member of the second set. If two sets are both one-to-one and onto, then we say they have one-to-one correspondence. For example, the set of uppercase letters and the set of lowercase letters have one-to-one correspondence.

We say a set is countable if it has a finite number of elements or if it has a one-to-one correspondence with the set of positive integers. Essentially, if you can count the members of the set, even if you’d have to count forever, the set is countable.

Cantor’s diagonal argument uses proof by contradiction. That means we’ll start with an assumption and then demonstrate how that assumption leads to a logical contradiction.

Assume the set of real numbers is countable. The set of real numbers is infinite so it must have one-to-one correspondence with the set of positive integers.

If the set of real numbers is countable, then it follows that the subset of real numbers from zero to one is also countable. (If you can count everything in the set, then you can count a subset of the set.)

Since we are assuming the set of real numbers is countable, it must be possible to create a numbered list the real numbers. (This sounds like counting!) Let this list be designated {s1, s2, s3, …}. Here is the start of one such list. The numbers chosen are not significant.

09315285-0668-44F1-82E6-87D998E38299

We must accept that this infinitely long list contains all real numbers between zero and one.

Next, let’s define a number a which will be formed by using the following rule:

The n-th digit of a will not be the same number as the n-th digit of sn.

Here is one possible construction of a. Each digit of a is chosen to be different than the bracketed number in that column.

EB91E22F-69AE-45B2-A9A3-0D5F3C7A155C

We can clearly see that a is a real number in the range zero to one, so there must be a number sn which equals a. However, by definition, the n-th digit of a cannot equal the n-th digit of sn. So a is not a member of our list. We have just shown that the set of positive integers does not map onto the set of real numbers. Thus the set of positive integers does not have one-to-one correspondence with the set of real numbers.

This is a contradiction with our original assumption that the set of real numbers is countable.

Thus the set of real numbers is not countable.

Simulating a half adder

I’m starting to simulate larger circuits in LTSpice. Here’s my attempt at a half adder. Obviously I need to work on my layout skills. It started off well, but the components were too close together.

Total current consumption of the half adder with both inputs high and LEDs on the outputs is 9.4mA.

The circuit is constructed from RTL inverter gates.

half adder

Flipping a sprite in DirectX

I have a sprite which faces to the right. I wanted to make it face left when moving left. After reading a dozen-plus forum threads without finding an answer, I’m posting this for reference. I’m a DirectX noob so this may not be the best solution, but it worked for me.

D3DXVECTOR2 position(caveman.x, caveman.y);
D3DXVECTOR2 spriteCenter(caveman.width / 2.0f, caveman.height / 2.0f);
D3DXVECTOR2 scaling(caveman.faceLeft ? -1 : 1, 1);
D3DXMATRIX matrix;
D3DXMatrixTransformation2D(&matrix, &spriteCenter, 0, &scaling, NULL, 0, &position);
sprite_handler->SetTransform(&matrix);

Also, you will need to turn off culling on your DirectX device object.

d3ddev->SetRenderState(D3DRS_CULLMODE, D3DCULL_NONE);

The Feynman Algorithm

Excerpted from: http://c2.com/cgi/wiki?FeynmanAlgorithm

1. Write down the problem.

2. Think real hard.

3. Write down the solution.

How to use the Feynman Algorithm

1. Write the problem down in an unambiguous way. Often this is just as hard as the next step. Indeed, really, really understanding the problem is sometimes the only hard bit. Once you really, really understand the problem, the answer may be obvious.

2. Become convinced it’s important. Really important. Think about odd ways to solve it, things you wouldn’t tell other people for fear of being laughed into the next century. Look at simple things. Look at really complicated intricate solutions. Then talk to others. Talking to others will allow you to crystallize some of the ideas you have, and produce more ideas for you to think about. Repeat until you have an answer you can write down. If you do this right, immediately before you come up with the answer people will think you’re almost obsessed with the problem and the answer to it.

Note: If you don’t have people to talk to, write down some intermediate results or something to make them become real.

Some problems don’t have answers, only compromises, or proofs of impossibility. These are also valid answers if you can show that a real answer doesn’t exist.

3. Write the answer.

 

A Man on the Moon

A Man On The Moon by Andrew Chaikin retells the story of Apollo through his interviews with each of the astronauts and dozens of engineers and support staff. This book put my childhood fascination in historical context and illuminated many of the less visible aspects of the program: the immense amount of planning, the scientific achievements of the later missions, and the years of individual preparation required. It gave me an insight into the daily lives of the astronauts as they helped design and test the spacecraft. It reads pretty quickly although I found myself constantly derailed as I searched out additional source material. I would highly recommend this book to every space junkie.

The book helped me appreciate the scale of surface features on the moon. Craters less than 6 miles across are classified as “small”! The surface itself does not experience erosion like on Earth, but rather is constantly pelted with micrometeorites (<2mm diameter)–there is no atmosphere to burn up these space particles. One side effect is everything is very sharp. Dust on the moon is highly abrasive and quickly damages spacecraft and equipment.

Apollo 15 landed at the base of the Appenine Mountains. Using the lunar rover (photo), the astronauts climbed over 500 ft up the side of a 16,000 ft tall mountain–taller than any mountain in the continental US. Apollo 17 set the record for most distance covered (12.5 miles).

10154129_10102185035173950_4368668995530086197_n

Detail of surface features. (Higher resolution available on Wikipedia.)

http://en.wikipedia.org/wiki/File:First_View_of_Earth_from_Moon_-_reprocessed.png

http://en.wikipedia.org/wiki/File:First_View_of_Earth_from_Moon_-_reprocessed.png

A DSL for testing cash registers

I’m kicking around an idea for a DSL for testing cash register transactions. My goal is for it to be simple enough that someone without a programming background could verify the test scenarios. To do that, I’m drawing inspiration from something that everyone at my employer is familiar with–receipts. The test input will look like a register receipt and the output will be another receipt with an expected and actual column.

test "Product at retail":
	item		"123"

	subtotal	50.00
	tax		 3.75
	total		53.75

This is just plain text in a file. You can also declare products, tender types, discounts, tax rates, etc in the same file to include them in a test. The entire DSL is declarative. For example, here I’m declaring an item before the discount it uses.

product:
	sku		"234"
	retail		10.00
	discounts	"bogo"

item_discount:
	name		"bogo"
	buy		1
	getFree		1

test "Item with BOGO":
	item		"234", 2    // qty = 2
	
	subtotal	10.00
	tax		 0.75
	total		10.75

The output of these tests is intended to look like another receipt.

Passed “Item at retail”

SKU                         Qty      Total
-------------------- ---------- ----------
123                        1.00      50.00

                       Expected     Actual
                     ---------- ----------
            Subtotal      50.00      50.00
           Discounts       0.00       0.00
               Taxes       3.75       3.75
               Total      53.75      53.75


FAILED “Item with BOGO”

SKU                         Qty      Total
-------------------- ---------- ----------
234                        2.00      20.00 
   bogo                             -10.00

                       Expected     Actual
                     ---------- ----------
            Subtotal      10.00      10.00
           Discounts       0.00       0.00
               Taxes       0.75       1.50 ***  // bug: tax applied on retail price
               Total      10.75      11.50 ***

The ***s indicate lines which failed the expectations. A future extension to the DSL may allow you to set expectations on discounts individually.

To pull this off, I leveraged RhinoDSL from Ayende Rahien. RhinoDSL is a tool for creating DSLs in Boo, a minimalist and very flexible .NET language which plays nicely with C# applications. I started from the OrderDSL sample and added a method for each keyword. When compiled, the tests look more like the following C# code:

public class TestScenario : BaseOrderDSL
{
	public override void Prepare()
	{
		Test("item with bogo", () => {
			Item(“123”, 2);
			Subtotal(10.00m);
			Tax(0.75m);
			Total(10.75m);
		});
	}
}

All the methods called are declared in BaseOrderDSL. The Execute() method provided by the base class transforms the test objects into domain objects and passes them to the application. The receipt output is generated by a bunch of string.Format() calls using the pad left/right string formatters (eg: {1,10:N2}). In all it’s only about 300 lines of code, and most of that is just ceremony for wiring up keywords.

If you’d like to learn more about writing DSLs in .NET applications, I’d recommend picking up a copy of Ayende’s book DSLs in Boo.

The Hole-in-the-Wall

The following is an excerpt from Abundance: The Future Is Better Than You Think (pgs 174-177). I’m excerpting this here because I found it to give such a great insight into one potential future for education.

In 1999 the Indian physicist Sugata Mitra got interested in education. He knew there were places in the world without schools and places in the world where good teachers didn’t want to teach. What could be done for kids living in those spots was his question. Self-directed learning was one possible solution, but were kids living in slums capable of all that much self-direction?

At the time, Mitra was head of research and development for NIIT Technologies, a top computer software and development company in New Delhi, India. His posh twenty-first century office abutted an urban slum but was kept separate by a tall brick wall. So Mitra designed a simple experiment. He cut a hole in the wall and installed a computer and a track pad, with the screen and the pad facing into the slum. He did it in such a way that theft was not a problem, then connected the computer to the Internet, added a web browser, and walked away.

The kids who lived in the slums could not speak English, did not know how to use a computer, and had no knowledge of the Internet, but they were curious. Within minutes, they’d figured out how to point and click. By the end of the first day, they were surfing the web and—even more importantly—teaching one another how to surf the web. These results raised more questions than they answered. Were they real? Did these kids really teach themselves how to use this computer, or did someone, perhaps out of sight of Mitra’s hidden video camera, explain the technology to them?

Continue reading

Synergy

Perhaps the best business buzzword ever. Coming from the technical implementation side of business, I always hear it used by executives when talking strategy. To be honest, I didn’t realize it was an actual word until recently when I started seeing it in management books. I’ve previously interpreted it as a mashup of the words “synergistic” and “energy”.

Dictionary.com defines synergy as:

synergy. noun. the interaction of elements that when combined produce a total effect that is greater than the sum of the individual elements, contributions, etc.; synergism.

Merriam-Webster defines it as “the increased effectiveness that results when two or more people or businesses work together”.

The word actually comes from the Greek synergos meaning “working together” (syn: together; ergos: work) and was first used in English in 1650.

So synergy is more than just a harmonious partnership. It describes a partnership where the output is greater than the sum of the individual contributions. In the ideal case, I would say synergy is a positive feedback loop; each partner can draw more out of the other.

Gallup Entrepreneur StrengthsFinder Results

Today I took Gallup’s Entrepreneur StrengthsFinder survey. The ESF is designed to identify your natural talents that will help in starting a successful business. It also highlights weak areas where you should find a partner to help fill out your skill set.

The ESF is part of Gallup’s initiative to identify and coach highly talented entrepreneurs. In the accompanying book, Jim Clifton, Gallup’s Chairman, lays out a vision for an education system that is not only great at identifying intellectual and sports talent, but also entrepreneurial talent. Jim believes that this is the key to reversing the downward trend of new business formation in the United States.

My dominant talents:

  • Knowledge-Seeker
  • Creative Thinker
  • Risk-Taker
  • Delegator

My contributing talents:

  • Independent
  • Business Focus

My supporting talents:

  • Determination
  • Confidence
  • Promoter
  • Relationship-Builder

 

What was your first reaction to the talents described on page two of your report? Which talents sound most like you?

I’m surprised “independent” isn’t in the dominant talents list. I’m introverted and tend to work alone very well. I suppose answering questions that asked if I bounce ideas off others reduced the dominance of this talent in the survey. Knowledge-Seeker is definitely my strong talent. Risk-Taker was the surprise result here.

With whom could you share your results?

I’ll share this report with my coworkers. I’ll also run the results by the local administrator of AIM who put on the IT Leadership Academy.

Which talent would you like to work on?

I need to work on confidence. When I’m working with people I know very well, I have no problem speaking up and arguing my viewpoint. In groups of strangers I’m much more reserved. This is probably my biggest hurdle for making new connections with customers. I need to ask more questions. I always prefer to take time to reflect after gathering the facts/requirements before proposing a solution. Some people interpret this as lack of enthusiasm or simply lack of ideas. In reality, I probably have too many ideas to share all at once and need time to determine what the best course of action is. I think the best way to improve this is through more practice and broadening my network to get in front of my people.