Some questions can not be solved with computation.


This is the first in a series of articles building up to an explanation the Church-Turing Thesis.

Consider the following yes-or-no question.

*Will the following program terminate?*

We can contrive simple examples for a "yes" case of the question:

~~~python
def a():
    print("Hello")
a()
~~~

And for the "no" case.

~~~python
def a():
    return a()
a()
~~~

Someone fluent in Python will tell you of the above: No, it will accumulate to infinite. Its stack will grow as such.

~~~text
   .
   .
   .
|-----|
| a() | <-- third call to a()
|-----|
| a() | <-- second call to a()
|-----|
| a() | <-- first call to a()
~~~

This toy question invites us to consider a concept called _decidability_.  A yes-or-no question is decidable if there exists an effective means of computing its answer.

An example of a _very_ decidable question is:

*Is the following number prime?*

~~~text
42
~~~

No.

~~~text
41
~~~

Yes.

We, as thinkers, can surmise computing machines that can _automatically_ and _reliably_ answer the above question with a yes or a no. The device that you are reading this post on is a machine that can reliably answer *yes* or *no* to *Is this number prime?*

## Undecidability

Returning to our first example. Why is it considered undecidable?

The device you are using can not reliably answer *Will the following program terminate?*. This is there's no simple tool for Bill Gates or Steve Jobs to include in their computers that would simply choose not to run a program with an infinite loop.

From a different angle, we are unable to determine whether a program will run without actually running the program. Well, if we want to know if a program will terminate, and our tool for determining so must run that program to completion... then we're hosed. The tool will sit and churn forever on the input.

Thus, "Does this program terminate?" is an undecidable question. We'll build on this concept (and return to it) in follow-up posts about the Church-Turing Thesis and its broader implications.


Church-Turing (Part 1): Will this program terminate?

Your email client sends read receipts. You should turn them off.


Your email client has a setting for "display external images". It should be disabled by default.

## Text vs. HTML Email

A long time ago, emails were just text. You sent an email as a self-contained sequence of letters and numbers. You received the email whole.

~~~html
From: montana@example.com
To: kilgore@example.com
Subject: Hello
Hi.
~~~

At some point, we decided we wanted colors and typeface and images... enter *HTML Email*. Emails now have typefaces and colors and images.

~~~html
From: montana@example.com
To: kilgore@example.com
Subject: Hello
<h1>Hi.</h1>
<p>Look at this cat.</p>
<img src="http://www.example.com/cat.jpg">
~~~

Just like the webpage you're viewing, I send you a plain text document containing HTML. When web browser sees an
```html
<img src="http://www.example.com/cat.jpg">
```
it conveniently grabs the image its referring to and shows it to you.

## Read Receipts

Unfortunately, corporations, marketing teams, or over-eager recruiters can exploit this to determine not only _if_ you've read something they've sent, but _where_ and _when_ you opened it.

### How

They'll hide an image, `example.com/image-just-for-kilgore@example.com.jpg` in an email they send to me.

~~~html
From: doug@recruitinggenius.com
To: kilgore@example.com
Subject: Hello
<p>Do you want a JOB?</p>
<img src="http://www.example.com/kilgore@example.com.jpg">
~~~


When I open this email, my email client encounters the `<img>`, and goes to their doug's malicious Recruiting Genius website to fetch it. The image's address was created unique to me, so these DOUG can see I've opened the email (AND my IP address. AND information about my device.).

## What can I do?

Always disable the "Display external images" in your email account. This leaves you an option to selectively display images in only the emails you wish to see. When I receive, for example, an email with a barcode that I _must_ see, I simply click the "Display Images in this Message"-- who cares if Amazon sees you've opened their email.

But Doug from RecruitingGenius... I SEE YOU.

NOTE: This is especially important with spam email. Spammers pay attention to who actually opens their junk mail. If they see you loading their images, they can be certain that your email address is a good one to keep bothering.


January 25, 2023

January 24, 2023