It Does Not Compute

coolsites.com

Suppose you visit the hypothetical website coolsites.com -- which is a list of cool websites you might want to visit. It might look like this:

coolsites

  • arstechnica.com
  • www.thisiscolossal.com/
  • www.reddit.com/
  • ...
  • ...
  • coolsites.com
  • ...

    Look! the website has a link to itself. This makes sense because it's a cool site.

    selflinking.com (aka sites that contain links to themselves)

    Turns out lots and lots and lots of website link to themselves. Among these websites is the hypothetical coolsites.com discussed above -- it links to itself. Suppose you work for yourself, or for Google, and you decide to make a website of all the sites that link to themselves. You create it, register the domain selflinking.com and create a great site. It might even be listed in coolsites.com, because it's a pretty interesting website.

    So far so good. Think about these questions (and answers)

    Self Check

    1. Can you create a website of interesting sites? (yes)
    2. Do some sites link to the themselves? (yes)
    3. Does every website link to itself? (no)
    4. Could you create a website by crawling the Internet of all the webistes that contain links to themselves? (yes)

    selflinking.com self check

    If selflinking.com included a link to itself, would that be ok? Sure! It would be a website that links to itself, so it would be listed in the pages of websites that link to themselves.

    If selflinking.com did not link to itself, would that be ok? Sure! It only contains a list of those websites that link to themselves.

    badsites.com

    A website that listed bad websites would be interesting. Parents might use it to protect their kids. You might use it to be sure to let others know that you don't like goheels.com so you submit that to the site badsites.com. Nothing wrong with this.

    The site badsites.com might be listed on coolsites.com, because it's a pretty cool site. For our purposes, let's supposed it would NOT include a link to itself, because it's not a bad site, it's a good site!

    This means that badsites.com is not listed on selflinking.com -- because it doesn't link to itself.

    braincrush.com aka nonselflinking.com

    You decide to make a website that contains a list of links to websites that don't have links to themselves. Because you're curious. You call it nonselflinking.com, but also create an alias for it called braincrush.com -- you are excited about this.

    You realize that coolsites.com will not be on on braincrush.com -- because coolsites.com contains a link to itself. This isn't a problem at all.

    You know that selflinking.com might contain a link to itself. If it does, it won't be listed on braincrush.com. This isn't a problem at all.

    If selflinking.com does not contain a link to itself, then it would appear on braincrush.com -- this still isn't a problem at all.

    Self Check

    1. Can you create a website of bad sites? (yes)
    2. If you create nonselflink.com, is it possible that selflinking.com is listed there? (yes)
    3. If you create nonselflink.com, is it possible that selflinking.com is not listed there? (yes)
    4. Can you create braincrush.com? (not yet known, but no)

    World of Hurt

    Aha! You are excited. You've created some great and useful websites. Then you start to wonder. What about braincrush.com aka nonselflinking.com --- does it link to itself?

    If it does link to itself then it will appear on selflinking.com, that's not a big deal. What is a big deal, is that it can't link to itself. Because braincrush.com is a website/list of sites that don't link to themselves. So it can't link to itself at all, by the very definition of the website.

    ARGGGGG!! --- if it doesn't link to itself, it should be listed on braincrush.com -- because that's a website of the sites that don't link to themselves. But (big but here), if it's listed on braincrush.com then it links to itself, because it's on its own pages. Because braincrush.com. is a listing of all the websites that don't link to themselves.

    So we CANNOT create braincrush.com -- the website that contains links to all the sites that don't link to themselves. If we could create it, we'd end up in a contradictory situation of not being able to create it -- because it can't be listed on its own pages, which means it must be listed on its own pages which means it can't be ....

    Computability

    When philosophers and mathematicians encounter these kinds of contradictions they can prove things. Not everyone enjoys these kinds of proof-by-contradiction: Assume you can create something, show you get a contradiction, so your assumption must be wrong. You can't create the thing you assumed you could create.

    We can't create braincrush.com, because we end up in a contradiction -- so it's not possible to create that website. We can create coolsites.com and selflinking.com, no contradictions there.

    It turns out there are programs we cannot write, just like there are websites we cannot create. This is an interesting fact. To some folks. To you, remember this: it's not about being smart enough, or clever enough, or experienced enough, or having faster computers. There are some programs that are impossible to write/create. One is a single program that can always tell correctly whether another program will enter an infinite loop run it's run on some input. We can't write this infinte-loop-checker.

    So What!

    Lucky for us, we can have Google Glass, we can get email, we can play angry birds. We can do a whole lot of cool things with programs. We just can't do everything.