##
10 posts tagged with math *and* complexity.

Displaying 1 through 10 of 10. Subscribe:

## So, the unknowable kicks in

Logic hacking - "Writing shorter and shorter computer programs for which it's unknowable whether these programs run forever, or stop... the winner of the Busy Beaver Game for N-state Turing machines becomes unknowable using ordinary math - somewhere between N = 5 and N = 1919." [more inside]

## 21st Century Wiener

Norbert Wiener: The Eccentric Genius Whose Time May Have Finally Come (Again) - "The most direct reason for Wiener's fall to relative obscurity was the breakthrough of a young mathematician and engineer named Claude Shannon." [more inside]

## A SAT Attack on the Erdos Discrepancy Conjecture

Computers are providing solutions to math problems that we can't check - "A computer has solved the longstanding Erdős discrepancy problem! Trouble is, we have no idea what it's talking about — because the solution, which is as long as all of Wikipedia's pages combined, is far too voluminous for us puny humans to confirm." (via; previously ;)

## A connection between the Mandelbrot set and the way nature operates...

Arthur C. Clarke, Benoit Mandelbrot, Stephen Hawking, David Gilmour and many more trip the fuck out about Fractals, the Colors of Infinity.

## John Baez on the maths of connecting everyone (and everything) on earth

Network Theory Overview - "The idea: nature and the world of human technology are full of networks! People like to draw diagrams of networks. Mathematical physicists know that in principle these diagrams can be understood using category theory. But why should physicists have all the fun? This is the century of

*understanding living systems and adapting to life on a finite planet*. Math isn't the main thing we need, but it's got to be part of the solution... so one thing we should do is develop a unified and powerful theory of networks." (via ;)## Why Philosophers Should Care About Computational Complexity

"One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory---the field that studies the resources (such as time, space, and randomness) needed to solve computational problems---leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume's problem of induction, Goodman's grue riddle, the foundations of quantum mechanics, economic rationality, closed timelike curves, and several other topics of philosophical interest. I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis."

## Computerized Math, Formal Proofs and Alternative Logic

Using computer systems for doing mathematical proofs - "With the proliferation of computer-assisted proofs that are all but impossible to check by hand, Hales thinks computers must become the judge." [more inside]

## direct realism

The Nature of Computation - Intellects Vast and Warm and Sympathetic: "I hand you a network or graph, and ask whether there is a path through the network that crosses each edge exactly once, returning to its starting point. (That is, I ask whether there is a 'Eulerian' cycle.) Then I hand you another network, and ask whether there is a path which visits each node exactly once. (That is, I ask whether there is a 'Hamiltonian' cycle.) How hard is it to answer me?" (via) [more inside]

## from complexity, universality

## The Complexity of a Controversial Concept

The Logic of Diversity "A new book,

*The Wisdom of Crowds*[..:] by The New Yorker columnist James Surowiecki, has recently popularized the idea that groups can, in some ways, be smarter than their members, which is superficially similar to Page's results. While Surowiecki gives many examples of what one might call collective cognition, where groups out-perform isolated individuals, he really has only one explanation for this phenomenon, based on one of his examples: jelly beans [...] averaging together many independent, unbiased guesses gives a result that is probably closer to the truth than any one guess. While true — it's the central limit theorem of statistics — it's far from being the only way in which diversity can be beneficial in problem solving." (Three-Toed Sloth)Page:
1