Talk:Baz

Turing complete proof

Baz can be translated to a modified version of Smallfuck which takes away Smallfuck's > and < instructions, since you can access every variable directly.

(| = newline, l = current line, c = length of code between [ and ])

Smallfuck operation	Baz operation(s)
*	foo = false | goto l+5 | endif | if! foo | foo = true | endif
[	if bar
]	goto l-c

Poolala (talk) 19:49, 2 September 2013 (UTC)

Neither Smallfuck nor Baz is Turing complete, as each program has bounded memory. --Ørjan (talk) 00:31, 3 September 2013 (UTC)

Could you not add new variables as the code requires them, making an unbounded tape? (truly infinite tapes are impossible though) Poolala (talk) 01:14, 3 September 2013 (UTC)

Yes Baz allows you to add new variables as the code requires. OriginalOldMan (talk) 03:25, 3 September 2013 (UTC)

I don't see in the current spec any way to create a variable not mentioned in the initial program. Note, it is well known that you cannot calculate the amount of memory needed for running a program in a Turing complete language in advance (This can be proved via the Halting problem.), so the variables would have to be addable after the program starts. --Ørjan (talk) 03:38, 3 September 2013 (UTC)

I assume the brainfuck program "+[>+]" would be a demonstration of this proof? Poolala (talk) 18:54, 3 September 2013 (UTC)

Well, it's an example of a program which uses unbounded memory if implemented naively. You could make an implementation which optimized that particular program to use constant memory, though. (From one perspective, it never reuses the cells, so they can be garbage collected.) The Halting problem proof can be used to show something much stronger: that no matter how clever your implementation of an interpreter for a Turing complete language, it will have to use unbounded memory when running some non-halting programs. --Ørjan (talk) 05:18, 4 September 2013 (UTC)