MAC Technical Reports (1963 - 1974): Recent submissions

Now showing items 40-42 of 119

    • Relativization of the Theory of Computational Complexity 

      Lynch, Nancy A. (1972-06)
      Blum's machine-independent treatment of the complexity of partial recursive functions is extended to relative algorithms (as represented by Turing machines with oracles). We prove relativizations of several results of ...

    • The Complexity of Finite Functions 

      Vilfan, Bostjan (1972-03)
      Lower bounds on the length of formulas for finite functions are obtained from a generalization of a theorem of Specker. Let f: (0,1,...,d-1) [0,1,...,d-1] be a function which can be represented by a formula of length ...

    • Autonomous, Synchronous Counters Constructed Only of J-K Flip-flops 

      Manning, Frank (1972-05)
      This report describes research into some properties of autonomous, synchronous counters constructed with only the simplest form of J-K Flip-Flop. The research revolved around a system with a special-purpose digital machine ...