4 ms·

For those who decline to watch a video: the author uses animations and hyperlinks to simulate a Turing machine inside a PowerPoint presentation. The actual pape

For those who decline to watch a video: the author uses animations and hyperlinks to simulate a Turing machine inside a PowerPoint presentation. The actual paper is at http://www.andrew.cmu.edu/user/twildenh/PowerPointTM/Paper.pdf http://www.andrew.cmu.edu/user/twildenh/PowerPointTM/Paper.p... . My first thought was that while this was really cool, it does seem to have only a finite tape; I would be quite prepared to believe it was possible to have an unbounded tape, but my mind would be blown. The author admits that the tape is indeed finite.

kazinator 9y ago
I recline to watch videos, myself.
metalliqaz 9y ago
You say that like there are other implementations that actually have an infinite tape. :P
- Smaug123 9y ago
  Logically infinite if not practically infinite. Python specifies a language which has access to logically infinite amounts of memory: it's an implementation detail that there's an upper bound on the size of tape it can simulate on a computer. PPTXTM is by design unable to simulate unbounded tapes.
  - Pharylon 9y ago
    But by this definition, C isn't Turing Complete either. https://cs.stackexchange.com/questions/60965/is-c-actually-turing-complete https://cs.stackexchange.com/questions/60965/is-c-actually-t...
    - deleted 9y ago
      [deleted]
    - bluGill 9y ago
      When talking about Turing completeness I use an alternate definition of infinity that I call practically infinite: for a given a program that halts on an arbitrary Turing machine it also halts on this specific on. I call this practical Turing completeness (though I suspect the literature has already considered this idea and has a different term)
      - Smaug123 9y ago
        Could you be more precise, please? I'm afraid I don't understand the definition you've given. Can you make your quantifiers explicit?
        bluGill 9y ago
        I mean that the technical limits are a not an issue for the program you want to run. Hello World will run on an AppleII computer, but it doesn't have enough memory to run Libre Office (Assume an unlimited budget to create/port the compiler, POSIX layer, X server ...) If the conversation is concerned with running Hello world it doesn't matter that an AppleII can't do everything, for our purposes it can do anything. If we expand the conversation a little but though we realize this machine is unable to run many things we find useful today.
    - Smaug123 9y ago
      I'm happy with that. It's an explicit design decision of C that there is a bound on the number of pointers. If I want to consider a Turing-complete variant, all I need to do is let pointers be of arbitrary size somehow, or let it have an "integer" type which really does hold any size of integer.
      - empath75 9y ago
        If we're doing that why not just imagine a PowerPoint presentation that's not bounded?
        Smaug123 9y ago
        Sure. PPTXTM+unbounded is to PPTXTM as C-with-integers is to C, and as Python is to Python-whose-specification-limits-it-to-boundedly-many-objects.
deleted 9y ago
[deleted]
laken 9y ago
An interesting thing about the paper, is that the paper itself is formatted and created using PowerPoint... Quite the dedication.
- jonnycomputer 9y ago
  time to implement LaTeX in PowerPoint.

kazinator 9y ago

I recline to watch videos, myself.

metalliqaz 9y ago

You say that like there are other implementations that actually have an infinite tape. :P

Smaug123 9y ago
Logically infinite if not practically infinite. Python specifies a language which has access to logically infinite amounts of memory: it's an implementation detail that there's an upper bound on the size of tape it can simulate on a computer. PPTXTM is by design unable to simulate unbounded tapes.
- Pharylon 9y ago
  But by this definition, C isn't Turing Complete either. https://cs.stackexchange.com/questions/60965/is-c-actually-turing-complete https://cs.stackexchange.com/questions/60965/is-c-actually-t...
  - deleted 9y ago
    [deleted]
  - bluGill 9y ago
    When talking about Turing completeness I use an alternate definition of infinity that I call practically infinite: for a given a program that halts on an arbitrary Turing machine it also halts on this specific on. I call this practical Turing completeness (though I suspect the literature has already considered this idea and has a different term)
    - Smaug123 9y ago
      Could you be more precise, please? I'm afraid I don't understand the definition you've given. Can you make your quantifiers explicit?
      - bluGill 9y ago
        I mean that the technical limits are a not an issue for the program you want to run. Hello World will run on an AppleII computer, but it doesn't have enough memory to run Libre Office (Assume an unlimited budget to create/port the compiler, POSIX layer, X server ...) If the conversation is concerned with running Hello world it doesn't matter that an AppleII can't do everything, for our purposes it can do anything. If we expand the conversation a little but though we realize this machine is unable to run many things we find useful today.
  - Smaug123 9y ago
    I'm happy with that. It's an explicit design decision of C that there is a bound on the number of pointers. If I want to consider a Turing-complete variant, all I need to do is let pointers be of arbitrary size somehow, or let it have an "integer" type which really does hold any size of integer.
    - empath75 9y ago
      If we're doing that why not just imagine a PowerPoint presentation that's not bounded?
      - Smaug123 9y ago
        Sure. PPTXTM+unbounded is to PPTXTM as C-with-integers is to C, and as Python is to Python-whose-specification-limits-it-to-boundedly-many-objects.

deleted 9y ago

[deleted]

laken 9y ago

An interesting thing about the paper, is that the paper itself is formatted and created using PowerPoint... Quite the dedication.

jonnycomputer 9y ago
time to implement LaTeX in PowerPoint.