View in EDS PDF Full Text

On the Computational Power of Particle Methods.

Saved in:
Bibliographic Details
Title: On the Computational Power of Particle Methods.
Authors: Pahlke, Johannes1,2,3, Sbalzarini, Ivo F.1,2,3,4 sbalzarini@mpi-cbg.de
Source: Fundamenta Informaticae. 2025, Vol. 194 Issue 1, p1-40. 40p.
Subjects: Particle methods (Numerical analysis), Machine theory, Computer simulation, Computer performance, Formal languages, Scientific computing
Abstract: We investigate the computational power of particle methods, a well-established class of algorithms with applications in scientific computing and computer simulation. The computational power of a compute model determines the class of problems it can solve. Automata theory allows describing the computational power of abstract machines (automata) and the problems they can solve. At the top of the Chomsky hierarchy of formal languages and grammars are Turing machines, which resemble the concept on which most modern computers are built. Although particle methods can be interpreted as automata based on their formal definition, their computational power has so far not been studied. We address this by analyzing Turing completeness of particle methods. In particular, we prove two sets of restrictions under which a particle method is still Turing powerful, and we show when it loses Turing powerfulness. This contributes to understanding the theoretical foundations of particle methods and provides insight into the powerfulness of computer simulations. [ABSTRACT FROM AUTHOR]
Copyright of Fundamenta Informaticae is the property of Polskie Towarzystwo Matematyczne and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 188919464
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: On the Computational Power of Particle Methods.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Pahlke%2C+Johannes%22">Pahlke, Johannes</searchLink><relatesTo>1,2,3</relatesTo><br /><searchLink fieldCode="AR" term="%22Sbalzarini%2C+Ivo+F%2E%22">Sbalzarini, Ivo F.</searchLink><relatesTo>1,2,3,4</relatesTo><i> sbalzarini@mpi-cbg.de</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Fundamenta+Informaticae%22">Fundamenta Informaticae</searchLink>. 2025, Vol. 194 Issue 1, p1-40. 40p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Particle+methods+%28Numerical+analysis%29%22">Particle methods (Numerical analysis)</searchLink><br /><searchLink fieldCode="DE" term="%22Machine+theory%22">Machine theory</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+simulation%22">Computer simulation</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+performance%22">Computer performance</searchLink><br /><searchLink fieldCode="DE" term="%22Formal+languages%22">Formal languages</searchLink><br /><searchLink fieldCode="DE" term="%22Scientific+computing%22">Scientific computing</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We investigate the computational power of particle methods, a well-established class of algorithms with applications in scientific computing and computer simulation. The computational power of a compute model determines the class of problems it can solve. Automata theory allows describing the computational power of abstract machines (automata) and the problems they can solve. At the top of the Chomsky hierarchy of formal languages and grammars are Turing machines, which resemble the concept on which most modern computers are built. Although particle methods can be interpreted as automata based on their formal definition, their computational power has so far not been studied. We address this by analyzing Turing completeness of particle methods. In particular, we prove two sets of restrictions under which a particle method is still Turing powerful, and we show when it loses Turing powerfulness. This contributes to understanding the theoretical foundations of particle methods and provides insight into the powerfulness of computer simulations. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Fundamenta Informaticae is the property of Polskie Towarzystwo Matematyczne and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=188919464
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.46298/fi.11227
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 40
        StartPage: 1
    Subjects:
      – SubjectFull: Particle methods (Numerical analysis)
        Type: general
      – SubjectFull: Machine theory
        Type: general
      – SubjectFull: Computer simulation
        Type: general
      – SubjectFull: Computer performance
        Type: general
      – SubjectFull: Formal languages
        Type: general
      – SubjectFull: Scientific computing
        Type: general
    Titles:
      – TitleFull: On the Computational Power of Particle Methods.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Pahlke, Johannes
      – PersonEntity:
          Name:
            NameFull: Sbalzarini, Ivo F.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 07
              Text: 2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 01692968
          Numbering:
            – Type: volume
              Value: 194
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: Fundamenta Informaticae
              Type: main
ResultId 1