00:27:06 -!- ShadowHntr has joined.
00:30:52 -!- RodgerTheGreat has joined.
00:54:48 <bsmntbombdood> http://www.cs.duke.edu/~rodger/baking/cs030327.html
01:32:45 <graue> edible turing machines, eh?
01:35:03 <graue> if you could execute the program by eating the muffins, that would make it better
01:36:09 <RodgerTheGreat> bitwise cyclic tag would be awesome with an infinite series of muffins extending to the right
01:37:18 <graue> no, not infinite, remember, just unbounded
02:18:14 -!- GreaseMonkey has joined.
03:03:58 <graue> infinite muffins is too expensive and nobody can afford it
03:04:08 <graue> but unbounded muffins just means you have to be ready to go out and buy another one if need be
03:04:24 <graue> in reality, there has to be a bound, but you can fake it
03:06:47 <graue> i believe it's a turing machine
03:40:28 -!- GreaseMonkey has changed nick to ^_`.
03:53:08 -!- calamari has joined.
03:54:06 -!- GregorR_ has joined.
03:55:21 -!- oklopol has quit (calvino.freenode.net irc.freenode.net).
03:55:21 -!- sekhmet has quit (calvino.freenode.net irc.freenode.net).
03:55:21 -!- NK` has quit (calvino.freenode.net irc.freenode.net).
03:55:21 -!- SimonRC has quit (calvino.freenode.net irc.freenode.net).
03:55:21 -!- GregorR has quit (calvino.freenode.net irc.freenode.net).
03:55:41 -!- ^_` has quit (Killed by ballard.freenode.net (Nick collision)).
03:55:42 -!- oklopol has joined.
03:55:42 -!- sekhmet has joined.
03:55:42 -!- GregorR has joined.
03:55:42 -!- NK` has joined.
03:55:42 -!- SimonRC has joined.
03:55:45 -!- GregorR has quit (Nick collision from services.).
03:56:13 -!- thematrixeatsyou has joined.
03:56:14 -!- GregorR_ has changed nick to GregorR.
03:56:57 -!- thematrixeatsyou has changed nick to GreaseMonkey.
04:07:42 -!- SimonRC has quit (calvino.freenode.net irc.freenode.net).
04:07:42 -!- sekhmet has quit (calvino.freenode.net irc.freenode.net).
04:07:42 -!- NK` has quit (calvino.freenode.net irc.freenode.net).
04:07:42 -!- oklopol has quit (calvino.freenode.net irc.freenode.net).
04:09:12 -!- oklopol has joined.
04:09:12 -!- sekhmet has joined.
04:09:12 -!- NK` has joined.
04:09:12 -!- SimonRC has joined.
04:11:46 -!- RodgerTheGreat has quit.
04:35:38 <graue> the wiki db backups were messed up for a few days
04:35:48 <graue> i think they're good now
05:03:06 -!- Sgeo has quit ("Leaving").
05:30:37 -!- Arrogant has joined.
05:50:32 -!- digital_me has quit (Read error: 110 (Connection timed out)).
05:52:39 -!- calamari has quit (Remote closed the connection).
06:10:56 -!- ShadowHntr has quit ("End of line.").
06:50:28 -!- anonfunc has joined.
07:30:01 -!- GreaseMonkey has quit ("There's always another bug to fix").
07:59:59 -!- clog has quit (ended).
08:00:00 -!- clog has joined.
08:18:46 -!- anonfunc has quit.
08:19:39 -!- anonfunc has joined.
08:20:38 -!- anonfunc has quit (Client Quit).
08:21:51 -!- anonfunc has joined.
08:54:43 -!- Arrogant has quit ("Leaving").
09:03:04 -!- anonfunc has quit.
09:15:46 -!- sebbu has joined.
10:27:32 -!- jix has joined.
10:37:13 -!- nazgjunk has joined.
11:32:11 -!- jix__ has joined.
11:40:36 -!- jix has quit (Read error: 110 (Connection timed out)).
11:45:17 -!- jix__ has changed nick to jix.
12:25:02 -!- tgwizard has joined.
12:27:18 -!- UpTheDownstair has joined.
12:28:05 -!- nazgjunk has quit (Read error: 104 (Connection reset by peer)).
12:30:29 -!- UpTheDownstair has changed nick to nazgjunk.
12:43:30 -!- nazgjunk has quit ("Leaving").
15:33:51 -!- mike_the_person has joined.
15:36:15 <EgoBot> help ps kill i eof flush show ls bf_txtgen usertrig daemon undaemon
15:36:17 <EgoBot> 1l 2l adjust axo bch bf{8,[16],32,64} funge93 fyb fybs glass glypho kipple lambda lazyk linguine malbolge pbrain qbf rail rhotor sadol sceql trigger udage01 unlambda whirl
15:45:25 -!- mike_the_person has quit ("Chatzilla 0.9.77 [Firefox 1.5.0.10/2007021601]").
15:52:41 -!- oerjan has joined.
17:04:28 -!- sekhmet_ has joined.
17:05:04 -!- sekhmet has quit (Read error: 104 (Connection reset by peer)).
17:09:59 -!- sekhmet_ has changed nick to sekhmet.
18:43:33 -!- twice11 has joined.
18:44:05 -!- Sgeo has joined.
18:51:20 <twice11> On the wiki, it says 0x29A is turing complete. Are there any references supporting that claim?
18:57:49 <oerjan> it seems to contain combinator calculus as a subset, by using the sk~ commands.
18:58:48 <twice11> I did not succeed in finding out how to create a function on the stack that increments the accumulator by to when executed (getting passed enough arguments to start running).
19:00:18 <twice11> And I am quite lost in finding out how to do anything useful if i can't somehow save the accumulator to the stack (in form of a function).
19:01:58 <twice11> That does not work, because (+x)y gets already executed when I try to build the function.
19:03:18 <oerjan> use the abstraction elimination of \z. +(+xy)y
19:05:14 <twice11> Sorry, I can't follow you on that.
19:05:34 -!- tgwizard has quit (Remote closed the connection).
19:06:05 <oerjan> let me use Unlambda notation.
19:06:58 <oerjan> ``s``s`k+``s``s`k+`kx`ky`ky
19:08:11 <twice11> I am not used to unlambda, but you apply the s combinator to (k+). I already tried that
19:08:49 <twice11> It does not work, because (((s(k+))x)y) gets converted to (((k+)x)y)
19:09:16 <twice11> This does not get anything, because the k combinator is too deep inside the parens to match any of the reduction rules.
19:10:14 <twice11> My implementation of 0x29A does *not* to the step from (((k+)x)y) to ((+x)y)
19:10:36 <twice11> I think this is according to the documentation.
19:11:05 <oerjan> well then you mean (((k+)y)(xy)
19:11:07 <twice11> Oops. It should do the step from (((k+)x)y) to (+x), of course...
19:12:04 <twice11> To put it right. I meant (((s(k+)x)y) gets (((k+)y)(xy)), and this gets stuck.
19:13:09 <twice11> You get stuck as soon as the "x" in (((sx)y)z) is anything but a k-like combinator (k,+-.,) or s, maybe applied to something.
19:13:14 <oerjan> i see. so there is an error in the embedding of combinator calculus into 0x29a.
19:14:09 <twice11> I admit to have overlooked in my search for a possibility of doing something useful what happens if x in (((sx)y)z) is is of the form (sx).
19:16:50 <oerjan> right. it evaluates only the top level of the function, if you take the description literally.
19:17:58 <oerjan> seems like a bug in the language description to me.
19:18:45 <twice11> I think I suceeded in writing a +2 function.
19:19:14 <twice11> (((s(sa))b)c) with a=(+), b=(+x) and c=y
19:19:33 <twice11> [where x, y are don't care functions]
19:20:57 <twice11> Yes, I tried it. It works.
19:20:58 <oerjan> =sac(bc) = a(bc)(c(bc))
19:22:02 <oerjan> = ++r, bc = ++r, ++r, x
19:23:07 <twice11> See http://pastebin.ca/389482.
19:24:56 <twice11> The haskell 0x29A interpreter is at http://pastebin.ca/389491
19:31:26 <oerjan> there seems to be no way to duplicate values on the stack.
19:31:55 <oerjan> so a function can only be evaluated once.
19:32:23 <twice11> Yes. This is also a problem.
19:33:15 <twice11> But I did not yet prove whether it is impossible to create a function that runs the function and returns the function on the stack.
19:33:22 <twice11> This would solve the problem.
19:34:02 <oerjan> i was pondering whether you could make a pair of functions simulate a brainfuck tape.
19:35:07 <twice11> I got lost at simulating the tape when I found out that there is no way to access anything but top-of-stack and next-to-top-of-stack.
19:36:00 -!- twice11 has quit ("taking a break.").
19:41:33 -!- RodgerTheGreat has joined.
20:07:31 -!- bsmntbombdood has changed nick to xor.
20:21:09 -!- ShadowHntr has joined.
21:18:28 -!- twice11 has joined.
21:18:48 <oerjan> hi, i think i solved the tape implementation
21:19:33 <oerjan> i put a description on the wiki.
21:20:23 <twice11> I think I also have an idea. You use two functions as stack.
21:20:38 <twice11> One for the values before current, one for values after currents.
21:20:51 <oerjan> that was my idea too :)
21:21:12 <twice11> I will try to implement it on my own, just as an exercise.
21:21:37 <twice11> But this has the problem that brainfucks + and - operations get O(N).
21:21:53 <twice11> I don't see a way around it.
21:22:00 <oerjan> eh, i save the _current_ cell in the register.
21:22:28 <oerjan> maybe you mean > and < ?
21:22:39 <twice11> Oh, sorry. Yes, of course.
21:23:14 <oerjan> actually not O(N), but with a possible constant factor <= 256.
21:23:33 <oerjan> so still technically O(1).
21:23:54 <twice11> OK, I used to use 16 or 32 bit cells on brainfuck with numeric I/O
21:24:16 <twice11> So I am used to cells containing 5-figure numbers.
21:24:28 <oerjan> 0x29A has byte registers.
21:25:21 <twice11> Yes :-). So it seems like emulating byte-brainfuck with ascii-code I/O is the simplest thing.
21:26:24 <twice11> BTW, is there literature on doing binary arithmetic in bf where cells are used as bits, to get O(logN) addition.
21:26:39 <twice11> That was a strange idea I had some year ago.
21:27:03 <twice11> This kind of bf use seems to translate into 0x29A without too high performance penalties.
21:27:18 <oerjan> i think i've seen it mentioned. Try looking at boolfuck.
21:29:50 <twice11> Yes, the translation they offer is mainly the same idea.
21:31:05 <twice11> But the problem with boolfuck compared to my brainfuck-with-binary approach
21:31:19 <twice11> is that I can't detect carries in boolfuck.
21:31:46 <twice11> And of course, performance is complete gone after translation from boolfuck to brainfuck.
21:36:01 <oerjan> maybe the broken S combinators work if you use continuation passing style.
21:36:20 <oerjan> because that corresponds to always staying at the top expression.
21:36:40 <twice11> The whole language seems to work only with CPS.
21:37:05 <twice11> And I currently think about the k-style combinators (+-,.) just as
21:37:20 <twice11> operators that get a continuation and a "start-now" flag as parameters.
21:37:52 <twice11> I am still puzzled about how to write a +3 function, but don't tell me. I will find out on my own.
21:38:15 <twice11> I seem to have run into the "broken S combinators" on my first attempt.
21:38:25 <oerjan> don't look at the wiki then because i have exactly that as the example
21:38:50 <twice11> I just plugged the +2 function into the +2 function. Probably I should have changed the other + to +2.
21:41:09 -!- twice11 has quit ("tearing down dial-up line. back later. reading logs.").
22:21:08 -!- twice11 has joined.
22:21:36 <twice11> oerjan: I got the same results as you.
22:22:15 <twice11> I use "ss+~~%~" to add one to the result of the function currently on the stack
22:22:33 <twice11> and "k%~" to separate to functions.
22:22:34 <oerjan> by coincidence? although i did start with that +2 function you mentioned earlier.
22:23:11 <oerjan> well then it simply has to work :)
22:23:22 <twice11> And I got the idea for the two-functions-make-a-tape by your comment from 11:34:02
22:23:31 <twice11> "i was pondering whether you could make a pair of functions simulate a brainfuck tape."
22:24:00 <twice11> I fell into the trap that i did not remember that ] does not
22:24:15 <twice11> decrement the register, so my first attempt for the reg-to-stack loop
22:24:42 <twice11> The second attempt showed that my 0x29A parser (a real hack)
22:25:01 <twice11> stops parsing after the first looped. After fixing, it worked.
22:25:36 <twice11> run "+%~k~+%~k~+%~k~ k%~[ss+~~%~-%~k~] k~"
22:26:00 <twice11> puts the number 3 into the register (first part), saves it into a function (second part)
22:26:07 <twice11> and executes it (third part).
22:26:40 <twice11> As output is destructive, I still have to develop a clone-value
22:27:08 <twice11> function (so of course a run function with itself as continuation function)
22:27:34 <twice11> But currently I think it should be possible using the s combinator somehow.
22:27:35 <oerjan> btw i suggest applying to i to execute the function.
22:28:04 <oerjan> because then i works also as the end of tape
22:28:46 <twice11> The function applied to execute gets omitted by the k-like combinators.
22:28:58 <twice11> I don't think it matters at all, which one I use.
22:29:12 <oerjan> it matters if you want the tape to expand automatically.
22:30:17 <oerjan> unless you manage to make the unlambda v combinator.
22:32:32 <oerjan> for the output value cloning it may be simpler to make the loop build two independent functions.
22:33:13 <twice11> You are right. Applying k to the end of tape puts k to the stack. Putting i there is better.
22:35:17 <oerjan> it actually doesn't matter that much.
22:35:38 <oerjan> applying to k just make you flip between k and (kk).
22:35:40 <twice11> Building two functions in the loop works.
22:36:43 <twice11> To build two functions, the loop looks like k%~k%~ [ss+~~%~%ss+~~%~ -%~k~]
22:42:39 <twice11> There is a catch: one should start the function (at least the later-executed one) with i
22:42:49 <twice11> to get completely rid of it with %~
22:50:01 <twice11> A working translation for bf "." is:
22:50:06 <twice11> sk~s~ sk~s~ [ss+~~%~%ss+~~%~ -%~k~] k~.%~ %~
22:54:38 <oerjan> i'm not sure that last %~ is quite right. Remember that . loses its second argument.
22:56:37 <twice11> Oops, there is a fault. The working (tested) version has
22:57:13 <twice11> (sk~s~)~.%~k~ ~ %~ past the loop
23:00:05 <oerjan> somehow i suspect it can be done shorter somehow with just k's than with sk~s~
23:02:42 <oerjan> note that a final drop can also be done with %k%~%~
23:06:23 <twice11> Yes. Independent of the start value. You are right.
23:10:07 -!- graue has quit ("Leaving").
23:12:43 -!- graue has joined.
23:15:31 -!- jix has quit ("Bitte waehlen Sie eine Beerdigungnachricht").
23:16:45 -!- SevenInchBread has joined.
23:17:45 <twice11> Except for ".", where I seem to have something messed up by simplification, my bf->0x29A seems to work now.
23:18:54 <twice11> I will put it to the pastebin when it's ready.
23:19:29 -!- graue has quit ("Leaving").
23:19:56 * SevenInchBread is looking at ways to encrypt information so that it can't be censored or subject to copyright law.
23:19:59 <oerjan> some links on the wiki would be nice too
23:20:27 <twice11> How permanent is the pastebin? Can I link to there?
23:25:11 <SimonRC> http://www.cs.duke.edu/~rodger/baking/cs.html
23:25:29 <SimonRC> Actually, I just got that from here, didn't I?
23:25:32 <xor> SimonRC: old
23:26:06 <xor> CompSci 4: Alice Programming Language"
23:26:14 <xor> "CompSci 6: Introduction to Java"
23:26:45 * xor screams about misuse of CS
23:28:22 <oerjan> twice11: you could submit it to one of the maintainers of the esolangs archive.
23:28:27 <SimonRC> they shouldn't be teaching languages
23:28:33 <SimonRC> They should be teaching paradigms
23:29:09 <twice11> I put the brainfuck -> 0x29A translation to the wiki. It's short.
23:29:38 <twice11> The 0x29A interpreter needs some polishing, it's worst WFM quality.
23:29:54 <twice11> I will put it to some webspace I own and link it from the wiki.
23:46:06 <twice11> The translation is on the wiki now.