# 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**