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:
    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:
    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
    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
    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')
        print('Well done')
  • Create a new script and call it
  • 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
>>> 16127 * 16127 == 16129
>>> 16126 * 16126 == 16129
  • 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:
        stop = True
        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?')
  • 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