Skip to main content
40 votes
Accepted

Can one build a "mechanical" universal Turing machine?

Sure. Electricity is unrelated to the model of computation. The only thing you can't actually build is the infinite tape, for obvious reasons. In this sense, anything that can be built is essentially ...
Shaull's user avatar
  • 17.2k
24 votes

Can one build a "mechanical" universal Turing machine?

Sure. Not only is it possible, the first design for a Turing-complete computer was purely mechanical. This was Charles Babbage's Analytical Engine. Babbage published its design in 1837, long before ...
Gilles 'SO- stop being evil''s user avatar
14 votes

What is the difference between luma and luminance?

There are actually three related terms: Luminance is a physical measure which represents the luminous intensity per unit area of light travelling in some direction. The units are candela per square ...
Pseudonym's user avatar
  • 22.1k
6 votes

Did Wheeler really believe that physics was undecidable?

The inference "the universe would be completely computable, so no undecidable/uncomputable things could exist" is invalid. In the effective topos, where everything is computable, there are many ...
Andrej Bauer's user avatar
  • 30.4k
5 votes
Accepted

Is computer science really a branch or sub-branch of physics?

No it is not. Computer science has as much to do with computers as astronomy does with telescopes: they're a tool. Even if computers didn't exist the science of computing things still would. IMO ...
orlp's user avatar
  • 13.4k
4 votes
Accepted

Learning dynamics

There are three issues. First, you must choose a class of models for the dynamics. Second, you must construct a training set, by taking the agent down different trajectories to explore the state ...
D.W.'s user avatar
  • 159k
3 votes

The class of problems that can be solved efficiently using physical means?

It's not clear what "can be solved" actually means here. Let me explain with a real example. It is known that NP-hard problems can be solved on an analog computer in polynomial time. Suppose ...
Pseudonym's user avatar
  • 22.1k
3 votes

Can one build a "mechanical" universal Turing machine?

See: YouTube Matt Parker has made some small scale logic gates out of dominoes. Highly impractical, but theoretically, with enough time and space, one could build a functional computer that way. ...
MikeB's user avatar
  • 131
3 votes
Accepted

Can all non-quantum physical systems be efficiently simulated on a classical computer?

Roughly speaking, I expect the answer will be yes, this can be done efficiently, but the longer answer is that I believe it takes some care to define what you mean by simulating. First, we must define ...
D.W.'s user avatar
  • 159k
3 votes

Generalization of computability to continuous for loops?

First of all, despite claims by several people here, there are models of computation which support computation on topological spaces. The "countable vs. uncountable" distinction is a red ...
Andrej Bauer's user avatar
  • 30.4k
3 votes
Accepted

Reference Request: Overlaps between complexity theory and dynamical systems?

This is a well-researched area. For a representative result, see Kawamura's proof that solving ODEs is difficult. A different line of works studies the hardness of computing Nash equilibria and ...
Yuval Filmus's user avatar
3 votes
Accepted

The Ising Model and Computational Complexity

Finding the minimal energy configuration in the Ising model is NP-hard, and many problems can be directly reduced to it. For a list, including Karp's original 21 NP-hard problem see e.g. Ising ...
Marcus Ritt's user avatar
3 votes

Are physical laws uncomputable in any type of computation (according to this article)?

The reasoning given in the paper is too vague to be of much value. The question whether laws of physics are computable cannot be decided by a philosophical discussion. It already takes some hard ...
Andrej Bauer's user avatar
  • 30.4k
2 votes

Potential General Model of Computation with Physics?

It would be meaningful, if you properly defined "formal physical system", "set in motion", and so on, in a mathematical way. Pretty much anything can be made meaningful in mathematics (which is what ...
Draconis's user avatar
  • 7,138
2 votes

The class of problems that can be solved efficiently using physical means?

No one knows. The extended Church-Turing hypothesis is sometimes described as saying that the answer is Phys-P = BPP. This is a conjecture or hypothesis but it is not proven. The answer depends on ...
D.W.'s user avatar
  • 159k
2 votes
Accepted

Would models of computation in other conceivable universes be Turing complete?

The study of models of computation extremely broadly construed is called "generalized recursion theory" (or "higher recursion theory," or "generalized/higher computability theory," or etc.). We can ...
Noah Schweber's user avatar
2 votes

Best C++ STL container to store bodies in an N-body simulation?

If you want to find collision pairs for $10^6$ objects, I would suggest using a spatial data structure (as suggested by @D.W. in the comments). For collision detection, some useful structures are ...
TilmannZ's user avatar
  • 764
2 votes

Best C++ STL container to store bodies in an N-body simulation?

With $N=10^6$ bodies, the obvious method to track their movements by having a system of simultaneous differential equations taking $\mathcal{O}(N^2)$ operations per step with a rather large constant ...
gnasher729's user avatar
  • 30.1k
2 votes

Best C++ STL container to store bodies in an N-body simulation?

Why choose? You can have it both ways: a vector that contains all the bodies, and, a map from ID to index in that vector Any simple modification of the vector (push_back, swap, pop_back) would also ...
harold's user avatar
  • 2,053
1 vote
Accepted

Evenly Spaced Points On Smooth Surface

I would suggest that you don't calculate the distance between all pairs of points, but only between pairs of points that are nearest neighbors. You could store the points in some nearest-neighbor ...
D.W.'s user avatar
  • 159k
1 vote
Accepted

How does one simulate continuous gravity using a discrete timestep?

This is an example of Euler's Method Using differentiation, you can find a better formula. Since discrete calculations only "drift" if they are non-linear, you only need to alter the position/time ...
nathanfranke's user avatar
1 vote

Undecidable problems limit physical theories

Babou, It's indeed a very interesting question but as said above a lot of literature has been produced on the subject. The least you can say once you have read all that is that mapping UTM to ...
Jerome's user avatar
  • 109

Only top scored, non community-wiki answers of a minimum length are eligible