5 ms·

Wouldn't you also need a way of storing information (preferably an unlimited amount of information) for Skylines to be turing complete? How would you implement

by ekiwi 7y ago

Wouldn't you also need a way of storing information (preferably an unlimited amount of information) for Skylines to be turing complete? How would you implement the tape of the turing machine?

davrosthedalek 7y ago
You can make memory out of logic gates.
- zokier 7y ago
  Adders belong to category of combinational logic, which by definition excludes memory. So OP is right, they do not yet demonstrate Turing Completeness. I imagine, but don't actually know, that they would be about as expressive as dfa, which are few steps below turing machines
  - davrosthedalek 7y ago
    He builds the adders from ANDs, ORs and NOTs. With these, you can also build flip-flops, which are memory. (Actually, it's enough to have only NAND (or NOR) to build all logic circuits, including memory)
- accrual 7y ago
  A flip-flop or latch is one way to store a single bit using just logic gates, using two NOR gates or two NAND gates. [0] [0] https://en.wikibooks.org/wiki/Electronics/Flip_Flops https://en.wikibooks.org/wiki/Electronics/Flip_Flops
jerf 7y ago
Yes. By convention we ignore that requirement for calling something Turing-complete, since in the absolute sense, nothing in the universe is Turing-complete.
- derefr 7y ago
  Is there some distinction to be made between Turing machines with tapes of fixed capacity, and ones whose capacities are limited by their execution substrate, such that they’ll support as much memory as they are “given” by the environment? I’m picturing here the difference between Turing machines in the Game of Life that take place on a fixed area of the grid, vs. ones that attempt to just index out to whatever grid position they need, whether that causes wraparound or not.
  - jerf 7y ago
    I'm not sure there's "a" distinction, but there's a couple I tend to think about. This isn't necessarily anything formal or official. One is just, could this be Turing complete if we gave it infinite resources in the obvious manner? e.g., in Life, an infinite grid, for a modern computer, hypothetically infinite RAM and disk and time, etc. I think this is the one most people are using. Another one I tend to think about is, since the system is theoretically modeled by a finite state automaton, you can ask the question "how large would the manifested finite state automaton be?" For these toy models such as Cities, or the CSS Turing machine [1], or some small chunk of a Rule 110 encoding, often the answer is still something that might fit in a real computer as a table. There's a sense in which that's so small that using Turing Machine tools to understand the system may still not be the best way to look at it. By contrast, the FSM for something like the computer you're using to read this would be so staggeringly large that it could never fit into our universe by any encoding that doesn't somehow "cheat" and cease to be an FSM model. (That is, we can "compress" the FSM model right back down by encoding it as a Turing machine, but that defeats the purpose, no?) Even though it is theoretically a correct model of your computer, it's not useful for us humans to understand the behavior of the system. The tools of computer science for Turing-complete systems are far more applicable to understanding what it does than the FSM-based tools, even if, technically, they don't fully apply. Often they still do de facto; while theoretically it is possible to create a program that can examine the real state of any real computer and determine whether it's going to halt [2], the result would (without proof) again be so large that it couldn't possibly be manifested in the real universe, so in reality the results of the Halting Problem and similar TM-based analyses are still generally "correct" for us in practice, even if they aren't in principle. Symantec isn't going to be selling a 10^100^100^100-byte-sized anti-virus program to us any time soon. So there's also a sort of line you can draw based on the size difference between the TM-based model and the FSM-based model. It's fuzzy, although, since the FSM-based model grows exponentially (super-exponentially?), it's less fuzzy than you may think since it doesn't take much for the FSM model to go to plaid. [1]: https://notlaura.com/is-css-turing-complete/ https://notlaura.com/is-css-turing-complete/ [2]: I'm not 100% sure this is true, but I'm pretty sure it is; I suspect we can prove that the only way this machine can run is to simply execute the computer internally and record every single state it passes through; eventually it'll either repeat a previous state or halt. You can't even assume you can compress the past history very well since for any compression scheme there are programs that will pass through the states in an order that will pessimize your compression (I'm pretty sure), so we rapidly exceed the universe's storage capacity trying to store all the previous states even with such cleverness as we might still be able to muster.

by ekiwi 7y ago

Wouldn't you also need a way of storing information (preferably an unlimited amount of information) for Skylines to be turing complete? How would you implement the tape of the turing machine?

davrosthedalek 7y ago

You can make memory out of logic gates.

zokier 7y ago
Adders belong to category of combinational logic, which by definition excludes memory. So OP is right, they do not yet demonstrate Turing Completeness. I imagine, but don't actually know, that they would be about as expressive as dfa, which are few steps below turing machines
- davrosthedalek 7y ago
  He builds the adders from ANDs, ORs and NOTs. With these, you can also build flip-flops, which are memory. (Actually, it's enough to have only NAND (or NOR) to build all logic circuits, including memory)
accrual 7y ago
A flip-flop or latch is one way to store a single bit using just logic gates, using two NOR gates or two NAND gates. [0] [0] https://en.wikibooks.org/wiki/Electronics/Flip_Flops https://en.wikibooks.org/wiki/Electronics/Flip_Flops

jerf 7y ago

Yes. By convention we ignore that requirement for calling something Turing-complete, since in the absolute sense, nothing in the universe is Turing-complete.

derefr 7y ago
Is there some distinction to be made between Turing machines with tapes of fixed capacity, and ones whose capacities are limited by their execution substrate, such that they’ll support as much memory as they are “given” by the environment? I’m picturing here the difference between Turing machines in the Game of Life that take place on a fixed area of the grid, vs. ones that attempt to just index out to whatever grid position they need, whether that causes wraparound or not.
- jerf 7y ago
  I'm not sure there's "a" distinction, but there's a couple I tend to think about. This isn't necessarily anything formal or official. One is just, could this be Turing complete if we gave it infinite resources in the obvious manner? e.g., in Life, an infinite grid, for a modern computer, hypothetically infinite RAM and disk and time, etc. I think this is the one most people are using. Another one I tend to think about is, since the system is theoretically modeled by a finite state automaton, you can ask the question "how large would the manifested finite state automaton be?" For these toy models such as Cities, or the CSS Turing machine [1], or some small chunk of a Rule 110 encoding, often the answer is still something that might fit in a real computer as a table. There's a sense in which that's so small that using Turing Machine tools to understand the system may still not be the best way to look at it. By contrast, the FSM for something like the computer you're using to read this would be so staggeringly large that it could never fit into our universe by any encoding that doesn't somehow "cheat" and cease to be an FSM model. (That is, we can "compress" the FSM model right back down by encoding it as a Turing machine, but that defeats the purpose, no?) Even though it is theoretically a correct model of your computer, it's not useful for us humans to understand the behavior of the system. The tools of computer science for Turing-complete systems are far more applicable to understanding what it does than the FSM-based tools, even if, technically, they don't fully apply. Often they still do de facto; while theoretically it is possible to create a program that can examine the real state of any real computer and determine whether it's going to halt [2], the result would (without proof) again be so large that it couldn't possibly be manifested in the real universe, so in reality the results of the Halting Problem and similar TM-based analyses are still generally "correct" for us in practice, even if they aren't in principle. Symantec isn't going to be selling a 10^100^100^100-byte-sized anti-virus program to us any time soon. So there's also a sort of line you can draw based on the size difference between the TM-based model and the FSM-based model. It's fuzzy, although, since the FSM-based model grows exponentially (super-exponentially?), it's less fuzzy than you may think since it doesn't take much for the FSM model to go to plaid. [1]: https://notlaura.com/is-css-turing-complete/ https://notlaura.com/is-css-turing-complete/ [2]: I'm not 100% sure this is true, but I'm pretty sure it is; I suspect we can prove that the only way this machine can run is to simply execute the computer internally and record every single state it passes through; eventually it'll either repeat a previous state or halt. You can't even assume you can compress the past history very well since for any compression scheme there are programs that will pass through the states in an order that will pessimize your compression (I'm pretty sure), so we rapidly exceed the universe's storage capacity trying to store all the previous states even with such cleverness as we might still be able to muster.