---
Video Title: Life on Mars
Description: Theory of Computation
https://uvatoc.github.io/week8

16.1: Life on Mars
- What does it mean for a function to be computable

Nathan Brunelle and David Evans
University of Virginia
---

So let's say that I have this function
that I'm going to call L.

And L takes in one bit as input,
and it's going to give one bit as output.

And the way that L behaves is it's going
to return one if there's life on Mars,

and it is going to return zero otherwise.

How many think that I can compute this
function with a NAND circuit?

How many think I am unable to compute this
function with a NAND circuit?

Okay, discuss this with your neighbors.

Try to come to an agreement
about whether or not

you can do this function
with a NAND circuit.

The important point here that you are
making is that basically there's a

difference between being
able to implement a function

and knowing what the
function is going to do.

So we as humans don't
know if the output to this

function should just always
be one or always be zero.

But it's going to be one of those two.

There are only two options for what this
function is.

It's either going to say for any x that
you give as input, it's going to return

one, or it's going to
say for any x that you

give it as input, it's
going to return zero.

I don't know which one it is, but I know
it's one of those two.

There are two options.

And I can implement either option.

So it's either going to be like return
one, or alternatively, if there isn't life

on Mars, then I can implement this
function by saying return zero.

So without knowing the exact identity of a
function, I can still reason about whether

or not I'm going to be able to implement
that with a circuit.

Because I knew that it
was going to be either

the left function or
the right function.

I didn't know which
one it was going to be,

but I knew it was going
to be one or the other.

Both of them I can implement using a very
simple program.

So therefore, I can implement this entire
function using a program.

I can implement this using Python or NAND
circuits or whatever I would like.