[Smaug123]

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

[metalliqaz]

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

[Smaug123]

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]

But by this definition, C isn't Turing Complete either.

https://cs.stackexchange.com/questions/60965/is-c-actually-t...

[bluGill]

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]

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]

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]

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]

If we're doing that why not just imagine a PowerPoint presentation that's not bounded?

[Smaug123]

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.

[kazinator]

I recline to watch videos, myself.

[laken]

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

[jonnycomputer]

time to implement LaTeX in PowerPoint.