Talk:MiniMAX

Smallfuck vs F2

Is the "&" instruction really required? I'd say that if you take F2 as basis instead of Smallfuck (without thinking too much) F2 programs could be compiled to MiniMAX just as well as Smallfuck ones. pgimeno 07:45, 13 May 2006 (UTC)

The problem is that Smallfuck has a limited-length data storage, so cannot be complete without some way to extend the tape. In MiniMAX, extending the tape must be explicit; > and & must be distinct, as & clears the new location of the tape, and > would access off the end of the tape. --ais523 09:14, 16 May 2006 (UTC)

Actually F2 (which is known to be Turing-complete) does not require a bounded tape. Furthermore you can simulate & using >[+]. --pgimeno 19:57, 18 May 2006 (UTC)

I know F2 doesn't require a bounded tape. However, MiniMAX does; at any given instant, the tape is bounded. & is in the MiniMAX Turing-completeness proof because the only way to get more data storage in MiniMAX is to run the command starting at the penultimate word of the program, which extends its data store by one word. So, an F2 to MiniMAX conversion could be written, but would be more complicated, as the program would have to continually check to see if it was at the right-hand end of the MiniMAX storage area, extending if it was and moving right if it wasn't (to avoid clobbering data). This could be done, say, by reserving every second tape location as 0 if it wasn't the end of the tape and 1 if it was; then < would become << and > would become >[+&&+<<]>, but it would be worse than the extended Smallfuck proof. --ais523 12:44, 19 May 2006 (UTC)