5 ms·

The Turing Completeness of PowerPoint [video]

92 points by strzalek 9y ago

Smaug123 9y ago
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?
- 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
Remember though, computational PowerPoint is not the same thing as expressive PowerPoint. :)
- goatlover 9y ago
  Is there a functional PowerPoint?
  - kazinator 9y ago
    No, but speaking of functional, there is a FixedPoint. It's that point in the presentation when your bleary eyes have seen fifty slides and now all subsequent slides look the same.
    - kazinator 9y ago
      Honorable mentions: GunPoint: boss made the presentation mandatory; attendance is checked. Disap-Point: presenter forgot laptop in hotel, uses overhead projector with markers. NeedlePoint: presenter applied cross-stitch simulating Script-Fu in GIMP to images; people at the back clean their glasses and squint in disbelief. CounterPoint: presenter keeps jumping ahead twenty slides and working backward, then forward again. StandPoint: large crowd shows up, enticed by free snacks.
nayuki 9y ago
More computer science humor can be found at SIGBOVIK: http://sigbovik.org/ http://sigbovik.org/
- kazinator 9y ago
  Very nice; that deserves to be a POSIX signal too: kill -BOVIK -1 # send SIGBOVIK to all processes, permissions permitting
flavio81 9y ago
The SIGBOVIK group is really full of comedy genius. I am really laughing with their publications: http://sigbovik.org/2017/proceedings.pdf http://sigbovik.org/2017/proceedings.pdf For example skip to page 114, "Automated Distributed Execution of LLVM code using SQL JIT Compilation" with such gems as: "The resulting PL/pgSQL code can then be executed on any database system, as long as that database system is PostgreSQL" "Another solution to distributed programming has been proposed by Microsoft with their innovative Excel system. In large companies, distributed execution can be achieved using Microsoft Excel by having hundreds of people all sitting on their own machine working with Excel spreadsheets. These hundreds of people combined can easily do the work of a single database server" "For easy reproducibility, we have included a SHA-3 hash of the complete source code [2]. If you want to reproduce the experiments, simply reverse this hash and run the provided source code. " I'm not putting more quotes because they would be spoilers.
candiodari 9y ago
Once again confirmation of Greenspun's 10th law: "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp." You can, of course, safely drop the "C or Fortran" part. Every program I've ever written, if it keeps getting used, maintained and expanded after ~2 years it gets it's own programming language, and therefore usually becomes turing-complete. The most powerful abstraction one can make in an application is the ability to quickly combine large parts of the application into new functionalities, effectively implementing a programming language. Usually this starts with "macros": the ability to specify sequences to be executed in series with either fully implicit data-passing (e.g. we're always acting on this global state), and then someone points out that variables would be really good, and then you do that : local, named variables in macros. And there's your programming language.
- Spivak 9y ago
  Would it be cheating to mention PowerPoint's Visual Basic support? I think your assertion could be even stronger -- every sufficiently advanced program embeds a full programming language.
- gkya 9y ago
  Well, users need to extend our programs or automate repetitive mechanical tasks, at the end of the day, that's a big part of why computation is so useful. We need to customise how certain actions happen, say how a blur effect is applied to a photo, and presets don't always work. Actually I can't see how tuning some sliders to adjust a certain variable is fundamentally different from setting it via an extension language. This process of adjusting a program or extending it is as natural as cutting a pair of jeans and making it into a pair of shorts. And this is why I like emacs so much: within it customisability and extendableness is a product of the programming paradigm, and you don't even need to allow the user explicitly. The online docs, the debugger that automatically comes up when needed, the lisp mechanisms like advices and live editing of the running program furnish a great environment where one is not confined to the application designer's decisions, and where making customisations and extensions are really approachable.

92 points by strzalek 9y ago

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?
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

Remember though, computational PowerPoint is not the same thing as expressive PowerPoint. :)

goatlover 9y ago
Is there a functional PowerPoint?
- kazinator 9y ago
  No, but speaking of functional, there is a FixedPoint. It's that point in the presentation when your bleary eyes have seen fifty slides and now all subsequent slides look the same.
  - kazinator 9y ago
    Honorable mentions: GunPoint: boss made the presentation mandatory; attendance is checked. Disap-Point: presenter forgot laptop in hotel, uses overhead projector with markers. NeedlePoint: presenter applied cross-stitch simulating Script-Fu in GIMP to images; people at the back clean their glasses and squint in disbelief. CounterPoint: presenter keeps jumping ahead twenty slides and working backward, then forward again. StandPoint: large crowd shows up, enticed by free snacks.

nayuki 9y ago

More computer science humor can be found at SIGBOVIK: http://sigbovik.org/ http://sigbovik.org/

kazinator 9y ago
Very nice; that deserves to be a POSIX signal too: kill -BOVIK -1 # send SIGBOVIK to all processes, permissions permitting

flavio81 9y ago

The SIGBOVIK group is really full of comedy genius. I am really laughing with their publications: http://sigbovik.org/2017/proceedings.pdf http://sigbovik.org/2017/proceedings.pdf For example skip to page 114, "Automated Distributed Execution of LLVM code using SQL JIT Compilation" with such gems as: "The resulting PL/pgSQL code can then be executed on any database system, as long as that database system is PostgreSQL" "Another solution to distributed programming has been proposed by Microsoft with their innovative Excel system. In large companies, distributed execution can be achieved using Microsoft Excel by having hundreds of people all sitting on their own machine working with Excel spreadsheets. These hundreds of people combined can easily do the work of a single database server" "For easy reproducibility, we have included a SHA-3 hash of the complete source code [2]. If you want to reproduce the experiments, simply reverse this hash and run the provided source code. " I'm not putting more quotes because they would be spoilers.

candiodari 9y ago

Once again confirmation of Greenspun's 10th law: "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp." You can, of course, safely drop the "C or Fortran" part. Every program I've ever written, if it keeps getting used, maintained and expanded after ~2 years it gets it's own programming language, and therefore usually becomes turing-complete. The most powerful abstraction one can make in an application is the ability to quickly combine large parts of the application into new functionalities, effectively implementing a programming language. Usually this starts with "macros": the ability to specify sequences to be executed in series with either fully implicit data-passing (e.g. we're always acting on this global state), and then someone points out that variables would be really good, and then you do that : local, named variables in macros. And there's your programming language.

Spivak 9y ago
Would it be cheating to mention PowerPoint's Visual Basic support? I think your assertion could be even stronger -- every sufficiently advanced program embeds a full programming language.
gkya 9y ago
Well, users need to extend our programs or automate repetitive mechanical tasks, at the end of the day, that's a big part of why computation is so useful. We need to customise how certain actions happen, say how a blur effect is applied to a photo, and presets don't always work. Actually I can't see how tuning some sliders to adjust a certain variable is fundamentally different from setting it via an extension language. This process of adjusting a program or extending it is as natural as cutting a pair of jeans and making it into a pair of shorts. And this is why I like emacs so much: within it customisability and extendableness is a product of the programming paradigm, and you don't even need to allow the user explicitly. The online docs, the debugger that automatically comes up when needed, the lisp mechanisms like advices and live editing of the running program furnish a great environment where one is not confined to the application designer's decisions, and where making customisations and extensions are really approachable.