Talk:Brainfuck/w/index.php?title=Talk:Brainfuck/index.php

So... ais523? Ørjan? Anyone want to take the bait and analyse this thing's computational class? :) —ehird 18:05, 27 December 2010 (UTC)

Unless I misread something, the defined behavior is exactly R, the set of all total functions. I should also note that since you don't constrain an interpreter's behavior when it's presented with an invalid program, technically all existing brainfuck interpreters are also Brainfuck/w/index.php?title=Talk:Brainfuck/index.php interpreters. --Chris Pressey 19:38, 28 December 2010 (UTC)

No, that's not quite right; because you don't have input here, this is the set of all total computations, not total functions. I don't know if that class has a standard letter (because people tend to study functions rather than computations and dismiss the difference between them as uninteresting), but it is easy enough to derive from R by fixing the input of every function to a constant. (Since everything in R is computable, so is the new set; and since R includes all the functions that ignore their input, the new set includes them too.) --Chris Pressey 19:53, 28 December 2010 (UTC)

The existing-interpreter thing was definitely intentional, because I don't believe you can truly regulate what things do on invalid programs. (XML tries to do this, but it's lies.) But yes, I keep talking about error-conformant implementations when talking about this. Some fun facts:

• The language is sub-Turing, but any error-conformant interpreter must be super-Turing.
• One can emulate full brainfuck-sans-IO with a simple shell script and an error-conformant interpreter. First, submit the program to the interpreter; if it succeeds, all is well. If it errors out, consider an interpreter-generator function BF(p,i,tape), which generates a program that runs step i (for some arbitrary definition of step) of BF program p, given the tape (including pointer) tape. Then just have an infinite loop doing BF(p,i++,tape), where you have to keep track of tape. (Presumably the interpreter outputs it at the end of the program.)

—ehird 00:32, 29 December 2010 (UTC)

I'm not sure I follow the first part; you can "truly regulate" what is supposed to happen with an invalid program as much as you can "truly regulate" anything else in a language spec. Just specify what is supposed to happen with an invalid program, and how and at what point the program needs to be recognized as invalid. That is to say, a language need not have undefined behavior so long as it is careful about defining its behavior under all conditions; that's why I used the phrase "defined behavior" in my first response. (Whether you want undefined behavior or not (and consider it an error or not) in this language is, of course, up to you.) --Chris Pressey 21:12, 9 January 2011 (UTC)

As for emulating brainfuck -- I wouldn't use the word arbitrary for the kind of step you simulate at each step, because of course you can't do "the rest of the program, even if it doesn't halt" as a step. Further, with a suitable notion of step, you don't need a language as powerful as Brainfuck/w/index.php?title=Talk:Brainfuck/index.php to perform the steps; you could use something that implements only the primitive recursive computations, for example. --Chris Pressey 21:21, 9 January 2011 (UTC)

test

test

Hey, spambot, this is a serious language, not a spambot honeypot page. Go away! --ais523 19:20, 12 April 2011 (UTC)

It's okay, I like you. You were the inspiration for this language! Can we be friends? —ehird 23:54, 12 April 2011 (UTC)

Ey Chris

The defined behavior of the language can compute the set of total computations (that is, take the set R of all total functions, pick some fixed value n, and give all the functions n for input instead of allowing it to vary.)

What if you picked n = Chaitin's constant? —ehird 04:22, 7 June 2011 (UTC)