For Nothing, Against Everything
the known universe starts to collapse, life disintegrates
The Beast's Beauty
witchkrieg
bastardnoise
about me
philosophy
math
Turing machines
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.
The “Turing” machine was described by Alan Turing in 1936, who called it an “a(utomatic)-machine”. The Turing machine is not intended as a practical computing technology, but rather as a thought experiment representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation.
Turing gave a succinct definition of the experiment in his 1948 essay, “Intelligent Machinery”. Referring to his 1936 publication, Turing wrote that the Turing machine, here called a Logical Computing Machine, consisted of:
…an infinite memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.(Turing 1948, p. 61)
A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine (UTM, or simply a universal machine). A more mathematically-oriented definition with a similar “universal” nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing’s in a formal theory of computation known as the Church–Turing thesis. The thesis states that Turing machines indeed capture the informal notion of effective method in logic and mathematics, and provide a precise definition of an algorithm or ‘mechanical procedure’.
Studying their abstract properties yields many insights into computer science and complexity theory.
(Source: Wikipedia)
can you dig it?
In mathematics, Zermelo–Fraenkel set theory with the axiom of choice, named after mathematicians Ernst Zermelo and Abraham Fraenkel and commonly abbreviated ZFC, is one of several axiomatic systems that were proposed in the early twentieth century to formulate a theory of sets without the paradoxes of naive set theory such as Russell’s paradox. Specifically, ZFC does not allow unrestricted comprehension. Today ZFC is the standard form of axiomatic set theory and as such is the most common foundation of mathematics.
ZFC has a single primitive ontological notion, that of a hereditary well-founded set, and a single ontological assumption, namely that all individuals in the universe of discourse are such sets. Thus, ZFC is a set theory without urelements (elements of sets which are not themselves sets). ZFC does not formalize the notion of classes (collections of mathematical objects defined by a property shared by their members) and specifically does not include proper classes (objects that have members but cannot be members themselves).
ZFC is a one-sorted theory in first-order logic. The signature has equality and a single primitive binary relation, set membership, which is usually denoted ∈. The formula a ∈ b means that the set a is a member of the set b (which is also read, “a is an element of b” or “a is in b”).
There are many equivalent formulations of the ZFC axioms. Most of the ZFC axioms state the existence of particular sets. For example, the axiom of pairing says that given any two sets a and b there is a new set {a, b} containing exactly a and b. Other axioms describe properties of set membership. A goal of the ZFC axioms is that each axiom should be true if interpreted as a statement about the collection of all sets in the von Neumann universe (also known as the cumulative hierarchy).
The metamathematics of ZFC has been extensively studied. Landmark results in this area established the independence of the continuum hypothesis from ZFC, and of the axiom of choice from the remaining ZFC axioms.
Cantor’s diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers. Such sets are now known as uncountable sets, and the size of infinite sets is now treated by the theory of cardinal numbers which Cantor began.
The diagonal argument was not Cantor’s first proof of the uncountability of the real numbers; it was actually published much later than his first proof, which appeared in 1874. However, it demonstrates a powerful and general technique that has since been used in a wide range of proofs, also known as diagonal arguments by analogy with the argument used in this proof. The most famous examples are perhaps Russell’s paradox, the first of Gödel’s incompleteness theorems, and Turing’s answer to the Entscheidungsproblem.
Philosophical implications of the Church-Turing thesis
The Church–Turing thesis has some profound implications for the philosophy of mind; however many of the philosophical interpretations of the Thesis involve basic misunderstandings of the thesis statement. B. Jack Copeland states that it’s an open empirical question whether there are actual deterministic physical processes that, in the long run, elude simulation by a Turing machine; furthermore, he states that it is an open empirical question whether any such processes are involved in the working of the human brain. There are also some important open questions which cover the relationship between the Church–Turing thesis and physics, and the possibility of hypercomputation. When applied to physics, the thesis has several possible meanings:
- The universe is equivalent to a Turing machine; thus, computing non-recursive functions is physically impossible. This has been termed the Strong Church–Turing thesis and is a foundation of digital physics.
- The universe is not equivalent to a Turing machine (i.e., the laws of physics are not Turing-computable), but incomputable physical events are not “harnessable” for the construction of a hypercomputer. For example, a universe in which physics involves real numbers, as opposed to computable reals, might fall into this category.
- The universe is a hypercomputer, and it is possible to build physical devices to harness this property and calculate non-recursive functions. For example, it is an open question whether all quantum mechanical events are Turing-computable, although it is known that rigorous models such as quantum Turing machines are equivalent to deterministic Turing machines. (They are not necessarily efficiently equivalent; see above.) John Lucas and, more famously, Roger Penrose have suggested that the human mind might be the result of some kind of quantum-mechanically enhanced, “non-algorithmic” computation, although there is no scientific evidence for this proposal.
There are many other technical possibilities which fall outside or between these three categories, but these serve to illustrate the range of the concept.
(Source: Wikipedia)
The shape of the universe is a matter of debate in physical cosmology over the local and global geometry of the universe which considers both curvature and topology, though, strictly speaking, it goes beyond both. In practice, more formally, the debate seeks a 3-manifold that corresponds to the spatial section (in comoving coordinates) of the 4-dimensional space-time of the universe.
The Wilkinson Microwave Anisotropy Probe (WMAP) has confirmed that the universe is flat with only a 0.5% margin of error. Within the Friedmann-Lemaître-Robertson-Walker (FLRW) model, the presently most popular shape of the Universe found to fit observational data according to cosmologists is the infinite flat model, while other FLRW models that fit the data include the Poincaré dodecahedral space and the Picard horn.
Alan Mathison Turing, OBE, FRS (23 June 1912 – 7 June 1954), was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of “algorithm” and “computation” with the Turing machine, which played a significant role in the creation of the modern computer. Turing is widely considered to be the father of computer science and artificial intelligence.
During the Second World War, Turing worked for the Government Code and Cypher School at Bletchley Park, Britain’s codebreaking centre. For a time he was head of Hut 8, the section responsible for German naval cryptanalysis. He devised a number of techniques for breaking German ciphers, including the method of the bombe, an electromechanical machine that could find settings for the Enigma machine. After the war he worked at the National Physical Laboratory, where he created one of the first designs for a stored-program computer, the ACE.
Towards the end of his life Turing became interested in mathematical biology. He wrote a paper on the chemical basis of morphogenesis, and he predicted oscillating chemical reactions such as the Belousov–Zhabotinsky reaction, which were first observed in the 1960s.
Turing’s homosexuality resulted in a criminal prosecution in 1952, when homosexual acts were still illegal in the United Kingdom. He accepted treatment with female hormones (chemical castration) as an alternative to prison. He died in 1954, just over two weeks before his 42nd birthday, from cyanide poisoning. An inquest determined it was suicide; his mother and some others believed his death was accidental. On 10 September 2009, following an Internet campaign, British Prime Minister Gordon Brown made an official public apology on behalf of the British government for the way in which Turing was treated after the war.
On Russell’s Paradox
In the late 19th and early 20th centuries, many schools of mathematics ran into difficulties with getting results without contradictions, and so there was a sudden need for a rigorous foundation of mathematics. Cantor’s Naïve Set Theory was an early attempt to provide a rigorous foundation through an axiomatic system and thus provide a solid basis for deriving solid results. However, one of his axioms, the axiom of seperation (also known as collection), leads to s contradiction known as Russell’s Paradox, which was discovered by Bertrand Russell in 1901.
In Cantor’s Naïve Set Theory, the axiom of seperation was just
∀z(z ∈{y : A(y)} ↔ A(z))
Now, let x ≡ {y : y ∉ y} such that A(y) ≡ (y ∉ y)
Then, z ∈ x ↔ z ∈{y : y ∉ y}
z ∈ x ↔ z ∉ z
Now, let x = z
Then, x ∈ x ↔ x ∉ x
x ∈ x ↔ ┐(x ∈ x) which is absurd
and so we have derived Russell’s Pardox.
ZF Set theory has a solution to this paradox while maintaining the extremely useful axiom of seperation. This is the most commonly used rigorous foundation of mathematics.
∀x∀z (z ∈{y : y ∈ x ^ A(y)} ↔ (z ∈ x ^ A(z)))
One issue with this solution is that it precludes the existence of the Universal Set (the set that contains all objects including itself).
Another solution to the paradox is the Vicious Circle Principle, which Russell himself endorsed as a solution to the paradox.The principle states that no object or property may be introduced by a definition that depends on that object or property itself. In addition to ruling out definitions that are explicitly circular (like “an object has property P if and only if it is not next to anything that has property P”), this principle rules out definitions that quantify over domains which include the entity being defined.
It is also important to note that Russell’s Paradox is not inherently a set theory result, but a theory of first order logic.
├ ┐∃x ∀y (Rxy ↔ ┐Ryy)
this fact can easily be shown in the following proof tree:
-
┐┐∃x ∀y (Rxy ↔ ┐Ryy)
-
∃x ∀y (Rxy ↔ ┐Ryy) (1, ┐┐ rule)
-
∀y (Ray ↔ ┐Ryy) (2, ∃rule)
-
Raa ↔ ┐Raa (3,∀rule)
-
Raa, ┐Raa ^ ┐Raa, Raa (4. ↔ rule) Note two branches, both closed.
So, such a property cannot exist in any mathematical system. This is similar to the barber paradox (the barber who shaves every person who doesn’t shave themselves) in that the solution is “such a thing doesn’t exist”.
In fact, there is a countable infinity of Russell’s Classes of non-existent objects
R2: ├ ┐∃x ∀y ∀z (Rxy ↔ (Rzy ↔ ┐Ryz))
2 line proofs are usually missing something at this level.
