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 value20
- 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 thewhile
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 equals16129
>>> 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