4 ms·

That’s definitely not Turing complete. Not because of the crank, but the fact the exact number of memory cells is hard coded. I can run an n-cell Rule 110 simul

That’s definitely not Turing complete. Not because of the crank, but the fact the exact number of memory cells is hard coded. I can run an n-cell Rule 110 simulation on a DFA, which is obviously not Turing complete.

tshaddox 5y ago
The exact number of memory cells in your computer is also bounded.
- carnitine 5y ago
  Yes, but things we actually care and prove to be Turing complete are not. There’s no up front memory limitation in the lambda calculus or Javascript or Prolog.
  - tshaddox 5y ago
    But you can increase the “hard-coded” amount of memory in this CSS demo too.
    - carnitine 5y ago
      To a finite amount, as part of the program itself. If I write a JS program that loops infinitely, pushing a number to an array, that will consume infinite memory by the standards of the JS spec. There’s no hard, upfront bound on memory. If we can hardcode memory limitations in our programs, then every ‘uncomputable’ problem just becomes a lookup table.
      - tshaddox 5y ago
        Isn’t it somewhat arbitrary to draw lines between “the JS spec” (which might not directly specify any bounds on memory usage) and the actual specifications of any given machine running JS? I’m pretty sure JS tends to run on a 64-bit architecture, for example. In fact, I’m pretty sure it’s not even true that “the JS spec” has no such limits. I’m reading that an array can’t be longer than 2^32. And apparently string length cannot exceed 2^53 - 1.
colejohnson66 5y ago
If we're going to be pedantic, then yes, no Turing Machines exist and everything is just a Finite Automaton. It's more helpful when talking about programming languages to assume an unbounded memory. For example, the desktop I'm at right now has only 16 billion memory cells (16 GiB), but I don't think of it as a Finite Automaton. The linked StackOverflow answer does not preclude adding more memory cells. It was just capped at 900 for an arbitrary reason.
cestith 5y ago
"Bounded Turing complete" or more accurately a "linear bounded automaton" is usually considered a practical enough form of Turing equivalency. No real-world computer is actually a universal Turing machine.

tshaddox 5y ago

The exact number of memory cells in your computer is also bounded.

carnitine 5y ago
Yes, but things we actually care and prove to be Turing complete are not. There’s no up front memory limitation in the lambda calculus or Javascript or Prolog.
- tshaddox 5y ago
  But you can increase the “hard-coded” amount of memory in this CSS demo too.
  - carnitine 5y ago
    To a finite amount, as part of the program itself. If I write a JS program that loops infinitely, pushing a number to an array, that will consume infinite memory by the standards of the JS spec. There’s no hard, upfront bound on memory. If we can hardcode memory limitations in our programs, then every ‘uncomputable’ problem just becomes a lookup table.
    - tshaddox 5y ago
      Isn’t it somewhat arbitrary to draw lines between “the JS spec” (which might not directly specify any bounds on memory usage) and the actual specifications of any given machine running JS? I’m pretty sure JS tends to run on a 64-bit architecture, for example. In fact, I’m pretty sure it’s not even true that “the JS spec” has no such limits. I’m reading that an array can’t be longer than 2^32. And apparently string length cannot exceed 2^53 - 1.

colejohnson66 5y ago

If we're going to be pedantic, then yes, no Turing Machines exist and everything is just a Finite Automaton. It's more helpful when talking about programming languages to assume an unbounded memory. For example, the desktop I'm at right now has only 16 billion memory cells (16 GiB), but I don't think of it as a Finite Automaton. The linked StackOverflow answer does not preclude adding more memory cells. It was just capped at 900 for an arbitrary reason.

cestith 5y ago

"Bounded Turing complete" or more accurately a "linear bounded automaton" is usually considered a practical enough form of Turing equivalency. No real-world computer is actually a universal Turing machine.