←2004-02-07 2004-02-08 2004-02-09→ ↑2004 ↑all
04:48:04 -!- Toreun has joined.
04:48:25 -!- Toreun has quit (Client Quit).
04:48:31 -!- Toreun has joined.
04:51:25 -!- lament has joined.
04:56:08 <Toreun> anyone alive here?
04:56:23 <lament> no
04:56:50 <lament> this channel is for dead people only
04:56:55 <Toreun> just checking
04:57:01 <lament> don't worry
04:57:16 <lament> if anybody alive comes in, he'll be banned
04:57:31 <Toreun> phew I'm safe
05:00:53 <Toreun> how do you test for turing-completeness in a programming language? aside from making a universal turing machine in the language
05:01:43 <lament> writing an interpreter for some other language which was already proven to be turing-complete
05:01:54 <lament> brainfuck is often easy to write an interpreter for
05:02:25 <lament> or the universal register machine, which was used to prove turing-completeness of brainfuck itself
05:02:53 <Toreun> well, brainfuck is a UTM itself, essentially, isn't it?
05:03:24 <lament> um
05:03:30 <lament> no?
05:03:45 <lament> what do you mean, "is a UTM"?
05:04:05 <lament> (whatever you mean, it isn't)
05:04:29 <Toreun> well, a universal turing machine is a subset of brainfuck, isn't it?
05:04:32 <Toreun> or something like that
05:04:32 <lament> no.
05:04:34 <lament> no.
05:04:44 <Toreun> because I thought that brainfuck was just meant to emulate a turing machine
05:04:47 <lament> no.
05:05:07 <Toreun> oh?
05:05:34 <lament> yeah.
05:06:34 <Toreun> what other functions does a turing machine have, apart from the bf ones?
05:06:54 <lament> it's just completely different.
05:07:17 <lament> TMs have a bunch of states.
05:07:32 <lament> depending on the state, certain operations are performed.
05:07:55 <lament> Then the machine goes into a new state depending on the old state and on what symbol the reading head is looking at.
05:08:02 <lament> Brainfuck is nothing like that.
05:08:40 <Toreun> oh, ok
05:09:29 <lament> TM is generally harder to implement in a given programming language than Brainfuck
05:09:57 <Toreun> the difference between a UTM and a TM is that a UTM emulates a TM, am I right?
05:10:13 <lament> the whole terminology is extremely fucked up.
05:10:27 <lament> a TM is what we now would call a program.
05:10:35 <Toreun> ok
05:10:49 <lament> UTM is a program that can emulate the behaviour of any other TM
05:10:55 <Toreun> so that's just like a table of states, etc.
05:11:03 <lament> i.e. basically an interpreter for the (unspecified) language in which TMs are written
05:11:30 <lament> note that saying "a program for the Turing Machine" is incorrect
05:11:44 <lament> which sucks! but oh well
05:12:06 <Toreun> so wait, if I write a non-universal turing machine in a language, does it still make it turing-complete?
05:12:18 <Toreun> or prove that a program is equivalent to a turing machine?
05:12:56 <lament> no.
05:13:06 <lament> for example you can have a turing machine for adding two numbers together.
05:13:20 <lament> and you can write that in your programming language.
05:13:23 <lament> that proves nothing.
05:13:51 <Toreun> ah, ok, but if you write the program in such a way that it acts like a turing machine
05:14:07 <Toreun> or do you actually have to write a utm
05:14:26 <Toreun> (or something that is a superset/equivalent of a utm)
05:14:53 <lament> equivalent to UTM
05:15:11 <lament> so, an interpreter which can interpret programs which specify turing machines
05:15:24 <Toreun> yes
05:16:24 <lament> one of the machines it can act as, then, is the UTM itself.
05:16:44 <lament> bah! turing machines are boring
05:16:59 <Toreun> well, I'm trying to prove turing-completeness for an esoteric language
05:17:24 <Toreun> I'm pretty sure it is, but I want proof
05:18:41 <lament> actually implementing a "turing machine intepreter" is generally harder than other possible ways
05:19:02 <lament> depending on the language, either Brainfuck or SKI calculus will be easy to implement
05:19:24 <Toreun> SKI Calculus
05:19:28 * Toreun goes to look that up
05:19:48 <lament> combinatory logic.
05:20:21 <Toreun> ok
05:20:55 <Toreun> it looks like brainfuck would be easier to implement because I don't really wanna think enough to implement this...
05:25:11 <Toreun> well, I'm off to bed
05:26:07 -!- Toreun has quit.
07:22:01 <lament> somebody actually came to #esoteric and asked questions.
07:22:05 <lament> First time ever.
07:58:30 -!- lament has quit ("Money is the answer to everything (Ecclesiastes 10:19)").
07:59:59 -!- clog has quit (ended).
08:00:00 -!- clog has joined.
08:08:48 -!- cmeme has quit (Connection reset by peer).
08:09:43 -!- cmeme has joined.
08:18:18 -!- cmeme has quit (Read error: 104 (Connection reset by peer)).
08:19:51 -!- cmeme has joined.
08:20:27 -!- cmeme has quit (Read error: 104 (Connection reset by peer)).
08:23:52 -!- cmeme has joined.
15:22:05 -!- Toreun has joined.
15:37:06 -!- Toreun has quit.
16:18:31 -!- Toreun has joined.
16:19:42 -!- Toreun has quit (Client Quit).
16:26:27 -!- cmeme has quit (Connection reset by peer).
16:34:13 -!- cmeme has joined.
17:00:50 -!- lament has joined.
20:03:25 -!- Toreun has joined.
20:33:55 <Taaus> Any luck proving TC for your language, Toreun? :)
20:48:02 <Toreun> almost
20:48:06 <Toreun> I'm working on a BF interpreter
20:48:13 <Toreun> I've got tape operations down pretty well
20:48:33 <Toreun> the actual interpretation is the hard part though
20:48:52 <lament> what's your language like?
20:48:59 <Toreun> two dimensional, using a stack and a queue
20:49:50 <Toreun> with source editing possibilities
20:49:59 <lament> like befunge with an extra queue?
20:50:14 <Toreun> sorta, yeah
20:50:21 <fizzie> random stuff: I almost wrote a sed-based brainf*ck interpreter, but then I decided writing a befunge one would be more interesting. managed to implement [0-9], @ and +, then got bored.
20:50:37 <Toreun> I wanted it to have the functionality of funge 98, without such a big mess
20:50:54 <fizzie> (writing things in sed is _tedious_.)
20:51:10 <Toreun> well, it's better than malbolge :)
20:51:24 <lament> Toreun: brainfuck is probably not the easiest way to prove turing-completeness of that
20:51:28 <fizzie> marginally, yes. but it doesn't have numbers.
20:51:55 <lament> Toreun: first, you could write a translator from befunge to your language; that would prove it
20:52:10 <Toreun> well, it's not that similiar
20:52:21 <lament> Toreun: second, you could implement something like the game of life - probably easy with a 2d field and source editing
20:52:27 <lament> and game of life is TC
20:52:43 <Toreun> that's a good idea
20:52:51 <Toreun> but source editing isn't that easy
20:53:23 <lament> well, you judge
20:53:41 <Toreun> because when you want to edit the source, to get to the byte you want to edit, the editing pointer follows the normal execution path
20:53:43 <Toreun> if that makes any sense
20:55:00 <fizzie> (and sed's _slow_. it takes about 6.22 seconds to calculate the 20th fibonacci number using my recursive sed thing. sorry if I seem obsessed with sed. the 'language' haunts my nightmares.)
20:55:21 <Toreun> I haven't look at sed much to be cursed by it like that
20:55:44 <Toreun> though I woke up last night with an algorithm for reversing the queue in my language
20:58:38 <fizzie> er, with a stack and a queue, wouldn't the "obvious" way to do that be to stack everything from the queue to the stack, and then enqueue them back in the queue? (hee, that sounds fun. stack to the stack and enqueue in a queue.)
20:59:27 <Toreun> well, yeah
20:59:38 <Toreun> but I also have temporary memory locations
20:59:57 <fizzie> whoa, you seem to have everything.
20:59:58 <Toreun> and I have to deal with null bytes and stuff, and make sure I preserve the contents of all the other mem locations
21:00:19 <lament> your language appears to be too easy :)
21:00:23 <Toreun> it is quite easy
21:00:35 <Toreun> but I didn't design it to be hard
21:00:41 <Toreun> I designed it to be featureful
21:00:59 <Toreun> it supports recursive functions!
21:01:07 <fizzie> programming should be hard, otherwise anyone could do it. :p
21:01:28 <lament> featureful esoteric languages are kind of boring
21:01:43 <fizzie> how do you define functions in your 2d language? there was that talk re functions-in-befunge on esolang a while ago.
21:01:56 <lament> "my language can do this, and this, and that, and that, and that, and that, and that"
21:01:59 <lament> "it's called Java"
21:02:04 <Toreun> lol
21:02:13 <lament> esoteric languages should be minimal!
21:02:22 <Toreun> you don't really define functions, you define a character to do something
21:02:57 <fizzie> ah. please tell me you don't have 'fingerprints' for extensions too.
21:03:11 <Toreun> fingerprints?
21:03:22 <fizzie> like funge98 '(' and ')' instructions?
21:03:31 <Toreun> nope
21:04:34 <fizzie> phew.
21:04:43 <Toreun> I designed it specifically so it /wouldn't/ be the mess that funge98 was, but was as functional
21:06:01 <Toreun> yes, it is probably too easy to use
21:06:23 <Toreun> as far as esolangs go, at least
21:06:48 <fizzie> oh well, they can't all be malbolges.
21:08:47 <Toreun> yeah
21:13:14 <Toreun> at times like this, I am kinda regretting that it is this complicated... I am still not sure how I should store the instructions for brainfuck
21:13:49 <Toreun> I'm probably gonna end up just using source-editing, so I can have the stack for other things
21:14:08 <lament> instead of writing an interpreter
21:14:17 <lament> perhaps writing a compiler from brainfuck to your language would be easier?
21:14:27 <lament> (it doesn't matter what you write the compiler itself in)
21:16:49 <Toreun> well, there are no specified loops in my language, it's just changing the direction four times
21:17:48 <Toreun> that shouldn't be too hard though
21:18:04 <Toreun> though I liked the idea of having an interpreter interpret an interpreter
21:18:05 -!- hcf has joined.
21:18:24 <fizzie> infinite-sized plane?
21:18:29 <lament> hi hcf!
21:18:33 <hcf> hi lament
21:18:37 <Toreun> well, it's defined by the source originally
21:18:44 <hcf> these links may interest you
21:18:45 <hcf> http://wiw.org/~ams/projects/itch.html http://sed.sourceforge.net/local/scripts/turing.sed http://c2.com/cgi/wiki?TuringComplete http://c2.com/cgi/wiki?LittleLanguage http://www2.lns.mit.edu/~dsw/turing/turing.html http://www.nmia.com/~soki/turing/ http://www.unidex.com/turing/ http://www.cus.org.uk/~flagg/tacpprm/graffle/
21:19:02 <fizzie> eek! I see 'sed' there.
21:19:13 <lament> hcf: just how much free time do you have? :)
21:21:03 <Toreun> fizzie: ... but you could just add whitespace on the sides of the source to make it bigger
21:21:15 <fizzie> mm'k.
21:21:31 -!- hcf has left (?).
21:21:41 <Toreun> I don't have an end execution instruction, it stops when it reaches the end of the source
21:22:41 <fizzie> are arbitrary jumps possible?
21:23:38 <Toreun> whattaya mean? like goto?
21:24:14 <fizzie> like that can't-remember-the-letter instruction in funge98 which pops the new delta vector from the stack.
21:24:28 <Toreun> I'm not sure what you mean
21:24:58 <fizzie> well, can you jump from (a, b) to (c, d) without arranging an empty path between them.
21:25:21 <Toreun> if you make two comment lines
21:25:50 <Toreun> comments vertically are not necessarily comments horizontally
21:25:58 <Toreun> so you could do that, and simulate an empty path
21:26:01 <fizzie> ah, a bit like funge98 ;.
21:26:11 <fizzie> (or was it ';'?)
21:26:26 <Toreun> I don't remember
21:36:22 <Toreun> hmm, I can't seem to find a good specification of funge-98
21:38:08 <fizzie> hm. the catseye page doesn't seem too alive.
21:38:18 <Toreun> yeah it's been down for quite awhile
21:38:28 <Toreun> and google doesn't even have a cache anymore
21:39:06 <Toreun> thanks to http://www.archive.org/
21:39:10 <Toreun> I'm able to find it
21:41:30 <Toreun> but... it seems to be slow, and the esoteric page isn't archived
21:44:18 <Toreun> but, yeah, comments in my lang are exactly like ; in funge98
21:44:20 <Toreun> I just checked
21:54:55 -!- hcf has joined.
21:54:59 <hcf> http://catseye.mine.nu:8080/projects/funge98-2003.0326/
21:55:54 <Toreun> catseye changed their url?
21:56:03 <hcf> it's not all there
21:56:18 <hcf> dunno if it's just a partial mirror or what
21:56:26 <Toreun> well, the index isn't there
21:57:25 <fizzie> what is this "hcf" thing? some kind of fairy godmother? someone needs a funge98 spec and then it joins out of the blue and gives an url. hm, lessee. "I lack a nice laptop." hmm? nothing happens...
22:00:17 <Toreun> heh
22:00:28 <hcf> fairy url service not fairy hardware service
22:00:38 <fizzie> aw. :(
22:00:51 <Toreun> hmm... I need a URL that gives me free hardware!
22:00:57 <Toreun> a URL for a website**
22:00:59 <hcf> damnit
22:02:25 <hcf> how about http://www.openhardware.net it's open as in free
22:02:44 <Toreun> damn! loophole!
22:03:50 <fizzie> "where was that website where they sent people apple powerbooks for free (without any form of payment, that is) when you entered your name and address?"
22:04:37 <Toreun> there was a site that got you a free Lindows PC if you lived in CA
22:04:38 <hcf> on Earth
22:04:45 <Toreun> (california, not canadia)
22:05:00 <fizzie> wrong continent.
22:07:26 -!- hcf has left (?).
←2004-02-07 2004-02-08 2004-02-09→ ↑2004 ↑all