4 ms·

.exe's (for the usual architectures) run on finite-state machines, not Turing machines. So, indeed, that is possible. If the .exe connects to a service that ru

.exe's (for the usual architectures) run on finite-state machines, not Turing machines. So, indeed, that is possible. If the .exe connects to a service that runs on something more powerful than finite-state machine, though, I don't know.

kaba0 3y ago
That’s still a stupid pedantry, and is even false. A Turing machine only makes use of at most n cells of its tape after n steps - so running it for a finite number of steps is possible even in finite memory. Especially that modern computers can do arbitrary side effects, having access to the whole universe as tape, which is still finite, but so is time. There is no way to differentiate between a magical Turing machine with infinite tape and a “fake” one that has n-sized memory under any program that takes n steps, so for all practical purposes they are identical.
- chromoblob 3y ago
  Why are they identical? A program may use more steps than memory.
  - kaba0 3y ago
    A Turing machine can either go left or right on its tape (some versions have a stay step as well, doesn’t matter). If all your program does is step right forever, than it will use the maximum amount of memory, but only ever a finite amount, that is equal to the number of steps taken. So if you don’t have infinite time (you don’t have), and you have big enough memory for the particular use case so that you don’t get OOMKiller involved, then you have a Turing machine for all complexity theoretical and practical purposes, especially that RAM is not analogous to the Turing machine tape - your computer has much more state than only its memory, if it has network access, you can basically make use of a cloud vendors whole army of servers as storage, just as an example.
    - deleted 3y ago
      [deleted]
    - chromoblob 3y ago
      The reason for undecidability of halting is that a program's state may grow without bound. If a program's memory usage is bounded, its halting can be determined. So the computer is not like a Turing machine since its programs don't use Turing machine's key feature - infinite tape. Although the naive way of deciding halting requires exponential time in program's memory bound, AGIs will speed that up for many programs by using clever math.

kaba0 3y ago

That’s still a stupid pedantry, and is even false. A Turing machine only makes use of at most n cells of its tape after n steps - so running it for a finite number of steps is possible even in finite memory. Especially that modern computers can do arbitrary side effects, having access to the whole universe as tape, which is still finite, but so is time. There is no way to differentiate between a magical Turing machine with infinite tape and a “fake” one that has n-sized memory under any program that takes n steps, so for all practical purposes they are identical.

chromoblob 3y ago
Why are they identical? A program may use more steps than memory.
- kaba0 3y ago
  A Turing machine can either go left or right on its tape (some versions have a stay step as well, doesn’t matter). If all your program does is step right forever, than it will use the maximum amount of memory, but only ever a finite amount, that is equal to the number of steps taken. So if you don’t have infinite time (you don’t have), and you have big enough memory for the particular use case so that you don’t get OOMKiller involved, then you have a Turing machine for all complexity theoretical and practical purposes, especially that RAM is not analogous to the Turing machine tape - your computer has much more state than only its memory, if it has network access, you can basically make use of a cloud vendors whole army of servers as storage, just as an example.
  - deleted 3y ago
    [deleted]
  - chromoblob 3y ago
    The reason for undecidability of halting is that a program's state may grow without bound. If a program's memory usage is bounded, its halting can be determined. So the computer is not like a Turing machine since its programs don't use Turing machine's key feature - infinite tape. Although the naive way of deciding halting requires exponential time in program's memory bound, AGIs will speed that up for many programs by using clever math.