RSS

stuhlmueller + compsci   95

Matt Might's blog
Articles on functional programming, compilation, continuations, parsing, and on general topics of interest to academics (writing, presentations, grad school).
compsci  functional-programming  academia  blog 
june 2011 by stuhlmueller
Patterns in Functional Programming
A book in process.
compsci  functional-programming  category-theory 
april 2011 by stuhlmueller
DP Zoo Tour
Illustrates the subcomputation tables built by common dynamic programming algorithms.
compsci  dynamic-programming 
february 2011 by stuhlmueller
Logic and computation (seminar)
References on the relation between programs, proofs, and (undelimited and delimited) continuations.
compsci  logic  continuations  references 
december 2010 by stuhlmueller
Programs as data (seminar)
References on program generation, partial evaluation, reflection, and other techniques that treat programs as data.
compsci  compilation  references 
december 2010 by stuhlmueller
What's new in purely functional data structures since Okasaki?
New purely functional data structures published since 1998.
compsci  functional-programming 
december 2010 by stuhlmueller
Topology via logic
Self-contained introduction to topology, approaching it as a way to study the logic of finite observations.
topology  math  compsci 
may 2010 by stuhlmueller
The Pi Calculus
The π-calculus is to concurrent programs as the λ-calculus is to sequential programs (although the choice of π is not as canonical as that of λ).
compsci  programming  language  theory 
august 2009 by stuhlmueller
Information, Physics and Computation
Draft of an introduction to the research field at the interface between statistical physics, theretical computer science/discrete mathematics, and coding/information theory.
math  physics  information  compsci  book 
july 2009 by stuhlmueller
Why Sets? (pdf)
Sets play a key role in foundations of mathematics and computer science. Why?
math  compsci  settheory 
november 2008 by stuhlmueller
Growing a Language (pdf)
Experimental talk: Defines its terms and says everything else in words of one syllable. I wish philosophical essays were written in this style.
compsci  language  programming 
october 2008 by stuhlmueller
The Tale of One-way Functions
Discusses and refines concepts relevant to the question whether one-way functions exist. (If yes, then P!=NP.)
compsci  functions  cryptography  levin 
august 2008 by stuhlmueller
Ulam's Problem: Twenty Questions with n Lies
Error-correcting codes (Hamming codes) solve the problem of searching with lies for n=1.
compsci  games  ulam  search 
june 2008 by stuhlmueller
How Big are Quantum States? (Scott Aaronson)
If you have a quantum state of n qubits, does it act more like n classical bits, or does it act more like 2^n bits?
quantum  physics  compsci 
june 2008 by stuhlmueller
History of Lambda Calculus and Combinatory Logic (pdf)
The inception and development of lambda calculus and combinatorics from their genesis in the 1920s through the entire 20th century.
history  compsci  lambda-calculus 
june 2008 by stuhlmueller
Inexact Graph Matching
Given a large (e.g. social or conceptual) network, applying graph matching to identify common structures (=subgraphs) might give us new vocabulary to talk about such networks.
graph  research  compsci  math 
may 2008 by stuhlmueller
Langton's ant
A two-dimensional Turing machine with a very simple set of rules but complicated emergent behavior.
turing  machine  algorithms  emergence  compsci 
may 2008 by stuhlmueller
Polynomial Programming Language
Proposes a language in which only all polynomial time computable functions can be programmed. A useful constraint for artificial intelligence based on program search?
compsci  programming  complexity  ai 
april 2008 by stuhlmueller
Computational Category Theory
An implementation of concepts and constructions from category theory in the functional programming language Standard ML.
math  compsci  category  theory  ebook 
april 2008 by stuhlmueller
Wang Tile
"It is possible to translate any Turing machine into a set of Wang tiles, such that the Wang tiles can tile the plane if and only if the Turing machine will never halt. [..] In a sense, Wang tiles have computational power equivalent to that of a TM."
math  compsci  wang  egan  wikipedia 
april 2008 by stuhlmueller
Sometimes all functions are continuous
For functions from N to N, all reasonable models of computation are equivalent to Turing machines. At higher types, questions of representation become important, and it does matter which model of computation is used.
math  programming  compsci 
february 2008 by stuhlmueller
Interesting higher-order functionals
"Functionals are higer-order functions, i.e., functions that take functions as arguments or return them as results. [..] Understanding every next level of functionals requires new concepts and fresh ideas. We have not come very far."
math  programming  compsci 
february 2008 by stuhlmueller
Phenotropics
Suggests to replace the current model of connecting software components (protocol adherence, chaotic failure modes) by pattern recognition (graceful error-tolerance).
compsci  programming  software  evolution 
december 2007 by stuhlmueller
Analytic Combinatorics
Tries to provide a unified treatment of analytic methods in combinatorics. Might be important to know how to create "averages" of combinatorially exploding things.
math  combinatorics  algorithms  compsci 
september 2007 by stuhlmueller
Estimated impact of publication venues in Computer Science
Impact is estimated using the average citation rate, where citations are normalized using the average citation rate for all articles in a given year.
compsci  research  conference  journal  ranking 
august 2007 by stuhlmueller
Lisp in Python
A translation of the original Lisp to Python in about 150 lines of code. Impressive.
python  lisp  programming  compsci 
july 2007 by stuhlmueller
Prolog in Python, Version 3
Prolog implemented in 250 lines of readable Python code. Now tell me you don't love Python!
python  programming  compsci  prolog 
july 2007 by stuhlmueller
Richard Feynman and The Connection Machine
An essay by Danny Hillis on Feynman's time at Thinking Machines Corporation. They built a 64,000 processor computer in the mid 1980's and then wrote software for simulating tiny cellular motion.
feynman  physics  compsci 
july 2007 by stuhlmueller
A Theory of the Learnable (PDF)
Gives a precise methodology for studying learning from a computational viewpoint. Show that there are both serious limits and important nontrivial classes of concepts that ca be learned.
compsci  learning  theory 
june 2007 by stuhlmueller
A Computational Foundation for the Study of Cognition
What is it for a physical system to implement a computation? Is computation sufficient for thought? What is the role of computation in a theory of cognition? What is the relation between different sorts of computational theory (e.g. connectionism)?
compsci  cogsci  philosophy 
june 2007 by stuhlmueller
Alligator Eggs!
A sneaky way to introduce the Lambda Calculus. Guess I need kids.
lambda-calculus  compsci  functional  programming 
may 2007 by stuhlmueller
Natural Proof
Shows how the P=NP? problem has a strange, self-referential character that’s not quite like anything previously encountered in mathematics, including in the work of Gödel and Turing.
compsci  theorem  wikipedia 
may 2007 by stuhlmueller
PTTP - Prolog Technology Theorem Prover
PTTP is an implementation of the model elimination theorem-proving procedure that extends Prolog to the full first-order predicate calculus.
prolog  theorem  proving  logic  lisp  compsci 
may 2007 by stuhlmueller
λ Prolog
Lambda Prolog is a logic programming language featuring polymorphic typing, modular programming, and higher-order programming. It can capture higher-order abstract syntax and thus map object-level bindings to programming language bindings.
compsci  prolog  logic  programming 
may 2007 by stuhlmueller
Wizard Book
An excellent computer science text used in introductory courses at MIT. One of the bibles of the LISP/Scheme world.
programming  compsci  scheme  lisp 
april 2007 by stuhlmueller
John's Combinatory Logic Playground
"This design of a minimalistic universal computer was motivated by my desire to come up with a concrete definition of Kolmogorov Complexity, which studies randomness of individual objects."
compsci  complexity  algorithms  programming 
april 2007 by stuhlmueller
The Nature of Code
Syllabus and notes from an ITP class called The Nature of Code, which focuses on "the programming strategies and techniques behind computer simulations of natural systems". Lots of good notes and Processing code examples.
programming  processing  compsci  math 
march 2007 by stuhlmueller
Design and control of self-organizing systems (PDF)
Thesis that proposes a methodology to aid engineers in the design and control of complex self-organizing systems.
complexity  design  compsci  ai 
march 2007 by stuhlmueller
6.844 Computability Theory of and with Scheme
6.844 is a graduate introduction to programming theory, logic of programming, and computability, with the programming language Scheme used to crystallize computability constructions and as an object of study itself.
scheme  programming  lisp  mit  compsci 
march 2007 by stuhlmueller
Reflexive Induktive Inferenz (PDF)
Skript bestehend aus den für die Vorlesung "Algorithmisches Lernen" (TU Darmstadt) relevanten Kapiteln der Dissertation "Selbsteinschätzende Lernverfahren: Möglichkeiten und Grenzen." von G. Grieser.
induction  solomonoff  ai  compsci  learning 
march 2007 by stuhlmueller
The Mizar Project
The Mizar project started around 1973 as an attempt to reconstruct mathematical language in a computer-oriented environment. The most important activity has been the development of a database for mathematics.
math  logic  programming  compsci  database 
march 2007 by stuhlmueller
Anticryptography: The Next Frontier in Computer Science
The basic goal in anticryptography is to create messages or programs that can be used by a recipient who has little or no prior knowledge about how they were created. By applying these techniques, we can build software that learns new procedures.
compsci  cryptography  seti 
march 2007 by stuhlmueller
Category theory - Wikipedia, the free encyclopedia
Deals in an abstract way with mathematical structures and relationships between them. A category consists of a class of objects, a class of morphisms (structure-preserving mappings between structures) and a binary operation (composition of morphisms).
math  category  theory  compsci 
march 2007 by stuhlmueller
Monads in functional programming - Wikipedia, the free encyclopedia
Monads are used in functional programming to express input/output (I/O) operations and changes in state without using language features that introduce side effects.
functional  programming  haskell  compsci 
march 2007 by stuhlmueller
Fraunhofer Quantum Computing Simulator
Web-based editor for setup, control and analysis of quantum computing simulation jobs.
quantum  computing  compsci  physics  simulation 
march 2007 by stuhlmueller
Reality, causation, and the great programmer
"The vast majority of the infinite collection of programs that are written within these worlds will be buggy, ill-behaved, or even ill advised, resulting in worlds containing no self-aware-substructures at all, or perhaps even lawyers and politicians."
compsci  infinity  quantum  physics 
march 2007 by stuhlmueller
Fixed-point theorem - Wikipedia, the free encyclopedia
A fixed-point theorem is a result saying that a function F will have at least one fixed point (a point x for which F(x) = x), under some conditions on F that can be stated in general terms. Results of this kind are amongst the most useful in mathematics.
math  theorem  compsci 
march 2007 by stuhlmueller
Shor, I’ll do it (Scott Aaronson)
Explains Shor’s algorithm (a quantum algorithm for factoring) without using a single ket sign, or for that matter any math beyond arithmetic.
quantum  algorithms  compsci 
february 2007 by stuhlmueller
The Church-Turing-Deutsch Principle
Hypothesis: "A universal computing device can simulate every physical process."
physics  compsci 
february 2007 by stuhlmueller
[quant-ph/9812037] Quantum Computation
Introduces quantum computation from a theoretical computer science background. What are the origins of the quantum computational power, what are the limits?
quantum  physics  compsci 
february 2007 by stuhlmueller
Minimum description length - Wikipedia, the free encyclopedia
A formalization of Occam's Razor in which the best hypothesis for a given set of data is the one that leads to the largest compression of the data. Computable!
compsci  information  theory  complexity 
february 2007 by stuhlmueller
Algorithmic information theory - Scholarpedia
Great introduction to algorithmic information theory. Explains Kolmogorov complexity, Solomonoff probability, Levins Kt-complexity, "Martin-Loef" randomness, ...
compsci  information  theory  complexity  reference 
february 2007 by stuhlmueller
Computational Depth (.ps)
Computational depth is a measure for the amount of “nonrandom” or “useful” information in a string. Considers the difference of various Kolmogorov complexity measures.
compsci  complexity 
february 2007 by stuhlmueller
Logical Depth and Physical Complexity (PDF)
An object’s “logical depth” is the time required by a universal Turing machine to generate it from an input that is algorithmically random. Under what conditions do systems undergo unbounded increase of depth in the limit of infinite space and time?
complexity  compsci  physics 
february 2007 by stuhlmueller
A Computer Scientist's View of Life, the Universe, and Everything (PDF)
Applies basic concepts of Kolmogorov compexity theory to the set of possible universes. Ideas on life, true randomness, generalization, and learning in a given universe.
schmidhuber  kolmogorov  complexity  compsci  physics 
february 2007 by stuhlmueller
Speed Prior (Jürgen Schmidhuber)
A new simplicity measure for near-optimal computable predictions (based on the fastest way of describing objects, not the shortest).
ai  compsci  schmidhuber  dallemolle 
february 2007 by stuhlmueller
On the existence and convergence of computable universal priors (.ps.gz)
A prior distribution summarises what is known about a variable in the absence of any observations. Solomonoffs universal prior combines Occam’s razor and the principle of multiple explanations. For which comp. classes do comp. universal priors exist?
compsci  ai  dallemolle 
february 2007 by stuhlmueller
Lecture notes on descriptional complexity and randomness (.ps.gz)
A detailed introduction to the main techniques of algorithmic information theory.
compsci  information  theory 
february 2007 by stuhlmueller
An Introduction to Kolmogorov Complexity and Its Applications
The idea behind Kolmogorov complexity: a good measure of the complexity of an object is the length of the shortest computer program which will construct that object. From this basic idea a variety of insights and powerful techniques have been developed.
kolmogorov  math  compsci 
february 2007 by stuhlmueller
Algorithmically random sequence - Wikipedia, the free encyclopedia
An infinite sequence S is random if and only if no prefix can be produced by a program much shorter than the prefix.
compsci  randomness  kolmogorov 
february 2007 by stuhlmueller
Kraft's inequality - Wikipedia, the free encyclopedia
The necessary and sufficient condition for the existence of a uniquely decodable code for a given set of codeword lengths. Relevant for binary trees, Chaitin's constant.
compsci  chaitin 
february 2007 by stuhlmueller
Goodstein's theorem - Wikipedia, the free encyclopedia
Theorem : Every Goodstein sequence eventually terminates at 0. Unprovable in Peano arithmetic. In contrast to the Collatz conjecture, Goodstein's theorem has been proven using the axioms of set theory.
math  theorem  compsci 
february 2007 by stuhlmueller
From Cbits to Qbits: Teaching computer scientists quantum mechanics
How to teach mathematically literate students, with no background in physics, just enough quantum mechanics for them to understand and develop algorithms in quantum computation and quantum information theory.
quantum  physics  compsci 
february 2007 by stuhlmueller
Collatz conjecture - Wikipedia, the free encyclopedia
Will a certain number sequence (n even: n/2; n odd: 3n+1) always end the same way, regardless of the starting number? Unsolved conjecture.
collatz  compsci  math  reference 
february 2007 by stuhlmueller
Competent Program Evolution by Moshe Looks (PDF)
How can we automatically build a problem-specific representation that is more tractable than the general space?
ai  compsci  learning  algorithms 
february 2007 by stuhlmueller
Yeah but how fast is it? - Some thoughts about adiabatic QC
If P!=NP (overwhelmingly likely) and if quantum computers can't solve NP problems in polynomal time (likely), NP-complete problems of sufficient largeness can never be solved by anything obeying the laws of physics. (Approximations are possible.)
physics  compsci  complexity  quantum  computing 
february 2007 by stuhlmueller
Algorithmic Information Theory & the Foundations of Mathematics
It begins to look like randomness is a unifying principle. We not only see it in quantum mechanics and classical physics, but even in pure mathematics, in elementary number theory.
gödel  heisenberg  randomness  quantum  physics  compsci 
february 2007 by stuhlmueller
From Heisenberg to Gödel via Chaitin (PDF)
Conjecture: Uncertainty implies algorithmic randomness not only in mathematics, but also in physics.
heisenberg  gödel  incompleteness  compsci  physics 
february 2007 by stuhlmueller
Complexity classes P and NP - Wikipedia, the free encyclopedia
If positive solutions to a yes/no problem can be verified quickly in polynomial time, can the answers also be computed quickly in polynomial time? There is no proof one way or the other yet.
compsci  complexity  theory  reference  wikipedia 
january 2007 by stuhlmueller
Cook-Levin Theorem - Wikipedia, the free encyclopedia
States that the Boolean satisfiability problem is NP-complete. The Cook-Levin theorem was the first proof of NP-completeness for any problem.
compsci  complexity  reference  wikipedia 
january 2007 by stuhlmueller
The Fastest and Shortest Algorithm for All Well-Defined Problems (Marcus Hutter)
An algorithm M is described that solves any well-defined problem p as quickly as the fastest algorithm computing a solution to p, save for a factor of 5 and low-order additive terms.
complexity  algorithms  compsci  hutter  dallemolle 
january 2007 by stuhlmueller
The Unknowable by Gregory J. Chaitin
Chaitin compares and contrasts Gödel's, Turing's and his own work in a straight-forward manner using Lisp.
chaitin  gödel  turing  math  compsci  lisp 
january 2007 by stuhlmueller
Complexity Theory: A Modern Approach / Sanjeev Arora and Boaz Barak
Draft of a textbook on computational complexity theory. Basic complexity classes, lower bounds for concrete computational models and more advanced topics.
compsci  complexity  theory  algorithms  math 
january 2007 by stuhlmueller
A Speed Limit for Evolution
An upper bound on the speed of evolution is derived. The bound concerns the amount of genetic information which is expressed in observable ways in various aspects of the phenotype. Typically it can't increase faster than a few bits per generation.
evolution  rsi  compsci  algorithms 
january 2007 by stuhlmueller
Course: Machine Learning and Optimization II
From foundations of algorithmic information theory to asymptotically optimal yet infeasible methods showing the ultimate limits of machine learning, and all the way down to practically useful tricks for recurrent nets.
ai  compsci  machinelearning  schmidhuber  studium  tu  munich 
january 2007 by stuhlmueller
Course: Machine Learning and Optimization I
"We focus on learning agents interacting with an initially unknown world. Since the world is dynamic, unlike many other machine learning courses ours will put strong emphasis on learning to deal with sequential data."
ai  compsci  machinelearning  schmidhuber  studium  tu  munich 
january 2007 by stuhlmueller
A Course in Combinatorial Optimization (PDF)
Combinatorial optimization algorithms solve problems that are believed to be hard in general, by exploring the usually-large solution space. Combinatorial optimization algorithms achieve this by reducing the effective size of the space.
math  compsci 
january 2007 by stuhlmueller
The Evolution of Cybernetics
A Journal by Simon Funk
blog  ai  math  compsci 
january 2007 by stuhlmueller
Project Euler
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve.
math  programming  compsci 
january 2007 by stuhlmueller
Computational Complexity and the Anthropic Principle
About the general problem of searching a landscape for a point with specified properties. In particular, is this problem solvable in a reasonable amount of time using the resources of the physical universe?
compsci  complexity 
december 2006 by stuhlmueller
« earlier      

Copy this bookmark:



description:


tags: