Luther's Meanderings

theory

Non-understandable belief (2 Aug 2017): Recent advances in automated theorem proving support my first postulate.

Bijecting ℕ and ℝ? (5 Jan 2014): Response to a comment on my post on Cantor diagonalization.

Computers are Poor Students (5 Mar 2013): Why I am bored by “Machine Learning” (and statistics).

Verification Difficulty in Collaboration (15 November 2012): Sometimes it is hard to share research because the results are not readily verified.

Rice's Theorem (31 May 2012): Any interesting, general program analysis is undecidable.

Two-Input Halting Problem (30 May 2012): The quintessential undecidable problem.

Quining (29 May 2012): A step toward undecidability.

The Math Analogy (29 Mar 2012): Nature doesn’t even know about mathematics.

Sorting Asymptotics (8 Feb 2012): Worst- and best-case runtime for sorting, and why anyone cares.

Polynomial or Not? (31 Jan 2012): Defining “tractable” or “efficient.”

Asymptotics (10 Jan 2012): How do you define “efficient”?

Non-Regular Languages (21 Dec 2011): Some languages aren’t regular.

NFA = Regular Expressions, part 2 (14 Dec 2011): The language of every DFA is described by a regular expression.

NFA = Regular Expressions, part 1 (13 Dec 2011): An equivalence between a class of languages and a class of machines.

Nondeterministic Automata (8 Dec 2011): Of NFAs and the unimportance of regular nondeterminism

Nondeterminism (28 Nov 2011): Doing everything all at once, or magically making the right choices.

Regular Expressions (9 Nov 2011): A notation for describing the languages of Finite Automata.

State Machines (2 Nov 2011): The simplest of information machines.

Irrationality (25 Oct 2011): Some numbers are not fractions.

Cantor Diagonalization (24 Oct 2011): An infinity bigger than infinity

Decision Problems (20 Oct 2011): Yes/no questions are “enough”.

The Church-Turing Thesis (12 Oct 2011): If it can be done, it can be done by a computer.

Theory: Know the Possible (3 October 2011): In introduction to the notion of formal reasoning and theory.