EDIT (much later than original answer): MarkCC of Good Math, Bad Math recently wrote up an excellent discussion of the Halting problem with concrete examples. The halting problem is basically a formal way of asking if you can tell whether or not an arbitrary program will eventually halt. In other words, can you write a … Read more
A finite state transducer (FST) is a finite state automaton (FSA, FA) which produces output as well as reading input, which means it is useful for parsing (while a “bare” FSA can only be used for recognizing, i.e. pattern matching). An FST consists of a finite number of states which are linked by transitions labeled … Read more
Watch this lecture. The idea is that your program is a combination of a datatype and operations over it. The problem asks for an implementation that allows to add new cases of the type and new operations without the need for recompilation of the old modules and keeping static type safety(no casts or runtime type … Read more
Theres a few ways you can do this. You can either add a background to the canvas you are currently working on, which if the canvas isn’t going to be redrawn every loop is fine. Otherwise you can make a second canvas underneath your main canvas and draw the background to it. The final way … Read more
I’ve only scanned through the paper, but here’s a rough summary of how it all hangs together. From page 86 of the paper. … polynomial time algorithms succeed by successively “breaking up” the problem into smaller subproblems that are joined to each other through conditional independence. Consequently, polynomial time algorithms cannot solve problems in regimes … Read more
Turing machines are theoretical concepts invented to explore the domain of computable problems mathematically and to obtain ways of describing these computations. The Von-Neumann architecture is an architecture for constructing actual computers (which implement what the Turing machine describes theoretically). Functional programming is based on the lambda-calculus, which is a another method of describing computations … Read more
Very good and important question! A good understanding of math is essential for every computer scientist, and the math requirement is starting to become more diverse. Discrete Math is the most important and basic class for computer science, and for this reason it is usually offered in CS departments instead of math departments. This class … Read more
Entropy can mean different things: Computing In computing, entropy is the randomness collected by an operating system or application for use in cryptography or other uses that require random data. This randomness is often collected from hardware sources, either pre-existing ones such as mouse movements or specially provided randomness generators. Information theory In information theory, … Read more
The benefit of lambda calculus is that it’s an extremely simple model of computation that is equivalent to a Turing machine. But while a Turing machine is more like assembly language, lambda calculus is more a like a high-level language. And if you learn Church encodings that will help you learn the programming technique called … Read more
A lambda (or closure) encapsulates both the function pointer and variables. This is why, in C#, you can do: int lessThan = 100; Func<int, bool> lessThanTest = delegate(int i) { return i < lessThan; }; I used an anonymous delegate there as a closure (it’s syntax is a little clearer and closer to C than … Read more