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

• 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`?

• 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.