OOPortal
OOPortal

Structured Programming
«Prev
Next»

## Programming Fundamentals Prerequisites

## Concept and History of Algorithms

## Kolmogorov complexity

Lesson 2 | Programming Fundamentals Prerequisites |

Objective | Verify that you have the right background for this course. |

There really aren't any prerequisites for this course other than a general familiarity with computers and an interest in learning how to write computer programs.

No previous programming experience is required for this course.

If your background includes downloading and installing software from the Web or creating Web pages with HTML and a scripting language, then some of the tasks you will be asked to do in the course will be made a bit easier.

In the next lesson, you will learn what you need to take this course.

No previous programming experience is required for this course.

If your background includes downloading and installing software from the Web or creating Web pages with HTML and a scripting language, then some of the tasks you will be asked to do in the course will be made a bit easier.

In the next lesson, you will learn what you need to take this course.

The concept of algorithm has existed for centuries, however a partial formalization of what would become the *modern algorithm* began with attempts to solve the Entscheidungsproblem (the "decision problem") posed by
David Hilbert in 1928. Subsequent formalizations were framed as attempts to define "effective calculability" or the "effective method".

Alan Turing's*Turing machines* from 1936 to 1937 and 1939 gave a formal definition of algorithms, corresponding to the intuitive notion.

Alan Turing's

In *algorithmic information theory*, the Kolmogorov complexity of an object, such as a piece of text,
is the length of the shortest computer program in a programming language that produces the object as output. It is a measure of the computational resources needed to
specify the object, and is also known as descriptive complexity,

The notion of Kolmogorov complexity can be used to state and prove impossibility results akin to

- Kolmogorov-Chaitin complexity,
- algorithmic entropy, or
- program-size complexity.

The notion of Kolmogorov complexity can be used to state and prove impossibility results akin to

- Cantor's diagonal argument,
- Goedel's incompleteness theorem, and
- Turing's halting problem.