Independence Results in Computer Science,

Abstract

During the last few years research in theoretical computer science has identified several problems whose solution seems to be important for the further development of the field and on which a considerable amout of research effort has been expended. In spite of all this effort these problems remain unsolved and, no real progress seems to have been made toward their solution. Nevertheless, there remains real optimism that they will be solved and a deeply ingrained conviction that they can be solved. This note points out that many of these problems may not have a solution in formalized mathematical systems; more specifically, proof is shown that the solutions of many instances of these problems are independent of the axioms of set theory.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1976
Accession Number
ADA040710

Entities

People

  • J. E. Hopcroft
  • J. Hartmanis

Organizations

  • Department of Computer Science, Cornell University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Computations
  • Computer Science
  • Computers
  • Language
  • Machines
  • Mathematics
  • Military Research
  • Recursive Functions
  • Set Theory
  • Theorems

Readers

  • Educational Psychology
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Systems Analysis and Design