Touring Turing

1 Turing Complete

Learn It

By combining while loops and conditional selection we can become Turing Complete.
That means we can write programs that can solve any problem a Turing Machine can solve.
As Turing Machines can solve any computable problem, that means we'll be able to write programs that can solve any computable problem.

Code It

Before we get started on learning about mixing conditional selection and loops, we need to look at an important aspect of programming that you may find useful.
Sometimes when we are writing scripts, we want to prevent lines from being executed, but we don't want to delete them.
Other times we want to add in little explanations into our code, so that someone reading it can understand what is going on.
For both of these things, we use comments

Code It

A commented line in Python starts with a hash - #
Copy and paste this code into a new script.

x = 10
x = 20
while x > 0:
    print(x)
    x = x - 1

Run the code and see what happens.

Now we're going to edit the code a little.

x = 10
#x = 20
while x > 0:
    print(x)
    x = x - 1

Run the code again.
You'll notice that the line with a # symbol in it did not get executed, so x was never reassigned to the value 20
We can also do this:

x = 10 #Assign x to the value 10
#x = 20
while x > 0: #Loop until x reaches 0
    print(x)
    x = x - 1 #Subtract 1 from x.

You'll notice that this code runs without any problems, but the comments provide helpful information to anyone who is reading your code.

#x = 10 #Assign x to the value 10
#x = 20
while x > 0: #Loop until x reaches 0
    print(x)
    x = x - 1 #Subtract 1 from x.

Here we've gone a little too far with our comments.
As the lines that assign a value to x have both been commented out, it's as if they're not there at all, and so the while loop doesn't make any sense.

Code It

To get used to combining loops and conditional selection, let's make another simple guessing game.
Here's the code

number = 7
guess = None

while guess != number:
    guess = int(input('What number am I thinking of? '))
    if guess > number:
        print('Too high')
    elif guess < number:
        print('Too low')
    else:
        print('Well done')

Create a new script and call it guessAnumber.py
Copy and paste the code in above, or use the Trinket below:

Run the code and make sure you are familiar with how it works.

Badge It - Silver

Add comments to the end of each line of code that explains the purpose of the line.
For instance:

number = 7 #Assign the value 7 to the variable number

2 Solving Computable problems

Learn It

A Turing Machine can solve any problem that is computable.
Up to now, your scripts have been fairly simple, and not accomplished any real useful work.
Let's try and make something useful

Code It

Finding square roots of a number are pretty hard.
There are some special formulas you can use to calculate a square root, but we're going to harness the power and speed of a computer in our algorithm.
Let's say we wanted to find the square root of 16129
What we need to know is which number, when multiplied by itself, equals 16129

sqrRt * sqrRt == 16129

Because computers can run calculations pretty fast, we can test every number below 16129, multiply it by it by itself and then see if it equals 16129

>>> 16128 * 16128 == 16129
False
>>> 16127 * 16127 == 16129
False
>>> 16126 * 16126 == 16129
False

We can keep doing this until we get the answer True
Let's see if we can code this in Python

number = 16129
test =  16128
stop = False
while stop == False:
    if test * test == number:
        print(test)
        stop = True
    else:
        test = test - 1

Try it with a few other numbers.
What happens when you use the number 152399025?

Badge It - Gold

Alter the script above so that instead of hard coding the number, it asks the user for a number (Don't forget to type cast)
Make sure the variable test is assigned to one less than the number to be tested.
When the program prints out the answer (if it finds one) it should say something like - The square-root is ....

3 Solving extra tricky problems

Learn It

We all have problems, and we're all very busy.
Computers can perform calculations so quickly, that they can solve problems billions of times faster than a human ever could. So even if we have problems to solve that would take us too much time, we can get a computer to do it for us.
The problem has to be a computable one though.
Too often people believe that computers can solve any problem…

Learn It

You've already encountered an infinite loop.
Here's another one you can try if you've forgotten what an infinite loop is.

x = True
while x == True:
    print('Does this program halt?')
    print('\n'*3)

Infinite loops are a problem in designing programs. Have you ever had an application that just freezes until you are forced to kill it?

Wouldn't it be nice if we could have some way of detecting if a program would enter an infinite loop?

Research It

Imagine we create a program that we'll call A.
Could a program exist that can read the code of A and determine if A contains an infinite loop?
This problem is known as The Halting Problem.
Is it possible to design a program that can detect if another program will halt or just go into an infinite loop?
There are lots of resources online about The Halting Problem.
You might like to have a read of Scooping The Loop Snooper
Or have a look at the video below.

Or try an find your own explanations online.

Badge It - Platinum

Try and write your own explanation for Alan Turing's proof that The Halting Problem is undecidable.
Be sure to write this in your own words - Don't copy and paste answers