Talk:Portal

Turing Completeness

Since I removed the Turing complete and Turing Tarpit tags, I figured I would include a proof that portal is not TC.

Proof of Turing Incompleteness

First since the execution of no instruction is dependent on the state of the tape, the tape is not usable memory as far as a Turing Machine goes. This leaves us with two sections of usable memory, the instruction pointer, which is bounded by the length of the program, and the locations of the two portals. Since the portals can only get closer to each other this memory is also bounded. Since each part of the memory is bounded the memory as a whole is bounded and thus Portal is a finite state machine and thus is not Turing complete.

Wheatwizard (talk) 03:04, 30 November 2017 (UTC)