SECOND-ORDER MATHEMATICAL THEORY OF COMPUTATION

Abstract

The work shows that it is possible to formalize all properties regularly observed in (deterministic and non-deterministic) algorithms in second-order predicate calculus. Moreover, it is shown that for any given algorithm it suffices to know how to formalize its 'partial correctness' by a second-order formula in order to formalize all other properties by second-order formulas. The result is of special interest since 'partial correctness' has already been formalized in second-order predicate calculus for many classes of algorithms.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1970
Accession Number
AD0708077

Entities

People

  • Zohar Manna

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Calculus
  • Computations
  • Computer Science
  • Computers
  • Theory Of Computation
  • Three Dimensional
  • Universities

Fields of Study

  • Computer science

Readers

  • Mathematical Modeling and Probability Theory.