The classic PV-Semaphore, defined by Dykstra, is a synchronization construct often used as the basis for many synchronization constructs. Thinking about these constructs, rather than the PV-Semaphore, is often more natural, as they are defined in terms of results, rather than of mechanism. It is the genius of the PV-Semaphore that it abstracts away from […]
In 1931 Kurt Godel showed the theory of numbers to be undecidable by showing that a general computation can be encoded as a number theory fact. The basic idea is that information can be packaged in the exponent of primes, and extracted and manipulated by the logical quantifiers ∃ and ∀. The data structures Given […]
The Turing Machine is the universal model of computation. There are other models, but the Turing Machine seems to be the most accessible given its purpose of overt simplicity. A Turing Machine is a finite state machine that encodes the program, and a single, half-infinite tape of blanks, with a read-write head that can move […]
This is a brief add-on problem for students in Theory of Computation, first written for term “152”, also known as Spring of the 2014-15 academic year. Dr. Nim is a plastic toy manufactured in the mid-1960’s by E.S.R, also the maker of Digi-Comp, a mechanical computer. Dr. Nim is a Mariambaud game, so named because […]
The theory of computation is more and more relevant as the idea of computation becomes more and more prevalent in society. It has always been that the theory of computation embraced a wide range of computational notions. However, it has been interpreted in the popular culture as either a computer, or the neural network of […]
We didn’t do justice in class to section 6.2 of the class text, Decidablity of Logical Theories. So here’s the story. A Logical Theory contains relations, variables, logical connectives, and quantifiers. The logical connectives are always AND, OR and NOT, and the quantifiers are always EXISTS and FORALL. These elements are combined into formulas in […]
Victor will be teaching next week on the 12 and 14-th. The 16-th will be off.
Homework 1 posted to homepage. Exercises are about notation and simple set theory, and there is one proof to do.
We began the course by looking at Finite State Automata. We will discuss these for awhile, and in doing so introduce the formalism-to-live-by for this course.