View in EDS PDF Full Text

Proving Program Termination.

Saved in:
Bibliographic Details
Title: Proving Program Termination.
Authors: COOK, BYRON1,2, PODELSKI, ANDREAS3, RYBALCHENKO, ANDREY4
Source: Communications of the ACM. May2011, Vol. 54 Issue 5, p88-98. 11p. 1 Illustration, 11 Diagrams.
Subjects: Computer software termination, Decidability (Mathematical logic), Ramsey theory, Computable functions, Computer logic, Mathematical logic
Abstract: The article discusses methods for testing whether a computer program will terminate or not. This involves methods of coping with a mathematical problem that was proved to be formally undecidable by the pioneering computer scientist Alan Turing. It is known as the halting problem, or program termination problem. Although a yes or no answer cannot always be supplied, the article presents a method, based on Ramsey theory, which provides yes or no answers often enough to be useful. The method can be scaled up to large programs by constructing modular termination arguments.
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 60863980
AccessLevel: 6
PubType: Periodical
PubTypeId: serialPeriodical
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Proving Program Termination.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22COOK%2C+BYRON%22">COOK, BYRON</searchLink><relatesTo>1,2</relatesTo><br /><searchLink fieldCode="AR" term="%22PODELSKI%2C+ANDREAS%22">PODELSKI, ANDREAS</searchLink><relatesTo>3</relatesTo><br /><searchLink fieldCode="AR" term="%22RYBALCHENKO%2C+ANDREY%22">RYBALCHENKO, ANDREY</searchLink><relatesTo>4</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Communications+of+the+ACM%22">Communications of the ACM</searchLink>. May2011, Vol. 54 Issue 5, p88-98. 11p. 1 Illustration, 11 Diagrams.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Computer+software+termination%22">Computer software termination</searchLink><br /><searchLink fieldCode="DE" term="%22Decidability+%28Mathematical+logic%29%22">Decidability (Mathematical logic)</searchLink><br /><searchLink fieldCode="DE" term="%22Ramsey+theory%22">Ramsey theory</searchLink><br /><searchLink fieldCode="DE" term="%22Computable+functions%22">Computable functions</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+logic%22">Computer logic</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+logic%22">Mathematical logic</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: The article discusses methods for testing whether a computer program will terminate or not. This involves methods of coping with a mathematical problem that was proved to be formally undecidable by the pioneering computer scientist Alan Turing. It is known as the halting problem, or program termination problem. Although a yes or no answer cannot always be supplied, the article presents a method, based on Ramsey theory, which provides yes or no answers often enough to be useful. The method can be scaled up to large programs by constructing modular termination arguments.
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=60863980
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1145/1941487.1941509
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 11
        StartPage: 88
    Subjects:
      – SubjectFull: Computer software termination
        Type: general
      – SubjectFull: Decidability (Mathematical logic)
        Type: general
      – SubjectFull: Ramsey theory
        Type: general
      – SubjectFull: Computable functions
        Type: general
      – SubjectFull: Computer logic
        Type: general
      – SubjectFull: Mathematical logic
        Type: general
    Titles:
      – TitleFull: Proving Program Termination.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: COOK, BYRON
      – PersonEntity:
          Name:
            NameFull: PODELSKI, ANDREAS
      – PersonEntity:
          Name:
            NameFull: RYBALCHENKO, ANDREY
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 05
              Text: May2011
              Type: published
              Y: 2011
          Identifiers:
            – Type: issn-print
              Value: 00010782
          Numbering:
            – Type: volume
              Value: 54
            – Type: issue
              Value: 5
          Titles:
            – TitleFull: Communications of the ACM
              Type: main
ResultId 1