00:12:07 -!- ShadowHntr has joined.
00:14:03 <oerjan> that seems a bit too strict. You need lazy evaluation for any conses to actually happen.
00:15:05 <oerjan> or you could do it in reverse:
00:16:41 <oerjan> ((Y (lambda (f) (lambda (l) (f (cons 'bitch l))))) '())
00:18:22 <oerjan> sequence_ $ repeat $ bitch
00:18:27 <bsmntbombdood> I don't think a Y combinator is even possible in scheme
00:18:57 <oerjan> yeah, that might need lazy evaluation too
00:20:36 <oerjan> ((lambda (f l) (f f l)) (lambda (f l) (f f (cons 'bitch l))) '())
00:21:10 <bsmntbombdood> ((lambda (x) (x x)) (lambda (f) (cons 'bitch (f f)))))
00:22:15 <oerjan> without lazy evaluation, you cannot apply (f f) without another intervening lambda.
00:22:58 <oerjan> it never bitches either
00:23:19 <oerjan> because it doesn't get to that part
00:23:54 <bsmntbombdood> ((lambda (f) (cons 'bitch (f f))) (lambda (f) (cons 'bitch (f f))))
00:23:56 -!- tgwizard has quit (Remote closed the connection).
00:24:25 <bsmntbombdood> (cons 'bitch ((lambda (f) (cons 'bitch (f f))) (lambda (f) (cons 'bitch (f f)))))
00:24:32 <oerjan> ok it evaluates 'bitch, perhaps. but it never conses.
00:25:36 <oerjan> ((lambda (x) (x x)) (lambda (f) (bitch) (f f)))
00:25:45 <oerjan> that should satisfy all camps :)
00:26:31 <oerjan> it's even tail recursive
00:28:31 <oerjan> in fact it has nothing _but_ side effects :)
00:30:35 <bsmntbombdood> ((lambda (x) (x x)) (lambda (f) (cons-stream 'bitch (f f)))))
00:32:26 <oerjan> bah, you got lazy and used a macro ;)
01:25:45 <oerjan> your comment made me think about how to remove all dummy variable names from that bitch recursion :)
01:26:38 <oerjan> on the downside, it requires an import Control.Monad.Fix
01:27:48 <oerjan> what kind of variables were you thinking of?
01:30:42 <oerjan> you mean unused variables?
01:31:40 <oerjan> in Haskell/ML, you use _ for those.
01:33:08 <oerjan> so it's actually basic lambda calculus abstraction you don't like? :)
01:33:50 <oerjan> there is also pointfree (pointless) style in Haskell
01:34:01 <oerjan> like my fix (bitch>>) above
01:34:57 <oerjan> and the whole Forth/Joy style of languages
02:50:08 -!- RodgerTheGreat has quit.
02:51:22 -!- RodgerTheGreat has joined.
03:34:51 -!- ShadowHntr has quit ("End of line.").
03:42:18 -!- RodgerTheGreat has quit.
03:51:24 -!- GreaseMonkey has joined.
04:08:31 -!- bsmntbombdood has quit (Read error: 54 (Connection reset by peer)).
04:21:36 -!- oerjan has quit ("Good night").
04:43:21 -!- bsmntbombdood has joined.
04:46:35 -!- bsmnt_bot has joined.
04:56:00 <bsmntbombdood> I read that the halting problem is solvable on machines that have finite memory
04:57:06 <bsmntbombdood> so the number of steps needed before a repition occurs is known
04:57:11 -!- Arrogant has joined.
05:00:45 <bsmntbombdood> if it doesn't halt after 2**(number of bits in memory), it doesn't halt at all
05:05:19 <GreaseMonkey> i reckon that turing machines should have more than one tape
05:20:36 <lament> bsmntbombdood: that would be true if "real computers" performed no IO of any kind.
05:21:58 -!- ShadowHntr has joined.
05:22:00 <lament> as it is, a simple +[,] stumps every oracle
05:35:03 <bsmntbombdood> The halting function is given the program and its input
05:51:29 <GreaseMonkey> sleep tight dood, even though there's bombs in your bsmnt
06:46:58 -!- NK` has quit (Read error: 54 (Connection reset by peer)).
06:50:19 -!- ShadowHntr has quit ("End of line.").
07:07:07 -!- Arrogant has quit (Read error: 104 (Connection reset by peer)).
07:59:59 -!- clog has quit (ended).
08:00:00 -!- clog has joined.
08:30:52 <EgoBot> help ps kill i eof flush show ls bf_txtgen usertrig daemon undaemon
08:30:54 <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
08:31:38 <lament> for guitar players: http://users.adelphia.net/~cygnusx_1/equal_temperament.html
08:52:06 -!- nazgjunk has joined.
09:03:44 <EgoBot> 1 ais523: daemon ul bf
09:03:46 <EgoBot> 2 ais523: daemon deadfish funge93
09:45:16 -!- GreaseMonkey has quit ("gnight").
10:18:19 -!- nazgjunk has quit (Read error: 104 (Connection reset by peer)).
10:18:46 -!- nazgjunk has joined.
10:23:36 -!- jix__ has joined.
10:26:16 -!- UpTheDownstair has joined.
10:35:42 -!- UpTheDownstair has quit (Connection reset by peer).
10:38:37 -!- nazgjunk has quit (Read error: 110 (Connection timed out)).
10:53:14 -!- nazgjunk has joined.
11:04:42 -!- nazgjunk has quit ("Leaving").
11:24:58 -!- jix__ has quit ("This computer has gone to sleep").
11:26:35 -!- nazgjunk has joined.
11:27:58 -!- UpTheDownstair has joined.
11:31:56 -!- UpTheDownstair has quit (Read error: 54 (Connection reset by peer)).
11:32:56 -!- nazgjunk has quit (Connection reset by peer).
11:43:11 -!- nazgjunk has joined.
12:32:08 -!- UpTheDownstair has joined.
12:32:22 -!- UpTheDownstair has quit (Client Quit).
12:39:09 -!- nazgjunk has quit (Read error: 145 (Connection timed out)).
12:41:13 -!- nazgjunk has joined.
13:02:52 -!- oerjan has joined.
13:17:30 -!- jix__ has joined.
13:55:46 -!- jix__ has quit ("This computer has gone to sleep").
14:08:58 -!- helios24 has quit (Read error: 60 (Operation timed out)).
14:09:14 -!- fizzie has quit (Read error: 60 (Operation timed out)).
14:11:33 -!- helios24 has joined.
14:13:30 -!- fizzie has joined.
14:41:09 -!- ais523 has joined.
14:41:36 <ais523> ~bf ,[.,]!Is this still working?
14:42:49 <ais523> ~exec self.bf3="def bfarg(x,y):\n p=y.group(2)\n a=y.group(3)+unichr(0)\n o=?\n p=p+'!'\n t=[0]*30000\n i=0\n l=0\n while p[i]!='!':\n if p[i]=='[' and t[l]==0:\n c=1\n while c>0:\n i=i+1\n if p[i]=='[': c=c+1\n if p[i]==']': c=c-1\n if p[i]==']' and t[l]!=0:\n c=1\n while c>0:\n i=i-1\n if p[i]==']': c=c+1\n if p[i]=='[': c=c-1\n"
14:43:03 <ais523> ~exec self.bf4=" if p[i]=='+': t[l]=t[l]+1\n if p[i]=='-': t[l]=t[l]-1\n if p[i]=='<': l=l-1\n if p[i]=='>': l=l+1\n if p[i]=='.': o=o+unichr(t[l])\n if p[i]==',':\n t[l]=ord(a[0])\n a=a[1:]\n i=i+1\nsys.stdout(o)\nself. register_raw(r'\S+ PRIVMSG (\S+) :~bf ([^!]*)!?(.*)',bfarg)"
14:43:06 <oerjan> bsmnt_bot needs a better persistence system.
14:43:10 <ais523> ~exec exec(self.bf3+self.bf4)
14:43:41 <ais523> damn, something must have gone wrong with my copy-paste
14:43:49 * oerjan gives up on SWI-prolog
14:43:56 <ais523> you program in Prolog?
14:44:13 <ais523> I've written a few simple Prolog programs somewhere
14:44:20 <ais523> never got to run them though, I don't have an interpreter
14:45:13 <ais523> ~exec self.bf3="def bfarg(x,y):\n p=y.group(2)\n a=y.group(3)+unichr(0)\n o=''\n p=p+'!'\n t=[0]*30000\n i=0\n l=0\n while p[i]!='!':\n if p[i]=='[' and t[l]==0:\n c=1\n while c>0:\n i=i+1\n if p[i]=='[': c=c+1\n if p[i]==']': c=c-1\n if p[i]==']' and t[l]!=0:\n c=1\n while c>0:\n i=i-1\n if p[i]==']': c=c+1\n if p[i]=='[': c=c-1\n"
14:45:14 <ais523> 06:45:54 <ais523> ~exec self.bf4=" if p[i]=='+': t[l]=t[l]+1\n if p[i]=='-': t[l]=t[l]-1\n if p[i]=='<': l=l-1\n if p[i]=='>': l=l+1\n if p[i]=='.': o=o+unichr(t[l])\n if p[i]==',':\n t[l]=ord(a[0])\n a=a[1:]\n i=i+1\n sys.stdout(o)\nself.register_raw(r'\S+ PRIVMSG (\S+) :~bf ([^!]*)!?(.*)',bfarg)"
14:45:40 <ais523> ~exec self.bf3="def bfarg(x,y):\n p=y.group(2)\n a=y.group(3)+unichr(0)\n o=''\n p=p+'!'\n t=[0]*30000\n i=0\n l=0\n while p[i]!='!':\n if p[i]=='[' and t[l]==0:\n c=1\n while c>0:\n i=i+1\n if p[i]=='[': c=c+1\n if p[i]==']': c=c-1\n if p[i]==']' and t[l]!=0:\n c=1\n while c>0:\n i=i-1\n if p[i]==']': c=c+1\n if p[i]=='[': c=c-1\n"
14:45:51 <ais523> ~exec self.bf4=" if p[i]=='+': t[l]=t[l]+1\n if p[i]=='-': t[l]=t[l]-1\n if p[i]=='<': l=l-1\n if p[i]=='>': l=l+1\n if p[i]=='.': o=o+unichr(t[l])\n if p[i]==',':\n t[l]=ord(a[0])\n a=a[1:]\n i=i+1\n sys.stdout(o)\nself.register_raw(r'\S+ PRIVMSG (\S+) :~bf ([^!]*)!?(.*)',bfarg)"
14:45:57 <ais523> ~exec exec(self.bf3+self.bf4)
14:46:10 <ais523> ~bf ,[.,]!Hopefully this works now.
14:46:12 <oerjan> i thought SWI prolog should be so simple. But i have now spend more time than i want to try and make it work properly with gvim as external editor.
14:46:42 <ais523> is it the language that's the problem, or the development environment
14:47:29 <oerjan> the environment. i end up being infuriated by a bug, and then even more because their bug tracking system wants me to log in and _they_ select my password.
14:48:00 <ais523> I tried to write my own Prolog interpreter once, but that was when all my programs were in VBA for Excel
14:48:25 <ais523> nowadays I mostly use C, unless I'm using an esolang (often a better choice!) or am forced to use Java
14:48:31 <oerjan> well it is possible in theory :)
14:49:27 <ais523> !ul (Is this still working too?)S
14:49:28 <EgoBot> Is this still working too?
14:49:50 <oerjan> EgoBot does have some useful persistence.
14:50:15 <ais523> the thing that's surprising me is that the daemon hasn't crashed yet, considering it's written in BF and has no error checking
14:50:27 <ais523> and that people keep insisting on feeding it illegal programs
14:50:56 <ais523> the persistence of the deadfish daemon is less surprising
14:53:21 <ais523> !daemon bct bf http://www.bf-hacks.org/hacks/bct.b
14:55:16 <ais523> uh oh, maybe I shuldn't feed it programs without checking what they do first
14:55:50 <EgoBot> 1 ais523: daemon ul bf
14:55:52 <EgoBot> 2 ais523: daemon deadfish funge93
14:55:53 <oerjan> it would be nice if bsmntbombdood would make at least one directory writable. Then we could place nice scripts there.
14:56:18 <ais523> the process must have ended naturally before I could kill it
14:56:34 <ais523> but yes, oerjan, I agree that a persistent-daemon directory would be nice
14:56:43 <ais523> so we could store interpreters in it
14:57:33 <ais523> I've found myself rather wanting a Thutu interpreter here so I could write esolangs in it. BCT is easy:
14:58:52 <bsmnt_bot> NameError: name 'list_dir' is not defined
15:00:42 <ais523> no, BCT is less easy through an IRC client when you can't think sensibly about what you're doing
15:01:44 <ais523> hey, self-modifying BCT looks interesting
15:02:27 <ais523> 0 deletes at the left, 1x inserts at the right, and the instruction pointer cycles along the program
15:02:35 <oerjan> ~exec sys.stdout(os.listdir("/"))
15:02:35 <bsmnt_bot> ['bin', 'bot', 'etc', 'lib', 'usr']
15:02:46 <oerjan> ~exec sys.stdout(os.listdir("/bot"))
15:02:46 <bsmnt_bot> ['betterbot.py', 'test.pickle', 'foo.py~', 'ski_repl.py', 'foo.py', 'ircbot.py~', 'start.sh', 'better.sh', 'ircbot.py']
15:03:31 <oerjan> ~exec sys.stdout(os.listdir("/lib"))
15:03:31 <bsmnt_bot> ['libm.so.6', 'libreadline.so.5', 'libacl.so.1', 'libdl-2.4.so', 'libresolv.so.2', 'libutil.so.1', 'libncurses.so.5', 'libattr.so.1', 'libcrypt.so.1', 'ld-linux.so.2', 'libdl.so.2', 'libpthread.so.0', 'libpam_misc.so.0', 'libpam.so.0', 'libc.so.6', 'librt.so.1']
15:04:46 <oerjan> might be too simple to be turing complete
15:05:04 <ais523> it's not obviously not TC
15:05:25 <oerjan> let's see. Any 00 will force synchronization
15:06:45 <oerjan> wait, exactly how do you mean
15:06:59 <ais523> there's a description on the page linked from the wiki
15:07:27 <ais523> the instruction pointer takes the command after the current one, looping back to the start when it reaches the end
15:07:44 <ais523> and the commands operate on the program itself. Apart from that, it's just BCT
15:08:12 <ais523> (The 'start' is the first non-deleted command. So the logic of self-modifying BCT is more like Muriel than a tag system.)
15:08:18 -!- UpTheDownstair has joined.
15:08:51 <ais523> The problem seems to be that the number of 0s has to be kept quite low, or they'll end up demolishing the program
15:08:58 <ais523> but obviously you can't have nothing but 1s
15:10:34 <oerjan> So essentially you have a cycle with two pointers in it, one data and one instruction
15:11:30 <ais523> that's it. And they both increase and cycle through. Wow, it's like a cross between tag systems, Muriel, and Malbolge
15:11:44 <ais523> (more like Dis, actually, as there isn't encryption confusing the issue too)
15:11:56 <oerjan> the example seems buggy from step 4 to 5
15:12:07 -!- UpTheDownstair has quit (Read error: 104 (Connection reset by peer)).
15:12:36 <ais523> I agree, there should be an extra 1 at the end
15:13:14 <oerjan> hm, what happens if the modified data is inside the current instruction?
15:13:15 -!- UpTheDownstair has joined.
15:13:51 <ais523> I'm not sure if that can happen. A 0 can delete itself, but then you just go onto the next instruction, and a command can't add inside itself
15:14:25 <oerjan> why not? There could be 0...*1
15:14:50 <ais523> in that case, presumably you go on to the command after the 0 at the start, with an extra 0 at the end
15:15:33 <oerjan> and then what about 0...*0
15:15:52 <oerjan> ok it's obvious what it should do
15:17:07 <oerjan> there is a problem with the obvious linked list implementation though
15:17:59 <oerjan> if you are not careful, you will end up with the instruction pointer at a deleted node.
15:18:26 <oerjan> no matter which order you choose for the operations
15:18:26 <ais523> I'm writing it in Thutu at the moment, which has problems of its own
15:18:44 <ais523> (Unfortunately, Thutu is 'the obvious implementation' for just about everything for me at the moment)
15:26:09 -!- nazgjunk has quit (Read error: 110 (Connection timed out)).
15:44:21 <oerjan> with ...1x, does execution continue before or after the added x?
15:44:42 <ais523> I've just written an interpreter, so I'll check
15:45:09 <ais523> before the way I've written it
15:45:33 <ais523> http://pastebin.ca/raw/397461
15:48:59 <ais523> from my experiments so far, it seems that if the program contains any 0s the density of 0s increases until they end up swamping the program
15:54:50 <ais523> If 1s and 0s are distributed randomly, with a proportion p of 0s, then there's a chance p(1-p) of deleting a 1, a chance p^2 of deleting a 0, a chance (1-p)^2 of adding a 1, a chance p(1-p) of adding a 0
15:55:54 -!- RodgerTheGreat has joined.
15:56:22 <oerjan> from that description one would expect the proportion to stay constant.
15:56:25 <ais523> hello, RogerTheGreat! We were discussing self-modifying Bitwise Cyclic Tag
15:56:37 <ais523> I know, there's something slightly stranger going on
15:57:43 <ais523> starting with 1111111110, the number of 0s grows gradually, with the 0s getting clumpier and clumpier, until the whole thing collapses
15:59:19 <ais523> aha! Consider the number of 1s between consecutive 0s
15:59:40 <ais523> if it's odd, then it adds a string half that length to the end of the input
15:59:54 <ais523> if it's even, it ends up combining with the next string
16:00:21 <ais523> so if there's even one odd string, all the strings before it in the program will combine to it
16:00:58 <ais523> no, wait; my argument doesn't work due to the 0s changing the length of the initial string
16:01:25 <ais523> but the point is that newly-generated strings of 1s tend to be shorter than the strings of 1s that generated them
16:01:45 <ais523> so the 1s-in-a-row count tends to decrease, which is what causes the programs to tend to terminate
16:02:39 <RodgerTheGreat> does this imply that a bitwise cyclic tag system must halt?
16:02:59 <ais523> no, BCT is turing-complete. It's self-modifying BCT that I was talking about
16:09:33 -!- nazgjunk has joined.
16:09:59 -!- UpTheDownstair has quit (Read error: 104 (Connection reset by peer)).
16:14:47 <RodgerTheGreat> alright, I think I have a better handle on the topic now
16:15:10 <RodgerTheGreat> hm... I wonder what I should write an implementation in?
16:21:18 <RodgerTheGreat> standard BCT could probably be expressed very concisely in BASIC using strings, with the minor caveat that most BASIC interpreters have arbitrary string length limitations
16:21:32 <RodgerTheGreat> it's hard to dynamically allocate storage in BASIC. <:|
16:22:21 <ais523> there was a pragma in the version of BASIC I used that allowed for dynamic arrays, and it had a REDIM command to resize them
16:24:57 <ais523> QBASIC, if I remember. It was bundled with some versions of DOS
16:25:17 <oerjan> Perl should be fairly compact, even more so if you write it directly rather than compile to it ;)
16:25:36 <RodgerTheGreat> I've used it quite a bit, although I was never aware of REDIM
16:25:46 <ais523> oerjan: more readable too without the compilation, and also more efficient
16:26:04 <RodgerTheGreat> I'd say my favorite BASIC implementations are DarkBASIC and Cbaspad for PalmOS
16:28:40 -!- nazgjunk has quit (Success).
16:29:11 <RodgerTheGreat> Calamari's opus is truly an achievement, but it isn't particularly handy when I find myself without a Java runtime environment
16:30:37 <RodgerTheGreat> and believe me, Cbaspad is an esoteric language in it's own right. It's the only BASIC interpreter I've found for palmOS that offers peek() poke and call(), making inline ASM possible
16:30:59 <RodgerTheGreat> not to mention a number of additional low-level hardware access and I/O functions
16:31:40 <ais523> that was possible in QBASIC too IIRC. It had a CALL ABSOLUTE that would jump to a particular location in memory, and you could find where in memory a variable was stored
16:32:52 <RodgerTheGreat> yes, it's a standard feature on most BASIC implementations from the '80s and earlier
16:33:35 -!- nazgjunk has joined.
16:34:44 -!- jix__ has joined.
16:36:35 -!- jix__ has changed nick to jix.
16:38:01 -!- UpTheDownstair has joined.
16:40:30 <jix> hello RodgerTheGreat
16:41:08 <ais523> ~bf ,[.,]!Hello everyone
16:46:08 -!- nazgjunk has quit (Connection reset by peer).
16:52:12 -!- UpTheDownstair has quit (Connection reset by peer).
16:57:49 -!- nazgjunk has joined.
16:58:27 -!- ShadowHntr has joined.
17:00:19 * ais523 has just written a Dupdog interpreter
17:01:10 <ais523> http://pastebin.ca/raw/397555
17:01:39 <ais523> I don't have any Dupdog programs to test it on, though
17:06:04 <RodgerTheGreat> wow. I can see the essential features necessary for computation, but that would be tricky as hell to program with.
17:06:35 <ais523> I can't even figure out "Hello, world!".
17:06:45 -!- oerjan has quit ("My brain is toast").
17:06:46 <RodgerTheGreat> unfortunately, I don't see any way to do input, so I don't think cat is possible either. :S
17:07:38 <RodgerTheGreat> ~ and ! provide a facility for looping, and Mfit's ? seems to allow for branching
17:08:49 <ais523> no, it doesn't, so the language can't be TC. The problem is that the only way to increase the program's length is by doubling it, so a nonterminating program is always odd for Mfit and even for Shanty
17:09:03 <ais523> no, I'm wrong: Mfit can double it too
17:09:15 <RodgerTheGreat> it would be a lot easier if instructions for each interpreter could act as NOPs for the other...
17:09:34 <ais523> ...or if there were any NOPs at all
17:09:53 <RodgerTheGreat> as it stands, it seems like it'd be very difficult to manipulate program length enough to generate useful output
17:10:47 <RodgerTheGreat> is the program length mod 255ed before it's converted to ASCII?
17:11:00 <ais523> if the program length is odd for Mfit, then ??...?? is a NOP
17:11:10 <ais523> RogerTheGreat: I don't know. It isn't with my interpreter
17:11:27 <ais523> (I just pass the length to chr() and see what happens.)
17:11:35 <ais523> You get something like this:
17:11:53 <ais523> ~bf +++++++++++++++++[->+++++++++++++++++<]>.
17:11:54 -!- bsmnt_bot has quit (Remote closed the connection).
17:12:30 <ais523> wait, why did the bot just crash when I did that? Outputting 17*17 can't be that hard, surely?
17:12:46 <RodgerTheGreat> it might be easier to grow the program to fit into a character you needed by modding than to reduce it *and* increase it to generate strings
17:13:12 <ais523> would get round the problem of output being impossible in sufficiently complex programs too
17:13:30 <RodgerTheGreat> although, if we have a NOP, we can arbitrarily shorten the program whenever we want to
17:13:49 <RodgerTheGreat> perhaps both of these techniques can be combined to achieve output
17:14:20 <ais523> A sufficiently complex program needs a sufficiently large number of characters to represent it
17:14:46 <ais523> and so can't do output except right at the end, and even then only a limited amount of output
17:15:03 <ais523> so the language isn't BF-complete or even Underload-complete, at least
17:15:19 <ais523> but it might still be Turing-complete, because that doesn't depend on I/O
17:15:34 <RodgerTheGreat> thus, I would suspect that modding of program length is the intent
17:15:59 <RodgerTheGreat> "...Because dupdog is only capable of storing a single value (the source code itself) in memory at a time, which may correspond to a finite set of 256 states..."
17:16:14 <RodgerTheGreat> that implies that a program must have <= 255 characters.
17:16:30 <ais523> I think that line at the bottom is probably wrong
17:17:01 <ais523> let's deal without the arbitrary limit, and argue that as ASCII is a 7-bit code, it repeats every 128 characters. Then at least we might be able to get somewhere
17:18:08 * ais523 updates their interpreter accordingly
17:18:08 <RodgerTheGreat> and if we allow for modding, the program length can be any number- an infinite state automaton. I'm fairly certain that one-register turing machines exist, so turing completeness *may* be possible
17:21:11 <RodgerTheGreat> alright, so we know that we can halt at any time by having a character other than ! or ? at an odd space in the initial source code.
17:21:12 <ais523> updated interpreter: http://pastebin.ca/raw/397577
17:21:26 <ais523> yes, we even get a nice error number as output
17:21:50 <RodgerTheGreat> I think it's acceptable to generate some junk output as a consequence of halting
17:22:12 <RodgerTheGreat> it's probably easier than making a program that ends by eating itself completely
17:22:38 <RodgerTheGreat> I don't even think that's possible without generating more output
17:22:39 <ais523> in theory the program could be reversed, and maybe a bit of duplication, so a non-command character won't necessarily halt wherever you put it
17:22:58 <ais523> ???????? ends without output
17:23:04 <ais523> (it's two nested NOPs)
17:23:22 <RodgerTheGreat> I was forgetting the consequences of reversing the source...
17:23:41 <ais523> and ~ might not end, because it might not be a ~ by the time you reach it
17:24:29 <RodgerTheGreat> I get the sense that this will probably require a bit of malbolge-esque code buffering to ensure commands do what you expect them to
17:26:22 <ais523> unfortunately, 128 is divisible by 4, so some duplication's needed to print characters with both odd and even ASCII codes
17:27:08 <RodgerTheGreat> wrapping a code-reverse in an Mfit ? seems like a way to do some primitive branching, but it's necessary to make sure that you don't leave any ~'s for Shanty to encounter...
17:27:21 <ais523> at least, no time soon
17:27:31 <RodgerTheGreat> I guess that would allow for a conditional halt, at least
17:28:00 <ais523> One of the more fundamental parts of the program state is whether Mfit or Shanty is seeing the even-length programs
17:28:28 <ais523> In fact, it sort of seems more sensible to consider two-character commands than one-character commands
17:29:11 <RodgerTheGreat> we can look at it this way- the two ways we can manipulate the program size, "s" are to subtract one or to multiply s by two
17:29:37 <RodgerTheGreat> every time we muliply s by two, we are assured it is even
17:29:57 <RodgerTheGreat> if the program is even for mfit, it will be odd for shanty
17:30:05 <ais523> Yes. To think about it another way, the program+interpreter parity stays the same unless the odd-length interpreter duplicates
17:30:58 <RodgerTheGreat> although, I was wrong- we can only either do s-1 or (s*2)-1
17:30:58 <ais523> Another point: we have to duplicate or reverse the program _every time_ Shanty executes, which is every other command
17:31:31 <ais523> no, ~abc changes to abcabc (see the wiki Talk page)
17:33:07 <ais523> It's going to be easiest if we just let duplication roam free up to infinity. After all, it doesn't change either end of the program unless the program is very short; it only changes the length
17:34:21 <RodgerTheGreat> if we use both "ends" of the program to store our useful code, they will be preserved through duplication.
17:34:39 <ais523> I agree that the ends are what matters
17:34:59 <RodgerTheGreat> so, we can use them as two "branches" that we'll probably need to interleave code between, using reverses as a compact way to NOP
17:35:29 <ais523> reverse and duplicate are both NOPs in a way
17:35:37 <ais523> they just have different effects on the program length
17:36:08 <ais523> (Now I'm beginning to see why the language might not be TC; data storage is going to have to be /very/ non-localised)
17:36:49 -!- tgwizard has joined.
17:37:59 <RodgerTheGreat> if we design a program that doesn't fit evenly into 128 or 255, it should be a relatively simple matter of duplicating a specific number of times to get to each desired character, followed by an Mfit non-coding character
17:38:31 <RodgerTheGreat> the problem of data being dependent on final program length is a tough one
17:38:44 <ais523> yep. The parity isn't trivial to deal with, but it's workable-around
17:39:21 <RodgerTheGreat> *or* we can just assume it's bigger than we need it to be and pad the center with a bunch of noncoding characters to make it the right sie
17:40:07 <RodgerTheGreat> an optimal solution is hard, but an extremely nonoptimal one is much easier
17:40:49 <RodgerTheGreat> since there doesn't seem to be a lot of sourcecode handy, doing it at all seems like enough of an accomplishment
17:40:56 -!- jix has quit ("This computer has gone to sleep").
17:42:57 <RodgerTheGreat> so... what's an easy way to find the number of duplications we'll need to get each modulus value?
17:43:46 <ais523> come to think of it, it's easiest just to get a bit higher than needed and NOP your way down
17:44:32 <RodgerTheGreat> there are two kinds of NOPs- nops the interpreters skip over and nops that are never encountered at all
17:44:50 <RodgerTheGreat> we can use anything as that second kind, and keep them in the creamy nougat center of our program
17:45:54 <ais523> even better, adding 128 junk characters to the middle of the program has no visible effect on anything, until we reach them
17:46:18 <RodgerTheGreat> use mfit's duplicate to make duplicates and either reverse (code continues from the opposite end, nop) or duplicate with shanty
17:46:42 <ais523> you need the right interpreter to cause a duplicate according to whether the output character is odd or even
17:46:58 <RodgerTheGreat> so the hello world will look like "codecodecodeJUNKJUNKedocedocedoc"
17:47:07 <ais523> If you're not doing loops, it's actually not too hard to output arbitrary text, just generate the program from the outside in
17:47:37 <ais523> and all you need to code is the transition from one character to the next
17:47:59 <RodgerTheGreat> and at the end, we can encounter the junk as shanty to terminate
17:48:38 <ais523> In fact, ~!~!~!~ multiplies the source length by 128, so if we don't care about being optimal we can just generate code for each character.
17:49:01 <ais523> We can even use Mfit's ? as a NOP whether the program length is odd or even; just take it into account in all future code
17:49:33 <ais523> OTOH, a 99 bottles of beer program shorter than the song itself would be difficult and/or impossible
17:49:41 <RodgerTheGreat> so we just need to estimate an upper limit to the number of instructions we need to use for initial program length purposes, determine the actual number of flips and dups, generate the code and add padding as necessary
17:50:22 <RodgerTheGreat> largely because storing strings seperately from counter data is effectively impossible
17:50:52 <ais523> I'd go further and say storing counter data is incredibly difficult regardless of whether you have strings or not
17:50:58 <lament> 3.141592653589793238462643383279.........
17:50:59 <RodgerTheGreat> like storing it implicitly in the nesting of duplicates of something equally painful
17:51:58 <ais523> The problem is that we only have effectively 6 states to play with: reversed or not * three possible permulations of ?!~
17:52:30 <RodgerTheGreat> I think ultimately your idea of Mfit ? NOPs could lead to a more compact solution, but would drastically increase the complexity of the program
17:52:52 <ais523> the problem is that duplicating, reversing, and permuting are all independent of each other
17:53:17 <ais523> so the only way you can store data in the program is the /amount of the program/ that was still there last time you duplicated
17:54:26 <RodgerTheGreat> oh, jesus- I hadn't thought of that. This makes determining the number of flips and dups to arrive at a value is entirely dependent on the sequence of instructions that came before...
17:54:57 <RodgerTheGreat> you'd have to build it an instruction at a time to get working right, I think.
17:55:54 <ais523> no. But I think I know how I can write a Hello World-program-generating-program now
17:55:59 <RodgerTheGreat> It might be best to write a program to generate this program, to reduce the potential for error
17:56:08 <ais523> (i.e. a program in another language that generates Hello World in Dupdog)
17:56:59 -!- ShadowHntr has quit ("End of line.").
17:58:19 * ais523 sets out to try to write the program
18:04:08 <RodgerTheGreat> there's nothing like the thrill of groundbreaking esolang coding
18:07:55 -!- sebbu has joined.
18:09:34 <RodgerTheGreat> ais523 and I have been figuring out how to do something vaguely useful in dupdog (http://www.esolangs.org/wiki/Dupdog)
18:10:15 -!- nazgjunk has quit (Read error: 104 (Connection reset by peer)).
18:10:22 <RodgerTheGreat> we have a rough method that should create the first hello world in the language
18:16:45 -!- nazgjunk has joined.
18:38:59 <ais523> grr, it isn't working at the moment
18:41:27 <RodgerTheGreat> and I have a theory that the resulting program is going to be fucking *huge*
18:41:52 <ais523> you have to work from the inside and outside simultaneously
18:42:28 <RodgerTheGreat> and getting the right value means hopping around a lot- rather like doing hello world in BF without -
18:45:05 <RodgerTheGreat> average case, I estimate it should take something around 128 instructions to get a value from 0-255 as output. The number of hops could be much greater if your program doesn't try to get an optimal solution
18:46:18 <RodgerTheGreat> and all the interdependencies for size make things really tricky
18:50:29 <RodgerTheGreat> Do you think that genetic algorithms might be a good approach for this sort of thing? It worked for malbolge
18:50:50 <ais523> no idea. I think that working it out deterministically will probably work better, though
18:51:59 <RodgerTheGreat> I was just thinking that since we have a rough idea of how we want the program to "look", we could start the GA software with something pretty close to a correct answer, meaning reasonably rapid results
18:52:15 <ais523> I'll give up for the time being; I just realised why the method I was using wouldn't work. I still think it's possible to do it deterministically, though
18:52:29 <RodgerTheGreat> doing things deterministically will probably reap more benefits in terms of future work with the language
18:53:07 <ais523> The problem's that you want to end up with a program to print 'ello, World!' after printing the H
18:53:31 <ais523> but that you can't design the program to do that until you know what the H code is like, as it'll have to have a specific structure
18:53:52 <ais523> and you can't design the H code until you know what code you're aiming for...
18:54:36 <ais523> wait, most Dupdog programs don't care if they're duplicated, as long as they end up with the right length
18:57:18 <RodgerTheGreat> that is correct- perhaps design each character's code segment to reset the code size to a multiple of some predictable value?
18:57:31 <RodgerTheGreat> it adds more padding, but then you can build pieces independently
18:57:34 <ais523> that's it, ~!~!~!~ resets the code size to a multiple of 128
18:57:46 <ais523> lament: output's done when Mfit encounters an unrecognized character
18:57:57 <ais523> it outputs a character depending on the length of the program
18:58:01 <RodgerTheGreat> lament: the esolang page is here: http://www.esolangs.org/wiki/Dupdog
18:59:36 <RodgerTheGreat> we chose to interpret the spec as saying that we take the program length modulo 128/256 to determine the printed char, so all we care about is that modulus
18:59:57 <RodgerTheGreat> thus, you can have a program of any size and still be capable of output
19:01:02 <lament> it's in the Implemented category
19:01:24 <lament> is there a ref. implementation?
19:01:31 <ais523> I wrote an implementation just now; however, the category was there before I wrote it.
19:01:55 <ais523> Of course, we'll need a new optimizing implementation to have any chance of fitting Hello, World! into memory the way I plan to write it
19:02:56 <RodgerTheGreat> and if our interpretation of the spec leads to the first "useful" program, I imagine it will become canonical for exactly that reason
19:03:27 -!- nazgjunk has quit (Read error: 54 (Connection reset by peer)).
19:04:49 -!- nazgjunk has joined.
19:04:49 <ais523> damn, my latest idea doesn't work either; ~!~!~!~ resets the code size to something that isn't a multiple of 128 because those characters are disappearing all the time
19:05:31 <ais523> it does have a fixed value modulo 128, though
19:06:02 <RodgerTheGreat> well, any reset value works as long as it's the same modulo 128 every time
19:06:29 <ais523> If we only want to print characters with odd ASCII codes, we can just write a really long sequence of ??...?? NOPS and change appropriate characters to output characters
19:07:36 <ais523> something similar can be done with even ASCII codes
19:08:15 <ais523> Actually... the best way to think about a half-finished Dupdog program is as a sequence of commands at the start, commands at the end, and a /length/ for the whole thing
19:08:22 <ais523> then it might be possible to do it outside-in
19:08:43 <lament> the specification is pretty bad
19:09:06 <lament> it's not clear whether the current command is counted as part of the source
19:09:15 <RodgerTheGreat> lament: a few things are vague, but it's understandable. The talk page helps
19:09:26 <ais523> no for duplicate/reverse, yes for length measurement, as far as I can tell
19:13:12 <RodgerTheGreat> lament: we're pretty sure the "computational class" description is incorrect, although we're not certain it's turing-complete
19:13:46 <RodgerTheGreat> we haven't really proven anything yet with regards to arbitrary branching (or an analogue), and data storage is a bitch
19:25:22 <lament> (was he on crack when he came up with this?)
19:26:00 <ais523> If I remember correctly, they were messing around with the bots.
19:26:06 <ais523> Someone did something like this:
19:26:08 <RodgerTheGreat> I would be fascinated to know the meaning of "mfit" and "shanty"
19:26:31 <ais523> !daemon dog bf >,[>,]<[.<]
19:26:59 <ais523> !daemon dup bf >,[>,]<[<]>[.>]<[<]>[.>]
19:27:33 <ais523> 'cept my coding hasn't worked
19:27:41 <EgoBot> 1 ais523: daemon ul bf
19:27:41 <EgoBot> 2 ais523: daemon deadfish funge93
19:27:41 <EgoBot> 3 ais523: daemon dog bf
19:27:43 <EgoBot> 4 ais523: daemon dup bf
19:28:03 <ais523> EgoBot is 10=newline, isn't it?
19:28:26 <lament> so after the source code is duplicated, for the next instruction the length of source code is always EVEN?
19:29:02 <RodgerTheGreat> it might be worthwhile to skim the logs from earlier today
19:29:13 <ais523> !daemon dog bf +[->,----------[>,-----------]<[+++++++++++.[-]<]+]
19:29:50 <ais523> !daemon dog bf +[->,----------[>,-----------]<[+++++++++++.[-]<]++++++++++.[-]+]
19:30:12 <ais523> Now what have I done wrong?
19:31:16 <ais523> bsmntbombdood: bsmnt_bot didn't come back online after last time I tried to give it a BF program
19:31:25 <ais523> (and it wasn't even an infinite loop)
19:38:57 <ais523> !daemon dog befunge 0>~# :# 5# 5# +# -# _> .# _,$
19:39:09 <EgoBot> help ps kill i eof flush show ls bf_txtgen usertrig daemon undaemon
19:39:12 <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
19:39:19 <ais523> !daemon dog funge93 0>~# :# 5# 5# +# -# _> .# _,$
19:39:20 <lament> all i can see so far is that dupdog really likes printing the fourth character.
19:39:51 <EgoBot> 10 100 114 119 44 108 101 0
19:40:20 <ais523> !daemon dog funge93 0>~# :# 5# 5# +# -# _> ,# _,$
19:41:48 <ais523> !daemon dog funge93 0>~# :# 5# 5# +# -# _$> :# ,# _,$55+,
19:42:49 <ais523> !dog .won gnikrow eb ot smees tI
19:42:51 <EgoBot> It seems to be working now.
19:43:17 <ais523> One-line Befunge has a logic very like REVERSE.
19:44:13 <ais523> except that in Befunge, loops always return true to the left, and in REVERSE it depends on the direction you're going in.
19:49:35 -!- nazgjunk has quit (Read error: 54 (Connection reset by peer)).
19:50:00 -!- nazgjunk has joined.
19:50:05 <RodgerTheGreat> it seems like just using mfit to do duplications and relying on shanty to make up most of your code logic is a more predictable way to code
19:50:46 <ais523> then we'll need a new interpreter that can handle the colossally large progam that will result
19:51:14 <ais523> Maybe one that stores the program compressed? (It's going to consist of lots of repeated stuff.)
19:52:06 <ais523> not exactly, because we need to store near-repetitions and repetitions of groups of more than one character
19:52:21 <ais523> It would probably also need a way to store nested repetitions
19:53:03 <ais523> You could store it as a stack of pointers into the original program and into itself
19:59:52 -!- ais523 has quit ("Sorry I couldn't get that Dupdog Hello, World! to work").
20:29:07 -!- sebbu2 has joined.
20:35:35 <GregorR> http://i15.photobucket.com/albums/a379/GregorRichards/lcarssshot.png
20:41:06 <GregorR> It's awesome for a tablet PC :)
20:41:38 <GregorR> The new tablet PC I'm getting in a week or so allows you to use your finger for input instead of just the pen.
20:41:52 <RodgerTheGreat> I've wanted one for quite a while, but I keep hoping that apple will make one
20:41:54 <GregorR> And even though LCARS isn't real, it's definitely very finger-clickable ;)
20:44:06 <RodgerTheGreat> this may be the next best thing, though: http://axiotron.com/
20:45:30 <RodgerTheGreat> but OSX has built in keyboard emulation and pretty spiffy handwriting recognition, so no huge biggie
20:46:05 <GregorR> I wouldn't give up the keyboard ... programming with handwriting recognition and/or onscreen keyboard == basically impossible.
20:46:10 <RodgerTheGreat> I probably wouldn't use one of these for writing school papers or coding anyway- I'd be too busy doodling
20:46:26 <GregorR> See, I have a tablet PC as my general-purpose laptop.
20:46:33 <GregorR> So I can't sacrifice the keyboard.
20:47:14 <RodgerTheGreat> well, I'll bet when Apple finally gets off their asses and makes a proper tablet they'll have a good solution to the problem
20:47:51 -!- sebbu has quit (Success).
20:47:58 <GregorR> Yeah ... like a rotating screen :P
20:49:11 <RodgerTheGreat> I'm not a huge fan of the iPhone... mainly because I don't like cellphones and I dislike phone bills even more. If it had been designed as more of a PDA, I'd probably already have one
20:49:58 -!- jix__ has joined.
20:49:59 <RodgerTheGreat> fortunately, the iPod seems to be slowly aiming in that direction, so I may see my dream device in a couple of years
20:52:44 <RodgerTheGreat> if Apple just released an iPod SDK to take advantage of what the "games" feature opened up, we wouldn't need things like Rockbox or iPodLinux, and a lot of people would be happy
20:53:16 <RodgerTheGreat> I can't really say "everybody's happy", because bleeding-heart open-sourcers and the linux crowd are rarely if ever happy.
21:02:05 -!- jix__ has quit ("This computer has gone to sleep").
21:03:34 <GregorR> I hate Apple because of their interaction with the F/OSS community, not because they write proprietary software.
21:04:27 <GregorR> Their interaction with the F/OSS community has been incredibly dishonest and immoral, carefully crafted to make naive people think they're a F/OSS-supporting company.
21:05:00 <GregorR> At least Microsoft doesn't /pretend/ to support F/OSS.
21:06:00 <RodgerTheGreat> it has a lot to do with the underlying differences between the BSD license and the GPL
21:06:38 -!- jix__ has joined.
21:07:24 <GregorR> No, it doesn't. Everything GPL that they use, they do /precisely/ what they're legally required to do, no more. BSD software they mix with proprietary software to create non-F/OSS software. The original chunk of BSD-licensed code they use, they do usually continue to distribute, but they have no qualms with making it worthless in isolation.
21:08:11 <GregorR> Mind you, I'm not saying they've done anything /illegal/, as they haven't. Just unethical.
21:10:57 -!- jix__ has quit (Client Quit).
21:13:11 -!- jix__ has joined.
21:20:10 <lament> i'm beginning to suspect a 'hello world' might be impossible
21:22:32 -!- sebbu2 has quit ("reboot").
21:25:39 <lament> i have no proof though...
21:26:27 -!- Sgeo has joined.
21:26:56 <lament> RodgerTheGreat: you there?
21:27:09 <lament> RodgerTheGreat: http://www.esolangs.org/w/index.php?title=Dupdog&diff=6607&oldid=6606
21:27:21 <lament> at some point he put an implementation in
21:28:16 <lament> note how he apparently wraps by 257
21:28:31 <lament> that might be just a typo of course
21:29:04 <lament> if it's not a typo, it changes everything :D
21:29:21 <lament> probably a typo, though
21:29:33 <lament> no need to raise our hopes too high
21:30:27 <RodgerTheGreat> well, it *could* be intentional- this is #Esoteric, after all
21:30:27 -!- UpTheDownstair has joined.
21:30:45 <RodgerTheGreat> fortunately, it doesn't break our general solution to the problem, just the details of how it works
21:31:06 <lament> as far as i'm concerned, it would make things a lot easier
21:31:47 -!- nazgjunk has quit (Read error: 104 (Connection reset by peer)).
21:32:14 -!- UpTheDownstair has changed nick to nazgjunk.
21:32:54 <RodgerTheGreat> aside from confirming the theory that we do in fact wrap...
21:33:55 -!- sebbu has joined.
21:42:51 -!- oerjan has joined.
21:45:18 <lament> i have written hello world for the case where we wrap on 257
21:45:59 <lament> it's 2386 characters long.
21:46:31 <lament> the case where we wrap on 256 is much much harder.
21:46:42 <lament> i still think it's just a typo
21:47:26 <lament> need to ask cakeprophet...
21:49:07 <lament> the problem with 256 is that it's an even number
21:49:38 <RodgerTheGreat> you end up needing to do less "nop" things to shave off an instructions
21:49:56 <lament> suppose we want to print an 'even' char
21:50:26 <lament> if we wrap on 256, that means the program that prints this char has to be of even length
21:50:34 <lament> if we wrap on 257, the program could be either even or odd
21:53:05 <RodgerTheGreat> well, if the hello world works and it's the first program coded in the language, doesn't that instantly make it canon?
21:53:28 <lament> well, 257 is a strange thing to wrap on, and he did remove that implementation from the wiki
21:54:11 <lament> i'm not sure pastebin likes being sent stuff to
21:55:27 <lament> http://pastebin.ca/397942
21:56:22 <lament> It's practically trivial. In particular, the source is never doubled.
21:57:02 -!- nazgjunk has quit ("Leaving").
21:57:17 <lament> can you try it in the other interpreter?
21:57:36 <RodgerTheGreat> sweet jesus I do not understand that... wait, are you using a series of NOPs to gradually decrease the program value, and using a C to dump out each character?
21:58:24 <RodgerTheGreat> I believe the proper response to that lies here: http://www.myconfinedspace.com/wp-content/uploads/2007/03/omgwtfbbq-39352.jpg
22:03:47 <RodgerTheGreat> got it. Now I need to find where he specified wrapping...
22:04:23 <oerjan> I haven't read all the logs yet, but it occurs to me that there should be a way to compress the program with all that duplication in it, so you could worry less about space.
22:04:58 <RodgerTheGreat> although, lament's solution doesn't depend on duplication at all
22:06:07 <RodgerTheGreat> http://pastebin.ca/raw/397577 <- I'm having difficulty figuring out what part of this to modify for mod 257 wrapping...
22:06:34 <lament> http://pastebin.ca/397959
22:06:42 <oerjan> That's not perl, that's thutu2perl
22:07:14 <lament> RodgerTheGreat: i'm guessing you need to change those '128' to '257'?
22:07:50 <RodgerTheGreat> lament: that's what I was thinking, but there seemed to be more than I was expecting- I'll just give it a shot and see what happens.
22:08:37 <oerjan> might be an idea to use the original thutu source.
22:09:10 <lament> RodgerTheGreat: use the prettified version, it's way more informative :)
22:10:10 <oerjan> i would presume that everything from the original thutu is within that large while loop.
22:13:46 <oerjan> on the other hand the original thutu may not be much better, the part before the and's is probably the same and the part after just boilerplate for each thutu primitive command
22:15:03 <oerjan> which means we could probably reverse the compilation rather easily.
22:15:43 <RodgerTheGreat> well, I'm not sure if it doesn't work or I'm just using the interpreter properly. :/
22:22:25 <RodgerTheGreat> which is currently looking fairly impossible without bruteforcing
22:22:26 <lament> i still think it's wrong to wrap on 257
22:22:44 <lament> his interpreter is full of typos and doesn't even run
22:23:21 <RodgerTheGreat> and that's probably why nobody else has tried to code in this language
22:24:02 -!- bsmnt_bot has joined.
22:25:14 <oerjan> writing a dupdog interpreter directly in perl should be trivial.
22:27:22 <bsmnt_bot> IOError: [Errno 2] No such file or directory: '/bot/scripts/foo'
22:51:00 -!- nazgjunk has joined.
22:54:04 -!- nazgjunk has quit (Client Quit).
23:12:21 <oerjan> simply add a new initial state to the initial state of the maximal one for n, which transitions to the original immediately. Thus BB(n+1) >= BB(n)+1.
23:14:38 <oerjan> in fact i think that can be improved to something approximately like BB(n+1) >>= BB(n)*(1+1/n)
23:15:07 <oerjan> namely, let s be the _most_ used state for the maximal one for BB(n).
23:15:58 <oerjan> Now make a new one which always pass through s and the new state in sequence. Thus at least 1/n of the steps will be doubled.
23:16:30 -!- jix__ has quit ("Bitte waehlen Sie eine Beerdigungnachricht").
23:17:31 <oerjan> but intuition tells that it of course grows much more rapidly than that from some point.
23:18:30 <oerjan> because in fact there can be no computable function f such that f(BB(n)) >= BB(n+1)
23:21:23 <oerjan> although proving that f(BB(n)) < BB(n+1) for _every_ n greater than some limit might require some cleverness.
23:24:17 <oerjan> f(BB(n)) < BB(n+k) for some k and all n seems like it could be done, if k is big enough to embed computation of f in
23:25:26 <Sgeo> What does "grows faster than" mean?
23:26:17 <Sgeo> "computable function f such that f(BB(n)) >= BB(n+1)"
23:27:51 <oerjan> it means at a minimum that lim (x -> inf) f(x)/BB(x) = 0
23:28:53 * Sgeo doesn't understand "f(x) = o(BB(x))
23:28:59 * Sgeo understands the limit
23:29:12 <oerjan> well it's a notation for the limit
23:29:46 -!- ShadowHntr has joined.
23:31:41 <Sgeo> Can there exist a computable function f(x) such that f(x) > BB(x) when x is less than an arbitrary integer a?
23:31:43 <oerjan> HE WAS EATEN BY THE COOKIE MONSTER
23:32:20 <oerjan> just let f(y) = 1 + max (x <= a) BB(x)
23:32:39 <oerjan> as you see it can even be constant
23:33:22 <Sgeo> umm... BB(x) isn't computable.. am I missing something?
23:33:37 <oerjan> mind you the constant exists in theory but we cannot actually find it for any but a finite number of a's
23:34:19 <oerjan> well the point is that every constant is computable in isolation.
23:34:47 <oerjan> it's only functions that can be theoretically uncomputable
23:35:53 <oerjan> so it is sort of cheating
23:37:40 <oerjan> the constant "exists", but its decimal sequence cannot be proven to satisfy its definition (or for that matter, written down within the space of our universe).
23:38:14 <Sgeo> "our universe"? So it's a finite amount of space?
23:38:22 <bsmntbombdood> the busy beaver function is able to solve the halting problem too
23:38:31 <oerjan> the visible universe, then.
23:38:58 <Sgeo> No, I meant the space the number would require
23:39:37 <oerjan> well it is a finite number, so it has a finite, but totally impractical and perhaps physically non-existing size.
23:40:59 <oerjan> but even writing down the _size_ would be impossible in practice. That's what being greater than any computable functions you can think of does.
23:42:01 <bsmntbombdood> oh nice, the busy beaver function is able to prove theorems experimentally
23:42:03 <oerjan> i.e. the number is greater than Ackermann(1000,1000), which is itself an entirely computable number but still of massively "unphysical" size.
23:43:07 <oerjan> *computable number = computable function of reasonable numbers
23:44:33 <Sgeo> grr I don't have haskell installed I think
23:44:40 * Sgeo is reading about factorials
23:44:44 <Sgeo> and the gamma function
23:45:10 <lament> yeah, factorials are a cool Haskell feature.
23:45:20 <oerjan> apropos haskell, the Data.Sequence module seems eminently suited for optimizing Dupdog, since it can concatenate in logarithmic time
23:46:01 <oerjan> the language everyone was discussing during most of today
23:46:48 <oerjan> in fact you arrived just about when the discussion ended (just as i left just before it began)
23:47:12 <RodgerTheGreat> and seveninchbread was probably stoned when he made it
23:59:33 -!- tgwizard has quit (Remote closed the connection).