:: wikimiki.org ::

Algorithmic Information Theory

Algorithmic information theory

In computer science, the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity) of an object such as a piece of text is a measure of the computational resources needed to specify the object. For example consider the following two strings of length 100 0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101 1100100001100001110111101110110011111010010000100101011110010110001101111111010001100011011001110111 The first string admits a short English language description namely "50 repetitions of "01"". The second one has no obvious simple description other than writing down the string itself. More formally, the complexity of a string is the length of the string's shortest description in some fixed description language. The sensitivity of complexity relative to the choice of description language is discussed below. It can be shown that the Kolmogorov complexity of any string cannot be too much larger than the length of the string itself. Strings whose Kolmogorov complexity is small relative to the string's size are considered to be not complex. The notion of Kolmogorov complexity is surprisingly deep and can be used to state and prove impossibility results akin to Gödel's incompleteness theorem and Turing's halting problem. Algorithmic information theory is the area of computer science that studies Kolmogorov complexity and other complexity measures on strings (or other data structures). The field was developed by Andrey Kolmogorov, Ray Solomonoff and Gregory Chaitin starting in the late 1960s. There are several variants of Kolmogorov complexity or algorithmic information. The most widely used one is based on self-delimiting programs and is mainly due to Leonid Levin (1974).

Definition

To define Kolmogorov complexity, we must first specify a description language for strings. Such a description language can be based on a programming language such as Lisp, Pascal, or Java virtual machine bytecode. If P is a program which outputs a string x, then P is a description of x. The length of the description is just the length of P as a character string. In determining the length of P, the lengths of any subroutines used in P must be accounted for. The length of any integer constant n which occurs in the program P is the number of bits required to represent n, that is (roughly) log₂n. We could alternatively choose an encoding for Turing machines (TM), where an encoding is a function which associates to each TM M a bitstring . If M is a TM which on input w outputs string x, then the concatenated string w is a description of x. For theoretical analysis, this approach is more suited for constructing detailed formal proofs and is generally prefered in the research literature. In this article we will use an informal approach. Fix a description language. Any string s has at least one description, namely the program function GenerateFixedString() return s Among all the descriptions of s, there is one with shortest length denoted d(s). In case there is more than one program of the same minimal length, choose one arbitrarily, for example selecting the lexicographically first among them. d(s) is the minimal description of s. The Kolmogorov complexity of s, written K(s), is :

K(s) = |d(s)|. \quad

In the other words, K(s) is the length of the minimal description of s. We now consider how the choice of description language affects the value of K and show that the effect of changing the description language is bounded. Theorem. If K₁ and K₂ are the complexity functions relative to description languages L₁ and L₂, then there is a constant c (which depends only on the languages L₁ and L₂) such that :

|K_1(s) - K_2(s)| \leq c, \quad \forall s

By symmetry, it suffices to prove that there is some constant c such that for all bitstrings s, :

K_1(s) \leq K_2(s) + c.

To see why this is so, there is a program in the language L₁ which acts as an interpreter for L₂: function InterpretLanguage(string p) where p is a program in L₂. The interpreter is characterized by the following property: : Running InterpretLanguage on input p returns the result of running p. Thus if P is a program in L₂ which is a minimal description of s, then InterpretLanguage(P) returns the string s. The length of this description of s is the sum of # The length of the program InterpretLanguage, which we can take to be the constant c. # The length of P which by definition is K₂(s). This proves the desired upper bound. See also invariance theorem.

Basic results

In the following, we will fix one definition and simply write K(s) for the complexity of the string s. It is not hard to see that the minimal description of a string cannot be too much larger than the string itself: the program GenerateFixedString above that outputs s is a fixed amount larger than s Theorem. There is a constant c such that :

K(s) \leq |s| + c, \quad \forall s

The first surprising result is that there is no way to effectively compute K. Theorem. K is not a computable function. In other words, there is no program which takes a string s as input and produces the integer K(s) as output. We show this by contradiction. Suppose there is a program function KolmogorovComplexity(string s) that takes as input a string s and returns K(s). Now consider the program function GenerateComplexString(int n) for i = 1 to infinity: for each string s of length exactly i if KolmogorovComplexity(s) >= n return s quit This program calls KolmogorovComplexity as a subroutine. This program tries every string, starting with the shortest, until it finds a string with complexity at least n, then returns that string. Therefore, given any positive integer n, it produces a string with Kolmogorov complexity at least as great as n. The program itself has a fixed length U. The input to the program GenerateComplexString is an integer n; here, the size of n is measured by the number of bits required to represent n which is log₂(n). Now consider the following program: function GenerateParadoxicalString () return GenerateComplexString(n₀) This program calls GenerateComplexString as a subroutine and also has a free parameter n₀. This program outputs a string s whose complexity is at least n₀. By an auspicious choice of the parameter n₀ we will arrive at a contradiction. To choose this value, note s is described by the program GenerateParadoxicalString whose length is at most :

U + \log_2(n_0) + C  \quad

where C is the "overhead" added by the program GenerateParadoxicalString. Since n grows faster than log₂(n), there exists a value n₀ such that :

U + \log_2(n_0) + C < n_0. \quad

But this contradicts the definition of having a complexity at least n₀. Thus the program named "KolmogorovComplexity" cannot actually generate strings with the desired Kolmogorov complexity. This is proof by contradiction where the contradiction is similar to the Berry paradox: "Let n be the smallest positive integer that cannot be defined in fewer than twenty English words. Well, I just defined it in fewer than twenty English words."

Compression

It is however straightforward to compute upper bounds for K(s): simply compress the string s with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the resulting string's length. A string s is compressible by c if it has a description whose length does not exceed |s| − c. This is equivalent to saying K(s) ≤ |s| − c. Otherwise s is incompressible by c. A string incompressible by one is said to be simply incompressible; by the pigeonhole principle, incompressible strings must exist, since there are 2ⁿ bit strings of length n but only 2ⁿ-1 shorter strings. For the same reason, "most" strings are complex in the sense that they cannot be significantly compressed: K(s) is not much smaller than |s|, the length of s in bits. To make this precise, fix a value of n. There are 2ⁿ bitstrings of length n. The uniform probability distribution on the space of these bitstrings assigns to each string of length exactly n equal weight 2⁻ⁿ. Theorem. With the uniform probability distribution on the space of bitstrings of length n, the probability that a string is incompressible by c is at least 1 − 2^−c+1 + 2⁻ⁿ. To prove the theorem, note that the number of descriptions of length not exceeding n − c is given by the geometric series: :

1 + 2 + 2^2 + \cdots + 2^ = 2^-1.\quad

There remain at least :

2^n-2^+1 \quad

many bitstrings of length n that are incompressible by c. To determine the probability divide by 2ⁿ. This theorem is the justification for various challenges in [http://www.faqs.org/faqs/compression-faq/part1/ comp.compression FAQ]. Despite this result, it is sometimes claimed by certain individuals (considered cranks) that they have produced algorithms which uniformly compress data without lossage. See lossless data compression.

Chaitin's incompleteness theorem

We know that most strings are complex in the sense that they cannot be described in any significantly "compressed" way. However, it turns out that the fact that a specific string is complex cannot be proven, if the string's length is above a certain threshold. The precise formalization is as follows. First fix a particular axiomatic system S for the natural numbers. The axiomatic system has to be powerful enough so that certain assertions are formalizable in S and if these assertions are provable in S then they are true. See Gödel numbering. Theorem. There exists a constant L (which only depends on the particular axiomatic system and the choice of description language) such that there is no string s for which the statement :

K(s) \geq  L \quad

(as formalized in S) can be proven within the axiomatic system S. Note that by the abundance of nearly incompressible strings, the vast majority of those statements must be true. The proof of this result is a variant of the proof of Berry's paradox. The proof is by contradiction. If the theorem were false, then :Assumption (X): For any integer n there exists a string s for which there is a proof in S of the formula "K(s) ≥ n"(which we assume can be formalized in S). We can find an effective enumeration of all the formal proofs in S by some procedure function NthProof(int n) which takes as input n and outputs some proof. This function enumerates all proofs. Some of these are proofs for formulas we do not care about here (examples of proofs which will be listed by the procedure NthProof are the various known proofs of the law of quadratic reciprocity, those of Fermat's little theorem or the proof of Fermat's last theorem all translated into the formal language of S). A small fraction are complexity formulas of the form K(s) ≥ n where s and n constants in the language of S. There is a program function NthProofProvesComplexityFormula(int n) which determines whether the n^th proof actually proves a complexity formula K(s) ≥ L. The strings s and the integer L in turn are computable by programs: function StringNthProof(int n) function ComplexityLowerBoundNthProof(int n) Consider the folowing program function GenerateProvablyComplexString(int n) for i = 1 to infinity: if NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) >= n return StringNthProof(i) quit Given an n, this program tries every proof until it finds a string and a proof in the formal system S of the formula K(s) ≥ n. The program terminates by our Assumption (X). Now this program has a length U. There is an integer n₀ such that U+log₂(n₀) + C <n₀, where C is the overhead cost of function GenerateProvablyParadoxicalString() return GenerateProvablyComplexString(n₀) quit The program GenerateProvablyParadoxicalString outputs a string s for which K(s) ≥ n₀ can be formally proved in S. In particular K(s) ≥ n₀ is true. However, s is also described by a program of length U+log₂(n₀)+C so its complexity is less than n₀. This contradiction proves Assumption (X) cannot hold. Similar ideas are used to prove the properties of Chaitin's constant. The minimum message length principle of statistical and inductive inference and machine learning was developed by [http://www.csse.monash.edu.au/~dld/CSWallacePublications/ C.S. Wallace] and D.M. Boulton in 1968. MML is Bayesian (it incorporates prior beliefs) and information-theoretic. It has the desirable properties of statistical invariance (the inference transforms with a re-parametrisation, such as from polar coordinates to Cartesian coordinates), statistical consistency (even for very hard problems, MML will converge to any underlying model) and efficiency (the MML model will converge to any true underlying model about as quickly as is possible). [http://www.csse.monash.edu.au/~dld/CSWallacePublications/ C.S. Wallace] and D.L. Dowe showed a formal connection between MML and algorithmic information theory (or Kolmogorov complexity) in 1999.

References

- Ming Li and Paul Vitányi, An Introduction to Kolmogorv Complexity and Its Applications, Springer, 1997. [http://citeseer.ist.psu.edu/li97introduction.html Introduction chapter full-text].
- Yu Manin, A Course in Mathematical Logic, Springer-Verlag, 1977.
- Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997.

External links

- [http://www.kolmogorov.com/ The Legacy of Andrei Nikolaevich Kolmogorov]
- [http://www.cs.umaine.edu/~chaitin/ Chaitin's online publications]
- [http://www.idsia.ch/~juergen/ray.html Solomonoff's IDSIA page]
- [http://www.idsia.ch/~juergen/kolmogorov.html Schmidhuber's generalizations of algorithmic information]
- [http://homepages.cwi.nl/~paulv/kolmogorov.html Li & Vitanyi's textbook]
- [http://homepages.cwi.nl/~tromp/cl/cl.html Tromp's lambda calculus computer model offers a concrete definition of K()]
- [http://www3.oup.co.uk/computer_journal/hdb/Volume_42/Issue_04/pdf/420270.pdf Minimum Message Length and Kolmogorov Complexity] (by [http://www.csse.monash.edu.au/~dld/CSWallacePublications C.S. Wallace] and [http://www.csse.monash.edu.au/~dld D.L. Dowe], Computer Journal, Vol. 42, No. 4, 1999).
- [http://www.csse.monash.edu.au/~dld David Dowe]'s [http://www.csse.monash.edu.au/~dld/MML.html Minimum Message Length (MML)] and [http://www.csse.monash.edu.au/~dld/Occam.html Occam's razor] pages.
- P. Grunwald, M. A. Pitt and I. J. Myung (ed.), [http://mitpress.mit.edu/catalog/item/default.asp?sid=4C100C6F-2255-40FF-A2ED-02FC49FEBE7C&ttype=2&tid=10478 Advances in Minimum Description Length: Theory and Applications], M.I.T. Press, April 2005, ISBN 0-262-07262-9.
- [http://nms.lcs.mit.edu/~gch/kolmogorov.html Kolmogorov Complexity] provides a simple explanation of Kolmogorov complexity.
-
- ja:コルモゴロフ複雑性

Computer science

Computer science, an academic discipline (abbreviated CS or compsci), is a body of knowledge generally about computer hardware, software, computation and its theory. The discipline itself includes, but is not limited to, the fundamentals of computer languages, operating systems and mathematical foundations of computer science. The study of these fundamentals may lead to a wide variety of topics, such as algorithms, formal grammars, programming languages, program design, artificial intelligence and computer engineering. There exist a number of technical definitions of computer science. The status of computer science as a science is often challenged, typically arguing that it is more like mathematics and that it does not follow the scientific method, however these facts are not unanimously accepted. In popular language, the term computer science is often confusingly used to denominate anything related to computers.

History of computer science

Evolutionary

Before the 1920s, computers were human clerks that performed calculations. They were usually under the lead of a physicist. Many thousands of computers were employed in commerce, government, and research establishments. Most of these computers were women, and they were known to have a degree in calculus. After the 1920s, the expression computing machine refered to any machine that performed the work of a human computer, especially those in accordance with effective methods of The Church-Turing Thesis. The thesis states that a mathematical method is effective if it could be set out as a list of instructions able to be followed by a human clerk with paper and pencil, for as long as necessary, and without ingenuity or insight. Machines that computed with discrete values became known as the analog kind. They used machinery that represented discrete numeric quantities, like the angle of a shaft rotation or difference in electrical potential. Digital machinery, in contrast to analog, were able to render a state of a numeric value and store each individual digit. Digital machinery used difference engines or relays before the invention of faster memory devices. The phrase computing machine gradually gave away, after the late 1940s, to just computer as the onset of electronic digital machinery became common. These computers were able to perform the calculations that were performed by the previous human clerks. Since the values stored by digital machines were not bound to physical properties like the analog device, a logical computer, based on digital equipment, was able to do anything that could be described "purely mechanical." Alan Turing, known as the Father of Computer Science, invented such a logical computer, also known as a Turing Machine, that evolved into the modern computer from the tasks performed by the previous human clerks. These new computers were also able to perform non-numeric computations, like music. Computability, by logical computers, began a science by being able to make evident which was not explicitly defined into ordinary sense more immediate.

Academic discipline

Computer science has roots in electrical engineering, logic, mathematics, and linguistics. In the last third of the 20th century computer science emerged as a distinct discipline and developed its own methods and terminology. Originally, CS was taught as part of mathematics or engineering departments, for instance at the University of Cambridge in England and at the Gdansk University of Technology in Poland, respectively. Cambridge claims to have the world's oldest taught qualification in computing. The first computer science department in the United States was founded at Purdue University in 1962, while the first college entirely devoted to computer science was founded at Northeastern University in 1982. Most universities today have specific departments devoted to computer science, while some conjoin it with engineering, with applied mathematics, or other disciplines. Most research in computer science has focused on von Neumann computers or Turing machines (computation models that perform one small, deterministic step at a time). These models resemble, at a basic level, most real computers in use today. Computer scientists also study other models of computation, which includes parallel machines and theoretical models such as probabilistic, oracle, and quantum computers.

Careers

Some of the potential careers for those who study computer science are listed below:

Demographics

- Nearly half of all computer programmers held a bachelor’s degree in 2002; about 1 in 5 held a graduate degree. [http://www.bls.gov/oco/ocos110.htm]
- Computer programmer employment is expected to grow much more slowly than that of other computer specialists.
- Education requirements range from a 2-year degree to a graduate degree. [http://www.bls.gov/oco/ocos042.htm]
- Employment, other than computer programmer, is expected to increase much faster than the average as organizations continue to adopt increasingly sophisticated technologies.

Sub-disciplines of computer science

Computer Science has a number of major sub-fields which can be classified by a number of means (for example the [http://www.acm.org/class/1998/overview.html ACM classification system]).

Algorithms

The study of algorithms is aimed at creating techniques that will enable a computer to perform a certain task in an efficient manner. An algorithm is a set of well-defined instructions for accomplishing some task, often explained by analogy with a culinary recipe. Algorithms are often implemented in software, and advancing the state of the art in algorithms is responsible for many of the most spectacular successes in computing. An algorithms specialist may come up with methods to accomplish new tasks, but just as often, they will work on improving the efficiency of an existing algorithm. These improvements can come in "time" (the length of time it takes for the algorithm to work) and "space" (the amount of computer memory the algorithm consumes. The field of algorithms is highly formal and many things can be proved about a given algorithm (using complexity theory), including roughly how long it will take to complete, as compared to the size of its input (the number of options it must consider). One interesting open question in algorithms concerns the complexity classes P and NP, and whether or not P = NP. If it does, then a whole range of seemingly difficult algorithms can in theory be performed quickly.

Data structures

A data structure is a way to store data so that it can be remembered and retrieved efficiently. A well-designed data structure means that an algorithm can be performed using as little memory space and time as possible. Some data structures are very simple: the simplest is an array which is simply a numbered list of items. Since the memory of a computer is usually modelled as an array (of bytes), this is also one of the most important data structures in computer science. For example, strings of text are usually modelled as arrays. But there are many other data structures such as linked lists, trees, hash tables and many others that are quite different but critical to the science. Type theory classifies data at a most basic (mathematical) level into different types, such as integers, complex numbers, strings, etc. and deals with how those types can interact. Abstract data types, at a more concrete level, deal with how types and data structures are used in software programming.

Listing of sub-disciplines

Computer science is closely related to a number of fields. These fields overlap considerably, though important differences exist:

Major fields of importance for computer science

External links

- [http://www.dmoz.org/Computers/Computer_Science/ Open Directory Project: Computer Science]
- [http://www.techbooksforfree.com/science.shtml Downloadable Science and Computer Science books]
- [http://liinwww.ira.uka.de/bibliography/ Collection of Computer Science Bibliographies]
- [http://www.geocities.com/tablizer/science.htm Belief that title "science" in "computer science" is inappropriate] Category:Computer science ko:컴퓨터 과학 ja:情報工学 simple:Computer science th:วิทยาการคอมพิวเตอร์

String (computer science)

In computer programming and some branches of mathematics, strings are sequences of various simple objects. These simple objects are selected from a predetermined set, each entry of which is usually allocated a code. Most commonly these simple objects will be printable characters and the control codes that are used with them. The data types in which these are stored are also called strings and it is fairly common to use these types to store arbitrary, variable-length sequences of binary data. Generally, a string can be placed directly in the code usually by surrounding it with some form of quote marks (usually ' or ", as these are typeable on most keyboards worldwide). Sometimes the term binary string is used to refer to an arbitrary sequence of bits.

String datatypes

A string datatype is a datatype modeled on the idea of a formal string. Strings are such an important and useful datatype that they are implemented in nearly every programming language. In some languages they are available as primitive types and in others as composite types. The syntax of most high-level programming languages allows for a string, usually quoted in some way, to represent an instance of a string datatype; such a meta-string is called a literal or string literal. Although formal strings can have an arbitrary (but finite) length, the length of strings in real languages is often constrained to an artificial maximum. In general, there are two types of string datatypes: fixed length strings which have a fixed maximum length, and variable length strings whose length is not arbitrarily fixed. Most strings in modern programming languages are variable length strings. Despite the name, even variable length strings are limited in length; although, generally, the limit depends only on the amount of memory available. Historically, string datatypes had one byte for each character, and although the exact character set varied by region, the character encodings were similar enough that programmers could generally get away with ignoring this — groups of character sets used by the same system in different regions either had a character in the same place, or did not have it at all. Mostly these character sets were based on ASCII, though IBMs mainframe systems went their own way and used EBCDIC. Logographic languages such as Chinese, Japanese and Korean (known collectively as CJK) need far more than 256 characters — the limit of a one-byte-per-character encoding — for reasonable representation. The normal solutions involved keeping single-byte representations for ASCII and using two-byte representations for CJK ideographs. Use of these with existing code led to problems with matching and cutting of strings the severity of which depended on how the character encoding was designed. Some encodings such as the EUC family guarantee that a byte value in the ASCII range will only represent that ASCII character making the encoding safe for systems that use those characters as field separators or similar. Others such as ISO-2022 and shift-jis do not make such guarantees, making matching on byte codes unsafe. Another issue is that if the beginning of a string is cut off, important instructions for the decoder or information on position in a multibyte sequence may be lost. Another issue is that if strings are joined together (especially after having their ends truncated by code not aware of the encoding), the first string may not leave the encoder in a state suitable for dealing with the second string. Unicode has complicated the picture somewhat. Most languages have a datatype for Unicode strings (usually UTF-16 as it was usually added before Unicode supplemental planes were introduced). Converting between Unicode and local encodings requires an understanding of the local encoding, which may be problematic for existing systems where strings of various encodings are being transmitted together with no real marking as to what encoding they are in. Some languages like C++ implement strings as templates that can be used with any primitive type, but this is the exception not the rule.

Representations

Representations of strings depend heavily on the choice of character repertoire and the method of character encoding. Older string implementations were designed to work with repertoire and encoding defined by ASCII, or more recent extensions like the ISO 8859 series. Modern implementations often use the extensive repertoire defined by Unicode along with a variety of complex encodings such as UTF-8 and UTF-16. Most string implementations are very similar to variable-length arrays with the entries storing the character codes of corresponding characters. The principal difference is that, with certain encodings, a single logical character may take up more than one entry in the array. This happens for example with UTF-8, where single characters can take anywhere from one to four bytes. In these cases, the logical length of the string differs from the logical length of the array. The length of a string can be stored implicitly by using a special terminating character; often this is the null character having value zero, a convention used and perpetuated by the popular C programming language. Hence this representation is commonly referred to as C string. The length of a string can also be stored explicitly, for example by prefixing the string with integer value — a convention used in Pascal, consequently some people call it a P-string. In terminated strings, the terminating code is not an allowable character in any string. Here is an example of a null-terminated string stored in a 10-byte buffer, along with its ASCII representation:

F	R	A	N	K	NUL	k	e	f	w
46	52	41	4E	4B	00	6B	65	66	77

The length of a string in the above example is 5 characters, but it occupies 6 bytes. Characters after the terminator do not form part of the representation; they may be either part of another string or just garbage. Here is the equivalent (old style) Pascal string:

length	F	R	A	N	K	k	f	f	w
05	46	52	41	4E	4B	6B	66	66	77

While these representations are common, others are possible. Using ropes makes certain string operations, such as insertions, deletions, and concatenations more efficient.

Memory management

There are several serious memory management issues with strings, depending on the language these may be either handled invisiblly by the language or left up to the programmer.
- Making sure memory for strings that are no longer in use gets freed;
- Making sure strings that are still in use do not get freed;
- Making sure that a write to a memory block allocated to a string does not go past the end of the string. (Buffer overflow); and
- Making sure when a string is altered it does not have an unwanted/unexpected effect on other code. Different languages deal with the issue of strings and their memory management in different ways:
- C offers pointers to characters and the library supplies several functions which operate on strings as NUL terminated character sequences. The memory and buffer management must be dealt with by the programmer. This process is error prone and often leads to bugs when programmers get it wrong. In many cases these bugs have led to security holes (usually the famous buffer overflow attack). There is a notion that C's level string programming leads to higher performance, and it does for certain operations such as character extractions. However, the NUL terminated string design actually leads to much slower concatenation, comparison and string in string searching than the length prefixed method. C++ adopts the same interface for basic strings.
- Borland Pascal uses fixed-size arrays with a length byte at the beginning. The main weaknesses of this method are that it fundamentally limits the maximum length of the string (to 255), and always consumes memory for the whole buffer, even if the string itself is much shorter. The length limitation often forced coders to use character pointers to do things by hand like in C. On the other hand it does not involve the heap manager and therefore cannot cause a memory leak problem.
- Delphi 2 upwards (and freepascal in Delphi mode) uses reference counts maintained by the compiler. If an attempt is made to modify a string that has a reference count other than one, the string is copied first. Therefore, to the programmer, it looks like the string is being passed by-value but the huge overhead of copying the string on every assignment is removed. Unfortunately it also requires generation of what is effectively a try-finally block to ensure that the reference count is decreased when a procedure is exited by an exception. The main weakness of this is that it complicates multithreaded implementations of these languages, since reference counts need to be updated atomically.
- Garbage-collected languages like Microsoft .NET, Python, Perl, Lua and Java usually make strings an immutable class and let the garbage collector deal with strings that are no longer needed. This works well enough but can make string manipulation difficult and expensive so these languages usually have a second mutable class for doing string manipulation(StringBuffer in Java, StringBuilder in .NET, and so on).
- The C++ STL makes use of advanced language features such as copy constructors and destructors for non reference objects to allow a string template and class to be implemented that has semantics similar to a primitive type.

String algorithms

There are many algorithms for processing strings, each with various tradeoffs. Some categories of algorithms include
- string searching algorithms for finding a given substring or pattern;
- sorting algorithms;
- regular expression algorithms; and
- parsing a string. Advanced string algorithms often employ complex mechanisms and data structures, among them suffix trees and finite state machines.

String oriented languages and utilities

Strings are such a useful datatype that several languages have been designed in order to make string processing applications easy to write. Examples include the following languages:
- awk
- Icon
- Perl
- Ruby
- Tcl
- MUMPS
- Rexx
- sed
- SNOBOL Many UNIX utilities perform simple string manipulations and can be used to easily program some powerful string processing algorithms. Files and finite streams may be viewed as strings. Several string libraries for the C and C++ programming languages do exist which add greater functionality for string processing in those languages:
- [http://bstring.sf.net/ The Better String Library]
- [http://www.and.org/vstr/ The Vstr String Library]
- [http://www.pcre.org/ Perl Compatible Regular Expressions]
- [http://www.and.org/vstr/comparison Comparison page for C/C++ string libraries] Some APIs like Multimedia Control Interface, embedded SQL or printf use strings to hold commands that will be interpreted. Recent scripting programming languages, including Perl, Python, Ruby, and Tcl employ regular expressions to facilitate text operations.

Formal theory

One starts with a non-empty finite set Σ called an alphabet. Elements of this alphabet are called characters. A string (or word) over Σ is any finite sequence of characters from Σ. Infinite sequences of characters are not allowed in this definition. A particularly important string is the sequence of no characters, called the empty string. The empty string is often denoted ε or λ. For example, if Σ = , strings over Σ are of the form :ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, … The set of all strings over Σ is denoted Σ
- . One can define a binary operation on Σ
- called concatenation. If s and t are two strings, their concatenation, denoted st, is defined as the sequence of characters in s followed by the sequence of characters in t. For example, if s = bear and t = hug then st = bearhug and ts = hugbear. String concatenation is an associative, but non-commutative operation. The empty string serves as the identity element. In algebraic terms, the set Σ
- forms a monoid under string concatenation. In fact, Σ
- is the free monoid generated by Σ. The length of a string is the number of characters in the string. The length can be any natural number. The length of the empty string is 0. Algebraically speaking, the length function defines a monoid homomorphism from Σ
- to N (Non-negative integers with addition). A string s is said to be a substring or factor of t if there exist two strings u and v such that t = usv. One, or both, of u and v can be empty. The relation "is a substring of" defines a partial order on Σ
- , the least element of which is the empty string. More often, especially in computing applications, one is interested in a different kind of ordering on the set of strings. If the alphabet Σ is well-ordered (cf. alphabetical order) one can define a total ordering on Σ
- called lexicographical order. The empty string is also the least element with respect to this ordering. A set of strings over Σ (i.e. a subset of Σ
- ) is called a formal language over Σ. While the alphabet is a finite set and every string has finite length, a language may very well have infinitely many member strings. In fact, Σ
- itself is always an infinite language. Important examples of formal languages include regular expressions and formal grammars. Category:Data types Category:Formal languages Category:Character encoding Category:Data structures

Gödel's incompleteness theorem

In mathematical logic, Gödel's incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931.

First incompleteness theorem

Gödel's first incompleteness theorem is perhaps the most celebrated result in mathematical logic. It basically says that: : For any consistent formal theory including basic arithmetical truths, it is possible to construct an arithmetical statement that is true but not included in the theory. That is, any consistent theory of a certain expressive strength is incomplete. Here, "theory" has the special sense of a set of statements closed under logical inference rules. (A theory is in general an infinitely large set.) A theory is "consistent" if it contains no contradictions. The meaning of "it is possible to construct" is that there is some mechanical procedure which when given the axioms of the theory, produces another statement. That this statement is not included in the theory means that it cannot be derived from statements of the theory using the standard rules of first-order logic. The statement produced by the procedure is often referred to as "the Gödel sentence" for that theory, though there are actually infinitely many statements that have the same property (of being true but not provable from the theory). Roughly speaking, the Gödel statement, G, can be expressed: 'G is not provable'. If one were to suppose that G were provable (from the theory) then the theory would have a theorem, G, saying the opposite of what was just supposed. So we are forced to conclude that G is not provable; yet it is true. Q.E.D. The demonstration just given is in ordinary English and thus not mathematically rigorous. In order to provide a well-defined demonstration, Gödel represents statements by numbers; then the theory, which is already about numbers, also pertains to statements, including its own. Questions about the provability of statements are represented as mathematically definable questions about the properties of numbers, which would be decidable by the theory if it were complete. In these terms, the Gödel sentence is a claim that there does not exist a natural number with a certain property. A number with that property would be a proof of inconsistency of the theory. If there were such a number then the theory would be inconsistent, contrary to hypothesis. So there is no such number, and the Gödel statement is true, but the theory cannot prove it. Gödel demonstrated the incompleteness of a theory of arithmetic, but it is clear that the demonstration could be given for any theory and language of a certain expressiveness. Gödel originally proved a weaker theorem than the one stated above. In the theorem proved by Gödel the assumption is that the theory is (not just consistent but) omega-consistent. Omega-consistency is a technical concept which applies to a theory T if, for no property P, T proves that every specific natural number lacks P, yet T proves that there exists some natural number with P. Note that omega-consistency implies consistency, but consistency does not imply omega-consistency. J. Barkley Rosser later strengthened the theorem by removing the requirement for the theory to be omega-consistent. This is mostly of technical interest, since all true formal theories of arithmetic, i.e. theories the axioms of which are true statements about natural numbers, are omega-consistent and thus Gödel's original theorem applies to them.

Second incompleteness theorem

Gödel's second incompleteness theorem can be stated as follows: : For any formal theory T including basic arithmetical truths and also certain truths about formal provability, T includes a statement of its own consistency if and only if T is inconsistent. (Proof of the "if" part:) If T is inconsistent then anything can be proved, including that T is consistent. (Proof of the "only if" part:) If T is consistent then T does not include the statement of its own consistency. This follows from the first theorem. There is a technical subtlety involved in the second incompleteness theorem, namely how exactly are we to express the consistency of T in the language of T. There are many ways to do this, and not all of them lead to the same result. In particular, different formalizations of the claim that T is consistent may be inequivalent in T, and some may even be provable. For example, first order arithmetic (Peano arithmetic or PA for short) can prove that the largest consistent subset of PA is consistent. But since PA is consistent, the largest consistent subset of PA is just PA, so in this sense PA "proves that it's consistent". What PA does not prove is that the largest consistent subset of PA is, in fact, the whole of PA. (The term "largest consistent subset of PA" is rather vague, but what is meant here is the largest initial segment of the axioms of PA ordered according to some criteria, e.g. by "Gödel numbers", the numbers encoding the axioms as per the scheme used by Gödel mentioned above). In case of Peano arithmetic or any familiar explicitly axiomatized theory T, it is possible to define the consistency "Con(T)" of T in terms of the non-existence of a number with a certain property, as follows: "there does not exist an integer coding a sequence of sentences, such that each sentence is either one of the (canonical) axioms of T, a logical axiom, or an immediate consequence of preceding sentences according to the rules of inference of first order logic, and such that the last sentence is a contradiction". However, for arbitrary T there is no canonical choice for Con(T). The formalization of Con(T) depends on two factors: formalizing the notion of a sentence being derivable from a set of sentences and formalizing the notion of being an axiom of T. Formalizing derivability can be done in canonical fashion, so given an arithmetical formula A(x) defining a set of axioms we can canonically form the predicate Prov_A(P) which expresses that P is provable from the set of axioms defined by A(x). Using this predicate we can express Con(T) as "not Prov_A('P and not-P')". Solomon Feferman showed that Gödel's second incompleteness theorem goes through when the formula A(x) is chosen so that it has the form "there exists a number n satisfying the decidable predicate P" for some P. In addition, Prov_A(P) must satisfy the so-called Hilbert-Bernays provability conditions: 1. If T proves P, then T proves Prov_A(P) 2. T proves 1., i.e. T proves that if T proves P, then T proves Prov_A(P) 3. T proves that if T proves that (P implies Q) then T proves that provability of P implies provability of Q Gödel's second incompleteness theorem also implies that a theory T₁ satisfying the technical conditions outlined above can't prove the consistency of any theory T₂ which proves the consistency of T₁. This is because then T₁ can prove that if T₂ proves the consistency of T₁, then T₁ is in fact consistent. For the claim that T₁ is consistent has form "for all numbers n, n has the decidable property of not being a code for a proof of contradiction in T₁". If T₁ were in fact inconsistent, then T₂ would prove for some n that n is the code of a contradiction in T₁. But if T₂ also proved that T₁ is consistent, i.e. there is no such n, it would itself be inconsistent. We can carry out this reasoning in T₁ and conclude that if T₂ is consistent, then T₁ is consistent. Since by second incompleteness theorem, T₁ does not prove its consistency, it can't prove the consistency of T₂ either. This easy corollary of the second incompleteness theorem shows that there is no hope of proving e.g. the consistency of first order arithmetic using finitistic means provided we accept that finitistic means are correctly formalized in a theory the consistency of which is provable in PA. It's generally accepted that the theory of primitive recursive arithmetic (PRA) is an accurate formalization of finitistic mathematics, and PRA is provably consistent in PA. Thus PRA can't prove the consistency of PA. This is generally seen to show that Hilbert's program of validating the use of "ideal" mathematical principles to prove "real" (finitistic) mathematical statements by showing that the "ideal" principles are consistent by finitistically acceptable principles can't be carried out. This corollary is actually what makes the second incompleteness theorem epistemologically relevant. As Georg Kreisel remarked, it would actually provide no interesting information if a theory T proved its consistency. This is because inconsistent theories prove everything, including their consistency. Thus a consistency proof of T in T would give us no clue as to whether T really is consistent; no doubts about T's consistency would be resolved by such a consistency proof. The interest in consistency proofs lies in the possibility of proving the consistency of a theory T in some theory T' which is in some sense less doubtful than T itself, e.g. weaker than T. For most naturally occurring T and T', such as T = Zermelo-Fraenkel set theory and T' = primitive recursive arithmetic, the consistency of T' is provable in T, and thus T' can't prove the consistency of T by the above corollary of the second incompleteness theorem.

Gentzen's theorem

In 1936 Gerhard Gentzen proved the consistency of first order arithmetic. In itself, the result is rather trivial, since the consistency of first order arithmetic has a very easy proof: the axioms are true—in a mathematically defined sense—the rules of predicate calculus preserve truth and no contradiction is true, hence no contradiction follows from the axioms of first order arithmetic. What makes Gentzen's proof interesting is that it shows much more than merely that first order arithmetic is consistent. Gentzen showed that the consistency of first order arithmetic is provable, over the very weak base theory of primitive recursive arithmetic mentioned earlier, using the principle of quantifier free transfinite induction up to the ordinal ε₀. The principle of quantifier free transfinite induction up to epsilon-0 says that for any formula A(x) with no bound variables transfinite induction up to ε₀ holds. ε₀ is the first ordinal

\alpha

, such that

\alpha^\omega = \alpha

, i.e. the limit of the sequence: :

\omega,\ \omega^\omega,\ \omega^,\ \ldots

To express ordinals in the language of arithmetic a notation is needed, i.e. a way to assign natural numbers to ordinals less than ε₀. This can be done in various ways, one example provided by Cantor's normal form theorem. That transfinite induction holds for a formula A(x) means that A does not define an infinite descending sequence of ordinals smaller than ε₀ (in which case ε₀ would not be well-ordered). Gentzen assigned ordinals smaller than ε₀ to proofs in first order arithmetic and showed that if there is a proof of contradiction, then there is an infinite descending sequence of ordinals < ε₀ produced by a primitive recursive operation on proofs corresponding to a quantifier free formula. Gentzen's proof also highlights one commonly missed aspect of Gödel's second incompleteness theorem. It's sometimes claimed that the consistency of a theory can only be proved in a stronger theory. The theory obtained by adding quantifier free transfinite induction to primitive recursive arithmetic proves the consistency of first order arithmetic but is not stronger than first order arithmetic. For example, it doesn't prove ordinary mathematical induction for all formulae, while first order arithmetic does (it has this as an axiom schema). The resulting theory is not weaker than first order arithmetic either, since it can prove a number theoretical fact - the consistency of first order arithmetic - that first order arithmetic can't. The two theories are simply incomparable. Gentzen's proof is the first example of what is called proof theoretical ordinal analysis. In ordinal analysis one gauges the strength of theories by measuring how large (constructive) ordinals they can prove to be well-ordered, or equivalently for how large (constructive) ordinals is transfinite induction provable. A constructive ordinal is the order type of a recursive well-ordering of natural numbers.

Meaning of Gödel's theorems

Gödel's theorems are theorems in first-order logic, and must ultimately be understood in that context. In formal logic, both mathematical statements and proofs are written in a symbolic language, one where we can mechanically check the validity of proofs so that there can be no doubt that a theorem follows from our starting list of axioms. In theory, such a proof can be checked by a computer, and in fact there are computer programs that will check the validity of proofs. (Automatic proof verification is closely related to automated theorem proving, though proving and checking the proof are usually different tasks.) To be able to perform this process, we need to know what our axioms are. We could start with a finite set of axioms, such as in Euclidean geometry, or more generally we could allow an infinite list of axioms, with the requirement that we can mechanically check for any given statement if it is an axiom from that set or not (an axiom schema). In computer science, this is known as having a recursive set of axioms. While an infinite list of axioms may sound strange, this is exactly what's used in the usual axioms for the natural numbers, the Peano axioms: the inductive axiom is in fact an axiom schema - it states that if zero has any property and the successor of any natural number has that property, all natural numbers have that property - it does not specify which property and the only way to say in first-order logic that this is true of all properties is to have an infinite number of statements. Gödel's first incompleteness theorem shows that any such system that allows you to define the natural numbers is necessarily incomplete: it contains statements that are neither provably true nor provably false. The existence of an incomplete system is in itself not particularly surprising. For example, if you take Euclidean geometry and you drop the parallel postulate, you get an incomplete system (in the sense that the system does not contain all the true statements about Euclidean space). A system can be incomplete simply because you haven't discovered all the necessary axioms. What Gödel showed is that in most cases, such as in number theory or real analysis, you can never discover the complete list of axioms. Each time you add a statement as an axiom, there will always be another statement out of reach. You can add an infinite number of axioms; for example, you can add all true statements about the natural numbers to your list of axioms, but such a list will not be a recursive set. Given a random statement, there will be no way to know if it is an axiom of your system. If I give you a proof, in general there will be no way for you to check if that proof is valid. Gödel's theorem has another interpretation in the language of computer science. In first-order logic, theorems are recursively enumerable: you can write a computer program that will eventually generate any valid proof. You can ask if they have the stronger property of being recursive: can you write a computer program to definitively determine if a statement is true or false? Gödel's theorem says that in general you cannot. Many logicians believe that Gödel's incompleteness theorems struck a fatal blow to David Hilbert's program towards a universal mathematical formalism. The generally agreed upon stance is that the second theorem is what specifically dealt this blow. However some believe it was the first, and others believe that neither did.

Examples of undecidable statements

It should be noted that there are two distinct senses of the word "undecidable" in use. The first of these is the sense used in relation to Gödel's theorems, i.e., that of a statement being neither provable nor refutable, in some specified deductive system. The second sense is used in relation to recursion theory and applies not to statements but to decision problems, which are countably infinite sets of questions each requiring a yes/no answer. Such a problem is said to be undecidable if there is no recursive function that correctly answers every question in the problem set. The connection between these two is that if a decision problem is undecidable (in the recursion theoretical sense) then there is no consistent formal system which proves for every question A in the problem either "the answer to A is yes" or "the answer to A is no". (For this reason, the term "independent" is often preferred to "undecidable", for the "neither provable nor refutable" sense. However "independent" is also ambiguous; some use it to mean just "not provable", and leave open whether an independent statement might be refuted.) It should be noted that undecidability of a statement, in a particular deductive system, does not in and of itself address the question of whether the truth value of the statement is well-defined, or whether it can be known. It says only that the particular deductive system being considered does not decide the issue. Whether there exist so-called "absolutely undecidable" statements, whose truth value can never be known or is ill-specified, is a controversial point among various philosophical schools. The subsequent combined work of Gödel and Paul Cohen has given concrete examples of undecidable statements (statements that, in some specified deductive system, can be neither proved nor disproved): The continuum hypothesis can neither be proved nor refuted in ZFC (the standard axiomatization of set theory), and the axiom of choice can neither be proved nor refuted in ZF (which is all the ZFC axioms except the axiom of choice). These results do not require the incompleteness theorem. In 1936, Alan Turing proved that the halting problem—the question of whether or not a Turing machine halts on a given program—is undecidable, in the second sense of the term. This result was later generalised in the field of recursive functions to Rice's theorem which shows that all non-trivial properties of recursive functions are undecidable, i.e. there is no recursive function which returns 1 when given a description of a recursive function having the property and 0 otherwise. In 1973, the Whitehead problem in group theory was shown to be undecidable, in the first sense of the term, in standard set theory. In 1977, Kirby, Paris and Harrington proved that a statement in combinatorics, a version of the Ramsey theorem, is undecidable in the axiomatization of arithmetic given by the Peano axioms but can be proven to be true in the larger system of set theory. Kruskal's tree theorem, which has applications in computer science, is also undecidable from the Peano axioms but provable in set theory. In fact Kruskal's tree theorem (or its finite form) is undecidable in a much stronger system codifying the principles acceptable on basis of a philosophy of mathematics called predicativism. Goodstein's theorem is a relatively simple statement about natural numbers that is undecidable in Peano arithmetic. Gregory Chaitin produced undecidable statements in algorithmic information theory and in fact proved his own incompleteness theorem in that setting. One of the first problems suspected to be undecidable, in the second sense of the term, was the word problem for groups, first posed by Max Dehn in 1911, which asks if there is a finitely presented group for which no algorithm exists to determine whether two words are equivalent. This was shown to be the case in 1952.

Misconceptions about Gödel's theorems

Since Gödel's first incompleteness theorem is so famous, it has given rise to many misconceptions. They are refuted here: # The theorem does not imply that every interesting axiom system is incomplete. For example, Euclidean geometry can be axiomatized so that it is a complete system. (In fact, Euclid's original axioms are pretty close to being a complete axiomatization. The missing axioms express properties that seem so obvious that it took the emergence of the idea of a formal proof before their absence was noticed.) # The theorem only applies to systems that allow you to define the natural numbers as a set. It is not sufficient that the system contain the natural numbers. You must also be able to express the concept "

x

is a natural number" using your axioms and first-order logic. There are plenty of systems that contain the natural numbers and are complete. For example both the real numbers and complex numbers have complete axiomatizations. # The theorem only applies to systems that are used as their own proof systems. Gentzen's work shows the consequences of using a proof theory that is not the same theory, but a more powerful one.

Discussion and implications

The incompleteness results affect the philosophy of mathematics, particularly viewpoints like formalism, which uses formal logic to define its principles. One can paraphrase the first theorem as saying that "we can never find an all-encompassing axiomatic system which is able to prove all mathematical truths, but no falsehoods." On the other hand, from a strict formalist perspective this paraphrase would be considered meaningless because it presupposes that mathematical "truth" and "falsehood" are well-defined in an absolute sense, rather than relative to each formal system. The following rephrasing of the second theorem is even more unsettling to the foundations of mathematics: :If an axiomatic system can be proven to be consistent and complete from within itself, then it is inconsistent. Therefore, in order to establish the consistency of a system S, one needs to utilize some other more powerful system T, but a proof in T is not completely convincing unless T's consistency has already been established without using S. The consistency of the Peano axioms for natural numbers for example can be proven in set theory, but not in the theory of natural numbers alone. This provides a negative answer to problem number 2 on David Hilbert's famous list of important open questions in mathematics (called Hilbert's problems). In principle, Gödel's theorems still leave some hope: it might be possible to produce a general algorithm that for a given statement determines whether it is undecidable or not, thus allowing mathematicians to bypass the undecidable statements altogether. However, the negative answer to the Entscheidungsproblem shows that no such algorithm exists. There are some who hold that a statement that is unprovable within a deductive system may be quite provable in a metalanguage. And what cannot be proven in that metalanguage can likely be proven in a meta-metalanguage, recursively, ad infinitum, in principle. By invoking a sort of super Theory of Types with an axiom of Reducibility -- which by an inductive assumption applies to the entire stack of languages -- one may, for all practical purposes, overcome the obstacle of incompleteness. Note that Gödel's theorems only apply to sufficiently strong axiomatic systems. "Sufficiently strong" means that the theory contains enough arithmetic to carry out the coding constructions needed for the proof of the first incompleteness theorem. Essentially, all that is required are some basic facts about addition and multiplication as formalized, e.g., in Robinson arithmetic Q. There are even weaker axiomatic systems that are consistent and complete, for instance Presburger arithmetic which proves every true first-order statement involving only addition. The axiomatic system may consist of infinitely many axioms (as first-order Peano arithmetic does), but for Gödel's theorem to apply, there has to be an effective algorithm which is able to check proofs for correctness. For instance, one might take the set of all first-order sentences which are true in the standard model of the natural numbers. This system is complete; Gödel's theorem does not apply because there is no effective procedure that decides if a given sentence is an axiom. In fact, that this is so is a consequence of Gödel's first incompleteness theorem. Another example of a specification of a theory to which Gödel's first theorem does not apply can be constructed as follows: order all possible statements about natural numbers first by length and then lexicographically, start with an axiomatic system initially equal to the Peano axioms, go through your list of statements one by one, and, if the current statement cannot be proven nor disproven from the current axiom system, add it to that system. This creates a system which is complete, consistent, and sufficiently powerful, but not recursively enumerable. Gödel himself only proved a technically slightly weaker version of the above theorems; the first proof for the versions stated above was given by J. Barkley Rosser in 1936. In essence, the proof of the first theorem consists of constructing a statement p within a formal axiomatic system that can be given a meta-mathematical interpretation of: :p = "This statement cannot be proven in the given formal theory" As such, it can be seen as a modern variant of the Liar paradox, although unlike the classical paradoxes it's not really paradoxical. If the axiomatic system is (omega-)consistent, Gödel's proof shows that p (and its negation) cannot be proven in the system. Therefore p is true (p claims to be not provable, and it is not provable) yet it cannot be formally proved in the system. Note that adding p to the axioms of the system would not solve the problem: there would be another Gödel sentence for the enlarged theory.

Minds and machines

Many scholars have debated over what Gödel's incompleteness theorem implies about human intelligence. Much of the debate centers on whether the human mind is equivalent to a Turing machine, or by the Church-Turing thesis, any finite machine at all. If it is, and if the machine is consistent, then Gödel's incompleteness theorems would apply to it. One of the earliest attempts to use incompleteness to reason about human intelligence was by Gödel himself in his 1951 Gibbs lecture entitled "Some basic theorems on the foundations of mathematics and their philosophical implications." In this lecture, Gödel uses the incompleteness theorem to arrive at the following disjunction: (a) the human mind is not a consistent finite machine, or (b) there exist Diophantine equations for which it cannot decide whether solutions exist. Gödel finds (b) implausible, and thus seems to have believed the human mind was not equivalent to a finite machine, i.e., its power exceeded that of any finite machine. However, he recognized that this was only a conjecture, since he could not disprove (b). In subsequent years, more direct anti-mechanist lines of reasoning were apparently floating around the intellectual atmosphere. In 1960, Hilary Putnam published a paper entitled "Minds and Machines," in which he points out the flaws of a typical anti-mechanist argument. Informally, this is the argument that the (alleged) difference between "what can be mechanically proven" and "what can be seen to be true by humans" shows that human intelligence is not mechanical in nature. Or, as Putnam puts it:

Let T be a Turing machine which "represents" me in the sense that T can prove just the mathematical statements I prove. Then using Gödel's technique I can discover a proposition that T cannot prove, and moreover I can prove this proposition. This refutes the assumption that T "represents" me, hence I am not a Turing machine.

Putnam objects that this argument ignores the issue of consistency. Gödel's technique can only be applied to consistent systems. It is possible, argues Putnam, that the human mind is inconsistent. J. R. Lucas in Minds, Machines and Gödel (1963), and later in his book The Freedom of the Will (1970), lays out an anti-mechanist argument closely following the one described by Putnam, including reasons for why the human mind can be considered consistent. Lucas admits that, by Gödel's second theorem, a human mind cannot formally prove its own consistency, and even says (perhaps facetiously) that women and politicians are inconsistent. Nevertheless, he sets out arguments for why a male non-politician can be considered consistent. These arguments are philosophical in nature and are the subject of much debate; Lucas provides references to responses on his own [http://users.ox.ac.uk/~jrlucas/Godel/referenc.html website]. Another notable work was done by Judson Webb in his 1968 paper "Metamathematics and the Philosophy of Mind." Webb claims that previous attempts have glossed over whether one truly can see that the Gödelian statement p pertaining to oneself, is true. Using a different formulation of Gödel's theorems, namely, that of Raymond Smullyan and Emil Post, Webb shows one can derive convincing arguments for oneself of both the truth and falsity of p. He furthermore argues that all arguments about the philosophical implications of Gödel's theorems are really arguments about whether the Church-Turing thesis is true. Later, Roger Penrose entered the fray, providing somewhat novel anti-mechanist arguments in his books, The Emperor's New Mind (1989) [ENM] and Shadows of the Mind (1994) [SM]. These books have proved highly controversial. Martin Davis responded to ENM in his paper [http://www.cs.nyu.edu/cs/faculty/davism/penrose.ps "Is Mathematical Insight Algorithmic?" (ps)], where he argues that Penrose ignores the issue of consistency. Solomon Feferman gives a critical examination of SM in his paper [http://math.stanford.edu/~feferman/papers/penrose.pdf "Penrose's Gödelian argument" (pdf)].

Proof sketch for the first theorem

The main problem in fleshing out the above mentioned proof idea is the following: in order to construct a statement p that is equivalent to "p cannot be proved", p would have to somehow contain a reference to p, which could easily give rise to an infinite regress. Gödel's ingenious trick, which was later used by Alan Turing to solve the Entscheidungsproblem, will be described below. To begin with, every formula or statement that can be formulated in our system gets a unique number, called its Gödel number. This is done in such a way that it is easy to mechanically convert back and forth between formulas and Gödel numbers. Because our system is strong enough to reason about numbers, it is now also possible to reason about formulas. A formula F(x) that contains exactly one free variable x is called a statement form. As soon as x is replaced by a specific number, the statement form turns into a bona fide statement, and it is then either provable in the system, or not. Statement forms themselves are not statements and therefore cannot be proved or disproved. But every statement form F(x) has a Gödel number which we will denote by G(F). The choice of the free variable used in the form F(x) is not relevant to the assignment of the Gödel number G(F). By carefully analyzing the axioms and rules of the system, one can then write down a statement form P(x) which embodies the idea that x is the Gödel number of a statement which can be proved in our system. Formally: P(x) can be proved if x is the Gödel number of a provable statement, and its negation ~P(x) can be proved if it isn't. (While this is good enough for this proof sketch, it is technically not completely accurate. See Gödel's paper for the problem and Rosser's paper for the resolution. The key word is "omega-consistency".) Now comes the trick: a statement form F(x) is called self-unprovable if the form F, applied to its own Gödel number, is not provable. This concept can be defined formally, and we can construct a statement form SU(z) whose interpretation is that z is the Gödel number of a self-unprovable statement form. Formally, SU(z) is defined as: z = G(F) for some particular form F(x), and y is the Gödel number of the statement F(G(F)), and ~F(y). Now the desired statement p that was mentioned above can be defined as: :p = SU(G(SU)). Intuitively, when asking whether p is true, we ask: "Is the property of being self-unprovable itself self-unprovable?" This is very reminiscent of the Barber paradox about the barber who shaves precisely those people who don't shave themselves: does he shave himself? We will now assume that our axiomatic system is consistent. If p were provable, then SU(G(SU)) would be true, and by definition of SU, z = G(SU) would be the Gödel number of a self-unprovable statement form. Hence SU would be self-unprovable, which by definition of self-unprovable means that SU(G(SU)) is not provable, but this was our p: p is not provable. This contradiction shows that p cannot be provable. If the negation of p= SU(G(SU)) were provable, then by definition of SU this would mean that z = G(SU) is not the Gödel number of a self-unprovable form, which implies that SU is not self-unprovable. By definition of self-unprovable, we conclude that SU(G(SU)) is provable, hence p is provable. Again a contradiction. This one shows that the negation of p cannot be provable either. So the statement p can neither be proved nor disproved within our system.

Proof sketch for the second theorem

Let p stand for the undecidable sentence constructed above, and let's assume that the consistency of the system can be proven from within the system itself. We have seen above that if the system is consistent, then p is not provable. The proof of this implication can be formalized in the system itself, and therefore the statement "p is not provable", or "not P(p)" can be proven in the system. But this last statement is equivalent to p itself (and this equivalence can be proven in the system), so p can be proven in the system. This contradiction shows that the system must be inconsistent.

References

Scientific articles

- K. Gödel: [http://home.ddc.net/ygg/etext/godel/ Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I.] Monatshefte für Mathematik und Physik, 38 (received 17 Nov 1930, published 1931), pp. 173-198. Translated in van Heijenoort: From Frege to Gödel. Harvard University Press, 1971.
- K. Gödel: Some basic theorems on the foundations of mathematics and their implications (1951). Printed in Collected works / Kurt Gödel v.III; edited by Solomon Feferman. Clarendon Press ; New York : Oxford University Press, 1995. pp. 304-323.
- J.R. Lucas: [http://users.ox.ac.uk/~jrlucas/Godel/mmg.html Minds, Machines, and Gödel]. Philosophy XXXVI (1961):112-127.
- Putnam, Hilary. Minds and Machines, Dimensions of Mind: A Symposium, edited by Sidney Hook. New York University Press: New York, 1960. Reprinted in Minds and Machines, edited by A.R. Anderson, Prentice-Hall: Englewood Cliffs, New Jersey, 1964. page 77.
- B. Rosser: Extensions of some theorems of Gödel and Church. Journal of Symbolic Logic, 1 (1936), N1, pp. 87-91.
- J. Webb. Metamathematics and the Philosophy of Mind. Philosophy of Science, Vol 35, Issue 2, (Jun 1968):156-178.

Books

- Hao Wang: A Logical Journey: From Gödel to Philosophy Bradford Books (January 10, 1997) ISBN 0262231891
- Kārlis Podnieks: Around Goedel's Theorem, http://www.ltn.lv/~podnieks/gt.html
- D. Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid, 1979, ISBN 0465026850. (1999 reprint: ISBN 0465026567).
- Ernest Nagel, James Roy Newman, Douglas R. Hofstadter: Gödel's Proof, revised edition (2002). ISBN 0814758169.
- [http://aleph0.clarku.edu/~djoyce/hilbert/problems.html#prob2 Hilbert's second problem] (English translation)
- Norbert Domeisen, Logik der Antinomien. Bern etc.: Peter Lang. 142 S. 1990. (ISBN 3-261-04214-1), [http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?first=1&maxdocs=3&type=html&an=0724.03003&format=complete Zentralblatt MATH]
- Torkel Franzén, Gödel's Theorem: An Incomplete Guide to its Use and Abuse, AK Peters (2005), ISBN 1568812388
- Peter Smith, [http://www.godelbook.net/ An Introduction to Gödel's Theorems], (Forthcoming)

External web pages

- [http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Godel.html Gödel's biography with photo]
- [http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Gentzen.html Gentzen's biography with photo]
- [http://www.miskatonic.org/godel.html Godel's Theorem explained further] Category:Mathematical theorems Category:Mathematical logic Category:Model theory Category:Proof theory ko:불완전성 정리 ja:ゲーデルの不完全性定理

Data structure

In computer science, a data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow a more efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data structure. A well-designed data structure allows a variety of critical operations to be performed, using as little resources, both execution time and memory space, as possible. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to certain tasks. For example, B-trees are particularly well-suited for implementation of databases, while routing tables rely on networks of machines to function. In the design of many types of programs, the choice of data structures is a primary design consideration, as experience in building large systems has shown that the difficulty of implementation and the quality and performance of the final result depends heavily on choosing the best data structure. After the data structures are chosen, the algorithms to be used often become relatively obvious. Sometimes things work in the opposite direction - data structures are chosen because certain key tasks have algorithms that work best with particular data structures. In either case, the choice of appropriate data structures is crucial. This insight has given rise to many formalised design methods and programming languages in which data structures, rather than algorithms, are the key organising factor. Most languages feature some sort of module system, allowing data structures to be safely reused in different applications by hiding their verified implementation details behind controlled interfaces. Object-oriented programming languages such as C++ and Java in particular use objects for this purpose. Since data structures are so crucial to professional programs, many of them enjoy extensive support in standard libraries of modern programming languages and environments, such as C++'s Standard Template Library, the Java API, and the Microsoft .NET framework. The fundamental building blocks of most data structures are arrays, records, discriminated unions, and references. For example, the nullable reference, a reference which can be null, is a combination of references and discriminated unions, and the simplest linked data structure, the linked list, is built from records and nullable references. There is some debate about whether data structures represent implementations or interfaces. How they are seen may be a matter of perspective. A data structure can be viewed as an interface between two functions or as an implementation of methods to access storage that is organized according to the associated data type.

External links

- [http://nist.gov/dads/ Descriptions] from the Dictionary of Algorithms and Data Structures
- [http://hal9k.com/cug/links/subject39.htm Links from the C/C++ User’s Group Page] Category:Data_structures ko:자료구조 ja:データ構造 th:โครงสร้างข้อมูล

Ray Solomonoff

Ray Solomonoff (born 1926) invented the concept of algorithmic probability around 1960. Take a universal computer and randomly generate an input program. The program will generate some possibly infinite output. The algorithmic probability of any given finite output prefix q is the sum of the probabilities of the programs that compute something starting with q. Algorithmic probability is the main ingredient of Solomonoff's theory of inductive inference, the theory of prediction based on observations. Given a sequence of symbols -- which will come next? Solomonoff's theory provides an answer that is optimal in a certain sense. Unlike Karl Popper's informal theory, Solomonoff's is mathematically sound. Algorithmic probability is closely related to the concept of Kolmogorov complexity. In fact, Solomonoff was the first to prove the invariance theorem, which shows that it is not really important which computer we use.
- [http://world.std.com/~rjs/ray.html Ray Solomonoff's Homepage] Solomonoff, Ray

Gregory Chaitin

Gregory J. Chaitin (born 1947) is an Argentine-American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made important contributions to algorithmic information theory, in particular a new incompleteness theorem similar in spirit to Gödel's incompleteness theorem. In 1995 he was given the degree of doctor of science honoris causa by the University of Maine. In 2002 he was given the title of honorary professor by the University of Buenos Aires in Argentina, where his parents were born and where Chaitin spent part of his youth. He is a research staff member at IBM's Thomas J. Watson Research Center and also a visiting professor at the Computer Science Department of the University of Auckland, and on the international committee of the Valparaíso Complex Systems Institute. Chaitin has defined Chaitin's constant

\ \Omega

, a real number whose digits are equidistributed and which expresses the probability that a random program will halt.

\ \Omega

has numerous remarkable mathematical properties, including the fact that it is definable but not computable. Chaitin's work on algorithmic information theory paralleled the earlier work of Kolmogorov in many respects.

Books

- Algorithmic Information Theory, ([http://www.cup.org Cambridge University Press], 1987),
- Information, Randomness & Incompleteness, ([http://www.worldscientific.com World Scientific], 1987),
- Information-Theoretic Incompleteness, ([http://www.worldscientific.com World Scientific], 1992),
- The Limits of Mathematics, ([http://www.springeronline.com Springer-Verlag] 1998),
- The Unknowable, ([http://www.springeronline.com Springer-Verlag] 1999),
- Exploring Randomness, ([http://www.springeronline.com Springer-Verlag] 2001),
- Conversations with a Mathematician, ([http://www.springeronline.com Springer-Verlag] 2002),
- From Philosophy to Program Size, ([http://ioc.ee Tallinn Cybernetics Institute] 2003),
- Meta Math!, ([http://www.randomhouse.com/pantheon Pantheon] 2005).

External links

- [http://cs.umaine.edu/~chaitin/ G J Chaitin Home Page]
- [http://cs.umaine.edu/~chaitin/complete.html List of publications of G J Chaitin]
- [http://www.dc.uba.ar/people/profesores/becher/ns.html New Scientist article (March, 2001) on Chaitin, Omegas and Super-Omegas] Chaitin, Gregory Chaitin, Gregory Chaitin, Gregory Chaitin, Gregory Chaitin, Gregory Chaitin, Gregory ja:グレゴリー・チェイティン

1960s

The 1960s in its most obvious sense refers to the decade between 1960 and 1969, but the expression has taken on a wider meaning over the past twenty years. The Sixties has come to refer to the complex of inter-related cultural and political events which occurred in approximately that period, in western countries, particularly Britain, France, the United States and West Germany. Social upheaval was not limited to just these nations, reaching large scale in nations such as Japan, Mexico and Canada as well. The term is used both nostalgically by those who participated in those events, and pejoratively by those who regard the time as a period whose harmful effects are still being felt today. The decade was also labelled the Swinging Sixties because of the libertine attitudes that emerged during the decade. Popular memory has conflated into the Sixties some events which did not actually occur during the period. For example, although some of the most dramatic events of the American civil rights movement occurred in the early 1960s, the movement had already began in earnest during the 1950s. On the other hand, the rise of feminism and gay rights began only in the very late 1960s and did not fully flower until the Seventies. However, the "Sixties" has become synonymous with all the new, exciting, radical, subversive and/or dangerous (according to one's viewpoint) events and trends of the period.

Events and trends

Many of the trends of the 1960s were due to the demographic changes brought about by the baby boom generation, the height of the Cold War, and the dissolution of European colonial empires. The rise in social revolution, civil rights movements, human rights movement, anti-War movements, and the Counterculture movement are only some of the characteristics that defined the 1960s. Many experts attribute the 1960s "counter-culture revolution" as being the result of the major social and political factors that rose in the 1950s like brinksmanship, continued fighting in the 3rd world, and a return to pre-WWII lifestyle. The new generation was determined to reject a pre-WWII conformist lifestyle with men in suits and women in the kitchen. While many believed it to be just a "Western" phenomenon, the '60s revolution spread far beyond the borders of America and Western Europe. In South America, revolutions were at a height, in the Eastern Bloc, movements were made inspired by the Hungarian Revolution to reject Soviet domination, and in the Middle East attempted to resist Soviet and American domination (see Non-Aligned Movement). Overall, the '60s affected almost the entire globe. It was during this time that protectionist, command, and mixed economies reached their peak...

Technology

Non-Aligned Movement Non-Aligned Movement]
- USSR puts first man (Yuri Gagarin) and first woman (Valentina Tereshkova) in outer space
- The United States puts man on Earth's Moon (see Apollo 11)
- Geosynchronous satellites revolutionize global communications
- Start of the development of algorithmic information theory
- The ARPAnet, precursor of the Internet, is founded in 1969 as a United States Department of Defense project. The numbered series of Request For Comments (RFC) documents begins in order to document the standards and practices of this network, and continues to this day
- Direct Use of the Sun's Energy by pioneer solar-energy scientist Farrington Daniels is published (1964)
- Compact audio cassette introduced; begins to displace reel-to-reel audio tape recording for home users

Science

- Discovery of plate tectonics revolutionizes understanding of continental drift
- Jacques Monod and Francois Jacob discover the lac operon
- Rise of the science of ecology in the awareness of the intelligentsia

War, peace and politics

intelligentsia"]] intelligentsia]
- Cultural Revolution in mainland China causes political and economic chaos.
- Nigerian Civil War begins.
- 6-Day War between Israelis and Arabs in 1967.
- Beginning of The Troubles in Northern Ireland
- Berlin Wall built in 1961.
- Bay of Pigs Invasion in 1961, the United States sponsored an attempt to overthrow Cuba's socialist government and Fidel Castro.
- Civil rights movement in the United States; end of official segregation and disenfranchisement of African-Americans; racial tensions continue with large race riots in Watts (Los Angeles) in 1966, Detroit in 1967, and Hough and Glenville in Cleveland.
- Sino-Indian War in late 1962. China attacks India and gains some land in Kashmir.
- Cuban Missile Crisis in 1962.
- Indo-Pakistani War of 1965 over Kashmir ends in a stalemate.
- The Vietnam War and protests, leading to Kent State University shootings in May, 1970.
- Suppression of uprising in Czechoslovakia.
- The Stonewall Riots in New York City give birth to the gay rights movement, June 1969.
- United Nations imposes sanctions against South Africa to protest the policy of Apartheid.
- Students protesting perceived problems with the status-quo are suppressed with violence by police and soldiers in USA, France, Mexico, Czechoslovakia. See New Left.
- The Quiet Revolution (Révolution tranquille) begins in Quebec - precipitous decline of the Roman Catholic church, liberalism, social-democratic programs, and the birth of modern Quebec nationalism.
- The rise of radical feminism.

Economics

- Many countries in The West experience high economic growth (4 to 8% per year)

Culture

- Rock and roll develops, diversifies, and becomes very hip. The Beatles eclipse Elvis Presley and become the most popular musical artists in the world. "Topical" artists like Bob Dylan and Joan Baez worked social commentary into their music.
- 2001: A Space Odyssey hits movie theaters
- The long running BBC family science fiction show Doctor Who begins in 1963
- Star Trek makes its debut in 1966
- James Bond movies begin. Dr. No is the first of the series in 1962, starring Sean Connery as Bond
- Hippies, drug culture & rock and roll converge at the Woodstock festival, 1969
- In the West, the growing popularity of religions other than Christianity (for example, as discussed in the writings of Alan Watts), and of atheism; Time Magazine asks: "Is God Dead?" See Fourth Great Awakening, Consciousness Revolution
- Memorable expositions, or "World's Fairs," are held in Seattle (1962), New York (1964/1965), Montreal (1967) and San Antonio (1968)
- Progressive rock emerges
- The fine arts begins to move away from exclusively consisting of painting, drawing, and sculpture and begins to incorporate elements from popular culture (Pop art) and begins to favour the ideas behind a work, rather than the work itself (Conceptual art)

Others

Conceptual art built in 1969]]
- Post-Colonialism; many new or previously colonized countries achieve independence in Africa, Asia
- U.S. president John F. Kennedy assassinated in 1963; his brother Robert F. Kennedy assassinated in 1968
- U.S. civil rights leader Martin Luther King Jr. assassinated on April 4, 1968
-