• blakestacey@awful.systemsM
    link
    fedilink
    English
    arrow-up
    3
    ·
    edit-2
    11 months ago

    More from the “super-recursive algorithm” page:

    Traditional Turing machines with a write-only output tape cannot edit their previous outputs; generalized Turing machines, according to Jürgen Schmidhuber, can edit their output tape as well as their work tape.

    … the Hell?

    I’m not sure what that page is trying to say, but it sounds like someone got Turing machines confused with pushdown automata.

    • V0ldek@awful.systems
      link
      fedilink
      English
      arrow-up
      5
      ·
      11 months ago

      That’s plainly false btw. The model of a Turing machine with a write-only output tape is fully equivalent to the one where you have a read-write output tape. You prove that as a student in elementary computation theory.

      • aio@awful.systems
        link
        fedilink
        English
        arrow-up
        3
        ·
        edit-2
        11 months ago

        The article is very poorly written, but here’s an explanation of what they’re saying. An “inductive Turing machine” is a Turing machine which is allowed to run forever, but for each cell of the output tape there eventually comes a time after which it never modifies that cell again. We consider the machine’s output to be the sequence of eventual limiting values of the cells. Such a machine is strictly more powerful than Turing machines in that it can compute more functions than just recursive ones. In fact it’s an easy exercise to show that a function is computable by such a machine iff it is “limit computable”, meaning it is the pointwise limit of a sequence of recursive functions. Limit computable functions have been well studied in mainstream computer science, whereas “inductive Turing machines” seem to mostly be used by people who want to have weird pointless arguments about the Church-Turing thesis.

    • self@awful.systemsM
      link
      fedilink
      English
      arrow-up
      3
      ·
      11 months ago

      it’s hard to determine exactly what the author’s talking about most of the time, but a lot of the special properties they claim for inductive Turing machines and super-recursive algorithms appear to be just ordinary von Neumann model shit? also, they seem to be rather taken with the idea that you can modify and extend a Turing machine, but that’s not magic — it’s how I was taught the theoretical foundations for a bunch of CS concepts, like nondeterministic Turing machines and their relationship to NP-complete problems

      • blakestacey@awful.systemsM
        link
        fedilink
        English
        arrow-up
        3
        ·
        edit-2
        11 months ago

        New top-level thread for complaining about the worst/weirdest Wikipedia article in one’s field of specialization?

        I wonder how much Rationalists have mucked up Wikipedia over the years just by being loud and persistent on topics where actual expertise would be necessary to push back.

        • self@awful.systemsM
          link
          fedilink
          English
          arrow-up
          2
          ·
          11 months ago

          New top-level thread for complaining about the worst/weirdest Wikipedia article in one’s field of specialization?

          fuck yes I’m down! finally I’ve got a use for all the weird CS garbage I keep finding. do you figure this’d be better as a SneerClub or TechTakes thread?

          • blakestacey@awful.systemsM
            link
            fedilink
            English
            arrow-up
            3
            ·
            11 months ago

            Our house, our rules, I suppose… but maybe TechTakes is a better fit, unless the examples you have in mind seem rooted in TREACLES particularly.