3 ms·

What do you regard as the first digital, Turing-complete (if given enough memory) computer? ENIAC, for example, was not a stored-program computer. Reprogrammin

What do you regard as the first digital, Turing-complete (if given enough memory) computer? ENIAC, for example, was not a stored-program computer. Reprogramming required rewiring the machine. On the other hand, by clever use of arithmetic calculations, https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.665 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.... says the Z3 could perform as a Universal Computer, even though, quoting its Wikipedia page, "because it lacked conditional branching, the Z3 only meets this definition by speculatively computing all possible outcomes of a calculation." Which makes me think the old punched card mechanical tabulators could also be rigged up as a universal machine, were someone clever enough. "Surprisingly Turing-Complete" or "Accidentally Turing Complete" is a thing, after all, and https://gwern.net/turing-complete https://gwern.net/turing-complete includes a bunch of them.

kragen 3y ago
let me preface this with the disclaimer that i am far from an expert on the topic probably numerous eddies in natural turbulent fluid flows have been digital turing-complete computers, given what we know now about the complexity of turbulence and the potential simplicity of turing-complete behavior. but is there an objective, rather than subjective, way to define this? how complicated are our input-preparation and output-interpretation procedures allowed to be? if there is no limit, then any stone or grain of sand will appear to be turing-complete a quibble: the eniac was eventually augmented to support stored-program operation but not, as i understand it, until after the ias machine (the johnniac) was already operational another interesting question there is how much human intervention we permit; the ias machine and the eniac were constantly breaking down and requiring repairs, after all, and wouldn't have been capable of much computation without constant human attention. suppose we find that there is a particular traditional card game in which players can use arbitrarily large numbers. if the players decide to simulate minsky's two-counter machine, surely the players are turing-complete; is the game? are the previous games also turing-complete, the ones where they did not make that decision? does it matter if there happens to be a particular state of the cards which obligates them to simulate a two-counter machine? if instead of attempting to measure the historical internal computational capability of systems that the humans could not perceive at the time, such as thunderstorms and the z3, we use the subjective standard of what people actually programmed to perform universal computation, then the ias machine or one of its contemporaries was the first turing-complete computer (if given enough memory); that's when universal computation first made its effects on human society felt
- eesmith 3y ago
  > is the game? Sure. One of the "Surprisingly Turing-Complete" examples is that "Magic: the Gathering: not just TC, but above arithmetic in the hierarchy ". See https://arxiv.org/abs/1904.09828 https://arxiv.org/abs/1904.09828 for the preprint "Magic: The Gathering is Turing Complete", https://arstechnica.com/science/2019/06/its-possible-to-build-a-turing-machine-within-magic-the-gathering/ https://arstechnica.com/science/2019/06/its-possible-to-buil... for an Ars Technica article, and https://hn.algolia.com/?q=magic+turing https://hn.algolia.com/?q=magic+turing for the many HN submissions on that result.
  - _a_a_a_ 3y ago
    Could you explain "above arithmetic in the hierarchy" in a few words, TIA, never heard of this
    - eesmith 3y ago
      Nope. The source page links to https://en.wikipedia.org/wiki/Arithmetical_hierarchy https://en.wikipedia.org/wiki/Arithmetical_hierarchy . I can't figure it out. An HN comment search, https://hn.algolia.com/?dateRange=all&page=0&prefix=false&query=Arithmetical%20hierarchy&sort=byDate&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu... , finds a few more lay examples, with https://news.ycombinator.com/item?id=21210043 https://news.ycombinator.com/item?id=21210043 by dwohnitmok being the easiest for me to somewhat make sense of. I think the idea is, suppose you have an oracle which tells you if a Turning machine will halt, in finite time. There will still halting problems for that oracle system, which requires an oracle from a higher level system. (That is how I interpret "an oracle that magically gives you the answer to the halting problem for a lower number of interleavings will have its own halting problem it cannot decide in higher numbers of interleavings").
      - BoiledCabbage 3y ago
        This appears to discuss it a bit more. Not certain if it's more helpful than the comment (still going through it), but it does cover it more in detail. https://risingentropy.com/the-arithmetic-hierarchy-and-computability/ https://risingentropy.com/the-arithmetic-hierarchy-and-compu...
midasuni 3y ago
Colossus was before eniac, but was also programmed by plugging up. Baby was a stored program machine and had branching

kragen 3y ago

let me preface this with the disclaimer that i am far from an expert on the topic probably numerous eddies in natural turbulent fluid flows have been digital turing-complete computers, given what we know now about the complexity of turbulence and the potential simplicity of turing-complete behavior. but is there an objective, rather than subjective, way to define this? how complicated are our input-preparation and output-interpretation procedures allowed to be? if there is no limit, then any stone or grain of sand will appear to be turing-complete a quibble: the eniac was eventually augmented to support stored-program operation but not, as i understand it, until after the ias machine (the johnniac) was already operational another interesting question there is how much human intervention we permit; the ias machine and the eniac were constantly breaking down and requiring repairs, after all, and wouldn't have been capable of much computation without constant human attention. suppose we find that there is a particular traditional card game in which players can use arbitrarily large numbers. if the players decide to simulate minsky's two-counter machine, surely the players are turing-complete; is the game? are the previous games also turing-complete, the ones where they did not make that decision? does it matter if there happens to be a particular state of the cards which obligates them to simulate a two-counter machine? if instead of attempting to measure the historical internal computational capability of systems that the humans could not perceive at the time, such as thunderstorms and the z3, we use the subjective standard of what people actually programmed to perform universal computation, then the ias machine or one of its contemporaries was the first turing-complete computer (if given enough memory); that's when universal computation first made its effects on human society felt

eesmith 3y ago
> is the game? Sure. One of the "Surprisingly Turing-Complete" examples is that "Magic: the Gathering: not just TC, but above arithmetic in the hierarchy ". See https://arxiv.org/abs/1904.09828 https://arxiv.org/abs/1904.09828 for the preprint "Magic: The Gathering is Turing Complete", https://arstechnica.com/science/2019/06/its-possible-to-build-a-turing-machine-within-magic-the-gathering/ https://arstechnica.com/science/2019/06/its-possible-to-buil... for an Ars Technica article, and https://hn.algolia.com/?q=magic+turing https://hn.algolia.com/?q=magic+turing for the many HN submissions on that result.
- _a_a_a_ 3y ago
  Could you explain "above arithmetic in the hierarchy" in a few words, TIA, never heard of this
  - eesmith 3y ago
    Nope. The source page links to https://en.wikipedia.org/wiki/Arithmetical_hierarchy https://en.wikipedia.org/wiki/Arithmetical_hierarchy . I can't figure it out. An HN comment search, https://hn.algolia.com/?dateRange=all&page=0&prefix=false&query=Arithmetical%20hierarchy&sort=byDate&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu... , finds a few more lay examples, with https://news.ycombinator.com/item?id=21210043 https://news.ycombinator.com/item?id=21210043 by dwohnitmok being the easiest for me to somewhat make sense of. I think the idea is, suppose you have an oracle which tells you if a Turning machine will halt, in finite time. There will still halting problems for that oracle system, which requires an oracle from a higher level system. (That is how I interpret "an oracle that magically gives you the answer to the halting problem for a lower number of interleavings will have its own halting problem it cannot decide in higher numbers of interleavings").
    - BoiledCabbage 3y ago
      This appears to discuss it a bit more. Not certain if it's more helpful than the comment (still going through it), but it does cover it more in detail. https://risingentropy.com/the-arithmetic-hierarchy-and-computability/ https://risingentropy.com/the-arithmetic-hierarchy-and-compu...

midasuni 3y ago

Colossus was before eniac, but was also programmed by plugging up. Baby was a stored program machine and had branching