c  go  java  js  lua  py  vbs  rkt  scm  pro  

A deterministic computation has the same output for the same input.

A non-deterministic computation may have different output for the same input.

• randomness (pseudo-random sequence, etc.)
• parallel computation
• user input

Last time we covered intractability.

The term NP-Complete problem stands for Non-deterministic polynomial time complete problem. That is, the problem can only be solved in polynomial time an a non-deterministic Turing machine.

A famous (and first) NP-Complete is SAT (Satisfiability) of Boolean expressions. Hundreds of other problems are related to this problem. If any can be solved, all can be solved in reasonably time and space.

Another is determining whether a graph has a Hamiltonian cycle

An NP-hard problem is an intractable problem that is not NP-complete.

A famous NP-hard problem is the factoring of numbered, especially large composite numbers formed by multiplying two large prime numbers.

Another is the Traveling Salesperson Problem.

Most people are not used to working with low probabilities.

• The number of small particles in the universe is 2²⁷⁰.
• The number of seconds in 40 billion years in 2⁶⁰.
• The number of millionths of seconds in 40 billion years in 2⁸⁰.

Remember the train puzzle? The math view ignores reality. The engineering view takes into account reality.

Computer science has to do with data and information. Computer science is sometimes called informatics or information science (though there is a specialized field of computer science called information retrieval).

• What is computer science?
• What is data?
• What is information?

Can you go through a degree in computer science (B.S., M.S., Ph.D.) without ever defining computer science, data, or information?

Data can be considered everything in the universe.

Information is data that is valuable depending on the point of view.

Computer science is the search for finite representations of (potentially) infinite objects.

• The more finite the time, the less time it takes.
• The more finite the space, the less space it takes.

Taken to the extreme: AIG - Algorithmic Information Theory (Chaitin, Kolmolgorov, etc.).

Knuth defines computer science as the study of algorithms [Knuth??].

Knuth is the author of the series "The Art of Computer Programming", creator of TeX computer typesetting system.

Wirth defines programs as composed of data structures and algorithms [Wirth??].

Wirth is inventor of Pascal, Oberon, Modula-2.

• Data structures: data component
• Algorithms: code component

Code can be data and data can be code. Von Neumann first recognized this principle.

Compilers treat programs as data input and generate data output as programs.

Kowalski (Logic Programming) separates algorithms into logic and control components [Kowalski??].

• Logic is what is to be done.
• Control is how to do it.

Algorithm = Logic + Control.

• Declarative systems (Prolog, spreadsheets, word processors) require one to specify what one wants.
• Imperative languages require one to tell the computer what to do (C, C++, Java, etc.).

The essence of computer science is the search for finite representations of potentially infinite objects.

Computer/Information science can be thought of as the search for finite representations of (potentially) infinite objects?

Is this possible?

How many dots are red?


What is the ratio of red dots to blue dots?

The ratio of red dots to blue dots is one third or 1/3.


How is this represented in decimal notation?

The decimal notation for 1/3 is infinite.


How can we finitely represent this infinity?

Mathematical repetend notation can be used to show that the finite representation is "repeated".


How can we show this in graph notation as might be used in computer science?

We could print out this finite representation to any desired precision as long as we eventually stop. Lazy evaluation only continues as needed.


Do real numbers exist? Or are they just in the human imagination as a way of approximating results.

In computation, everything is finitely represented using bits, even real number approximations that are sometimes called floating point number (approximations).

English: "The beloved God has made all of the integers, everything else is the work of man." (Kronecker, Leopold, 1823-1891)

German: "Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk" (Kronecker, Leopold, 1823-1891)

Floating point numbers are approximations of mathematical real numbers. Here is an example.

Here is the C code.
#include <stdio.h> int main() { printf("(begin main)\n"); int i1 = 0; int n1 = 10; double d1 = 0.0; while (i1 != n1) { d1 += 0.1; i1 += 1; printf("%d/10 is %0.20lf\n", i1, d1); } printf("(end main)\n"); return 0; }
What is the output? Here is the output of the C code.
(begin main) 1/10 is 0.10000000000000000555 2/10 is 0.20000000000000001110 3/10 is 0.30000000000000004441 4/10 is 0.40000000000000002220 5/10 is 0.50000000000000000000 6/10 is 0.59999999999999997780 7/10 is 0.69999999999999995559 8/10 is 0.79999999999999993339 9/10 is 0.89999999999999991118 10/10 is 0.99999999999999988898 (end main)

Remember the "Towers of Hanoi" problem?

Here is the Python code.
def eagerMove(n, a, c, b): if n != 0: eagerMove(n-1,a,c,b) print("move {0:d} from {1:s} to {2:s}".format(n,a,b)) eagerMove(n-1,c,b,a) eagerMove(3,"A","B","C")
Here is the output of the Python code.
move 1 from A to C move 2 from A to C move 1 from B to A move 3 from A to C move 1 from B to A move 2 from B to A move 1 from C to B
Change the 3 to 80 and the program will not finish even in 15,000,000,000 (15 billion) years!

Here is the Python code.
def lazyMove(n, a, b, c): if n != 0: for move in lazyMove(n-1,a,c,b): yield move yield "move " + str(n) + " from " + a + " to " + b for move in lazyMove(n-1,c,b,a): yield move nextMove = lazyMove(80, "A", "C", "B") for i1 in range(0,10): print(next(nextMove))
Here is the output of the Python code.
move 1 from A to B move 2 from A to C move 1 from B to C move 3 from A to B move 1 from C to A move 2 from C to B move 1 from A to B move 4 from A to C move 1 from B to C move 2 from B to A

Gleick has a very interesting book on the history of information called "The Information".

This is useful reading for anyone interested in computer/information science.

The book is available in PDF form via the Internet from a variety of sites.

In order to build a computer, a switch is necessary.

A switch allows changing between one of two values (and is closely related to 2-valued logic).

When was the first programmable computer designed?

Charles Babbage designed a mechanical programmable computer in the 1830's, well ahead of his time. He is considered one of the first computer/information scientists.

The difference engine was never implemented in his lifetime. The technology was not sufficiently advanced.

Mechanical switches tend to be slow and prone to mechanical failure.

150 years later, a replica was built and it did work.

Ada Lovelace, assistant to Charles Babbage, is considered the first programmer, although the programs she wrote would never be executed in her lifetime.

The programming language Ada is named after Ada Lovelace.

Charles Morse invented a code, called the Morse code, whereby codes of electrical on-off pulses represented letters of an alphabet.

The Morse code was used to send messages via the telegraph.

In the 1920's, Hilbert (1928) proposed finding a consistent mathematical system that will allow all possible truths
to be decided. This would allow the automatic, or mechanical, proving of all possible truths.

Hilbert was proposing using mathematics to prove mathematics - what it could and could not do.

Hilbert is considered (by Chaitin and others) as the first meta-mathematician.

The book "Meta math!" by Gregory Chaitin has a good historical background of computability as will as his own basis for algorithmic information theory - the connection of randomness and information and computability and non-computability.

Hilbert invented/discovered the Hilbert curve, a monster curve that was not fully understood until the introduction of fractals a half-century later.

Mathematics is abstract and has no direct connection with reality. That was a goal of mathematicians at the start of the 20th century, motivated by the German mathematician Hilbert's 23 unsolved problems in mathematics, posed in 1900.

Any connection of mathematics with reality is left to others - philosophers, scientists, etc.

Levels of truth:

• logical truth - no connection with any reality - just symbol manipulation
• reality truth - measurements and theories consistent with reality, history, etc.
• human truth - opinion truth which may or may not make use of reality truth and/or logical truth.

Hilbert started the separation of mathematics from philosophers (human truth) and reality truth. Today, (pure) mathematics is a logical truth -symbol manipulation with no direct connection with reality truth or human truth.

Kurt Goedel stunned the mathematical world in 1931 by proving that it is impossible to find a consistent mathematical system that will allow all possible truths to be decided. This is called the Undecidability Theorem. The incompleteness theorem of Kurt Goedel (Incompleteness theorem (1931)) says that, for any formal proof system that includes arithmetic, there exist true statements that cannot be proven within the system.

Goedel's Undecidability Theorem states that any sufficiently powerful formal system (i.e., if it includes arithmetic) will have logical implications (i.e., true theorems) that are not provable within the system.

The implications of Goedel's Undecidability Theorem are that there were well-defined problems for which computer programs could not be written to solve.

Part of Goedel's motivation was the belief that there is no finite description of truth. That is, truth is infinite.

Almost no one attended Goedel's presentation of his results at the conference where it was presented.

Except one young Hungarian mathematician named John Von Neumann who would forever change the history of computers and many other fields.

Alonzo Church (1903-1995) was an American logician who invented the lambda calculus.

The Church-Turing hypothesis forms the basis of the limits of computation.

• Turing used an operational definition of a computing machine that become the basis of modern electronic digital computers.
• Church used functions and mathematics for a language that became Lisp and formed the foundation of modern functional programming languages.

Both systems can compute the same functions (and have the same limitations).

The lambda calculus is very simple.

An expression E is one of the following.

• A constant C
• A variable X
• An application of an expression to an expression as ( E . E )
• A function as lambda x . E (where x is the argument and E the body of the function)

The purpose of a simple language like lambda calculus is that properties of programming languages need only be proved for a few constructs.

Such a proof is called a structural induction proof.

The 0th generation of computers (1920's, 1930's) can be thought of as the development of the theory of computation, actually fairly well advanced before the first working fully programmable computer was implemented.

Alan Turning (1912-1954) published his work on the limits of computation and what would later be called the Turning machine in 1936. Turing needed to invent such a theoretical computer in order to prove some computability (and non-computable) properties.


Alan Turing helped break the German Enigma machine encryption during World War II (shortening the war by at least a year) and later defined a test to determine if a computer is intelligent.

But every computable computation (or, math terms, every recursively enumerable function) could be computed on a Turing Machine, a simplified model of computation that made use of a tape, a read-write head, and a control mechanism.

A Turing machine is an operational computer.

A Turing complete computer programming language is a language that can compute every computable function.

The most famous such undecidable problem is that Halting Problem. That is, write a computer program that, given any other computer program (and its data), decides whether that computer program (and its data) ever halts. It cannot be done.

A consequence of this theorem is that there are undecidable problem. One of these, the halting problem, can be stated as follows. Halting problem: It is impossible to write a computer program that looks at another computer program (and its data) and determines whether the other computer program eventually halts or whether it loops forever. Possible answers for a computation of an undecidable problem are yes (true), no (false), or maybe (wait forever).

If one could write a computer program to solve the halting problem, then mathematical theorems could be proved by writing a computer program to check the theorem. Such a theorem would be Goldbach's conjecture, stated as follows.

Goldbach's conjecture: Every even number can be represented as the sum of two primes.

Write a program and determine if the program halts.

The key idea in the proof of Goedel's Incompleteness Theorem is Cantor's diagonalization theorem, which can be stated as follows. Cantor's diagonalization theorem: There are infinitely more reals than integers. The integers are countably infinite. The reals are uncountably infinite. A proof outline is as follows. Assume that all the reals can be written down (even though there are an infinite number of them). Then show that after all reals have been written down, another not in the list can be determined. Thus a contradiction to the original assumption that the reals can be enumerated. A consequence is that there are infinitely more problems (mathematical functions) than there are algorithms (computer programs) to solve them.

One practical implication is that one cannot write a computer program that, in general, can detect all instances of a computer virus program.

How do you know if your submitted information is secure?

Assume there are no security problems. Possible answer: lock in the status area.

The lock does not mean that your information to be submitted is secure! The lock means that the transaction you just did is secure.

You are concerned with the next transaction.

Where is the next submission going?

• http://www.mybank.com
• https://www.mybank.com
• somewhere else?

You have to wait until the page is submitted.

In general, detecting this is an undecidable problem.

Most browsers provide a warning that "You are about to leave/enter a secure page" (unless turned off).

What do most web sites do? Most web sites make the page before the submitted information secure.

Exactly what is intelligence?

Have you ever taken an IQ (Intelligent Quotient) test?

Intelligence can be hard to define.

Artificial intelligence might be better called machine intelligence.

When is a computer intelligent?

Alan Turing (1912-1954) defined a test to determine if a computer is intelligent.

Alan Turing was one of many mathematicians that helped solved the German enigma code cipher. In doing so, it helped defeat Nazi Germany during World War II.

The Turing test to determine if a computer is intelligent goes as follows.

Put a person in one room with a teletype terminal to another room to type questions and get answers.

If that person cannot tell if there is a person or a computer at the other end, and it is a computer, then that computer is considered intelligent.

If you use IM (Instant Messaging) , how do you know if you are communicating with a human or a computer.

Random numbers are often used in statistics, computer science, data science, etc.

A random number is a number determined entirely by chance. That is, with no predictability.

In general, this is not possible.

No one has found any evidence that random numbers actually exist.

Everything in the universe seems to be deterministic (pre-determined).

We usually settle for numbers that I know and that you cannot easily guess.

How can random numbers be simulated?

Lava lamps can be used to simulate random numbers.

White noise (e.g., in electrical circuits) can be used to simulate random numbers.

Information theorist Gregory Chaitin (determining randomness) showed that there is no algorithm for determining whether a sequence of symbols is random. One must be informed of this.

Chaitin uses Lisp, a simple programming language, for experimenting with and defining the size of information algorithmically.

In practice, pseudo-random number sequences are used for encryption purposes.

• Security requires (as true as possible) random numbers.
• Other application can usually settle for pseudo-random numbers.

Von Neumann: Anyone who thinks they can generate random numbers with a computer is in a state of sin. (paraphrased).

Most of Chaitin's ideas were already known and published by Kolmolgorov. His groundbreaking work in information theory was in Russian and, at the time, not widely published outside the U.S.S.R.

11 questions omitted (login required)

2 acronyms omitted (login required)