Induction

Induction is not part of first-order logic, we get this from systems that are advanced enough to allow arithmetic.

If we know that P(0) is true.

And we know that P(k) ==> P(k+1) for all k>=0, then we know that
P(k) is true for all k>= 0.

Prove that the sum of the first n perfect squares is equal to n(n+1)(2n+1)/6 .

1^2 + 2^2 + 3^2 + 4^2 = 1 + 4+ 9 + 16  =30.
4(5)(9)/6 = 30.

Can I prove the formula for the first 0 perfect squares.
The sum of the first zero perfect squares is 0.
And (0)(1)(1)/6 = 0.

If I know it's true for the k perfect squares can I prove it true for the first (k+1) of them.

1^2 + 2^2 + 3^2 + ... + k^2 + (k+1)^2.

k(k+1)(2k+1)/6 + (k+1)^2

k(k+1)(2k+1)/6 + 6(k+1)(k+1)/6

(k+1)/6  k(2k+1)+6(k+1)

(k+1)/6  2k^2+k +6k + 6

(k+1)/6   2k^2+7k+6
(k+1)/6   2k^2 + 4k + 3k+6
(k+1)/6  2k (k+2) + 3 (k+2)
(k+1)/6  (2k+3)(k+2)

(k+1)(k+2)(2k+3)/6

(k+1) ((k+1)+1)  (2(k+1)+1)/6, which is exactly what we're trying to prove.

So, this proves it, and the algebra isn't that bad.

1 = 1
4 = 1+3
9 = 1+3+5
16 = 1+3+5+7
n 1's + 3(n-1) + 5(n-2)

Induction, because sometimes, especially in Computer Science, you have to use what is called "structural induction".  You're not using induction on numbers, but on "stuff."

For example, if you prove something true about the empty string, and then if you can demonstrate that if that property is true for all substrings of a certain string, then it must be true for the whole string, this would be structural induction.

In Programming Languages, we often use program structures for structural induction.  For example, if you prove a property true for a single line of code, and if can prove  that

A) if the property for all statements in a block, then it is true for the block
B) if the property is true for the if and else portions of an if, that this guarantees it being true for the entire if-else statement
C) if the property being true for the interior of a loop guarantees the property for the whole loop

you can conclude that this property is true for all programs, and this is structural induction.  You're doing induction on the structure of code:  Knowing it's true for the inside stuff and using that to prove it true for the whole structure, guarantees that it's true for all structures.

Assume there is a program, HALT (P,I) which returns true if P halts on input I and false if P infinite loops in input I.

I will write program G:

 if (HALT (G,G)) {
  while (1);
 }

Does G halt using its own source code as input?
Suppose G halts on its own input, so HALT (G,G) is true.

But look at the code, program G infinite loops if HALT (G,G) is true, so G doesn't halt at all, and certainly not on this or any other input.

So, G must not halt on its own source code, so HALT (G,G) is false, but again if HALT (G,G) is false, G clearly halts.

Again a contradiction, and our assumption must be false:  There is no such program HALT (P,I).

Incompleteness is that in any mathematical system containing arithmetic, there are statements that are true in all models but for which there is no proof.

x = 6;
while (1) {
 y = 1;
 ct = 0;
 while (y < x) {
  if prime (y) && prime (x-y) ct++;
 }
 if (ct==0) break
 x+=2;
}
print ("I Rock")  <== Is this line unreachable code?

Collatz Conjecture:  26==>13==>40==>20==>10==>5==>16==>8==>4==>2==>1

Turing Machine.

A series of states and transitions.  You also have a 2-way infinite tape.

You have a non-empty set called an "alphabet" (really good if there are at least two characters in the alphabet).

Every square on the tape contains exactly one character from the alphabet.

You also have a set of states, which you can have as instructions in a very crude programming language.

Each instruction looks at the character on the tape, and takes one the following actions:  it overwrites the character with a different character OR the tape head moves one position to the left OR the tape head moves one position to the right.  It then moves to a different state OR halts.

The Turing model is the most widely used model for computational "power."  In other words, any problem that can be solved on a real-life computer can be solved on a Turing Machine.  (Church's thesis, a speculation that no physical will ever be built than can solve a problem that a Turing machine cannot solve.)  In fact, since a Turing Machine has an infinite tape, it can solve problems that no physical computer can, since we haven't yet invented infinite memory.

The "rule of thumb" test for whether something is Turing-complete is whether an infinite loop can be programmed in the language or system.

Given x, write a program that finds the smallest prime number greater than x.

n = x+1;
while (n is not prime) n++;
return n;

while (property,ct) runs as long as property is true but no more than ct times.

The Turing model is the most widely used model for computational "power." but NOT for computational "efficiency".

1:  ("A",R,1)
    (" ",L,H)

This is a one-state Turing machine program, alphabet is A and space.
This moves right until it hits a space at which it moves left over the last A then halts.

1:  ("A",R,1)
    (" ","A",2)

2:  ("A",L,2)
    (" ",R,H)

Assuming my head is at the beginning of a string of A's (there is a space to the left of the head), this machine moves to the far right of the string, adds another A and then moves back to the beginning.