'CSC527' Category

  • From Semaphores to Locks

    October 14, 2015

    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 [...]

  • Godel Encoding

    April 4, 2015

    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 [...]

  • Programming and Turing Machines

    March 17, 2015

    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 [...]

  • Dr. Nim as a Regular Language

    January 23, 2015

    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 [...]

  • A short history of the Theory of Computation

    January 12, 2015

    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 [...]

  • Godel’s Theorem

    March 28, 2007

    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 [...]

  • Problem 3 posted

    February 5, 2007

    Victor will be teaching next week on the 12 and 14-th. The 16-th will be off.

  • Homework 1

    January 22, 2007

    Homework 1 posted to homepage. Exercises are about notation and simple set theory, and there is one proof to do.

  • Introduction

    January 19, 2007

    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.

  • Welcome to Theory of Computation

    January 17, 2007

    This course meets MWF 3:35- 4:25 in Memorial 300.

Powered by Wordpress and MySQL. Theme by Shlomi Noach, openark.org