Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

8
  • 33
    $\begingroup$ Do you also think that pysicists should not use differential equations to describe the basic law of fluid dynamics? After all, a fluid is just finitely many molecules. $\endgroup$ Commented May 21, 2024 at 23:40
  • 8
    $\begingroup$ I suppose you could take some basic theorems in computability theory and see how they get destroyed if you try to apply them to finite state automata. $\endgroup$ Commented May 21, 2024 at 23:59
  • 2
    $\begingroup$ If we care about the finite capacity of real computers, and how much of that capacity is needed to execute certain algorithms, then we don't need to abandon the Turing machine model of computation. We can analyse the resource usage of an algorithm in terms of its time and space complexity. Then you don't need to change your model of computation or your methodology every time the "real computers" you care about get better. 10^10 might sound like a big number, but it's not much larger than the number of different IPv4 addresses, and we've already run out of those. $\endgroup$ Commented May 22, 2024 at 11:50
  • 3
    $\begingroup$ A FSM with 10^20 states will not be able to determine if a 200-character (binary) string is a palindrome. A TM with only a few states and, say, a bounded tape of length 500 will easily do so. Your computer will too. A FSM with 10^20 states will be able to check if your input equals the first 10^20 binary digits of pi (by hardcoding them). Said bounded TM won't. Your computer also won't. $\endgroup$ Commented May 22, 2024 at 14:46
  • 6
    $\begingroup$ When computer scientists ask "Is it computable?" they mean, without regard for how much memory or how much time or how much of any other resource the computation needs. We could argue all day about whether or not that makes any sense, but there's no point in arguing about whether or not that's what they really mean. It's just a simple fact. $\endgroup$ Commented May 22, 2024 at 21:51