Non-Computability and Intractability: Does It Matter to Physics?

Joseph F. Traub

Working Papers from Santa Fe Institute

Abstract: Over the last sixty years there has been a stream of impossibility results from mathematics and theoretical computer science announcing undecidability, non-computability, and intractability. Should these impossibility results be of concern to physics?

Two of these impossibility results are discussed:

Should non-computability be of concern to physicists?

Should intractability be of concern to physicists?

The answers to these questions are influenced by which abstract model of computation is used. Physicists who have thought about this seem to favor the Turing machine model, but the real-number model might be more appropriate.

Should physicists consider alternatives to the Turing machine model of computation?

Keywords: Undecidability; non-computability; intractability; Turing machine model; real-number model (search for similar items in EconPapers)
Date: 1998-02
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:98-02-019

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().