00:00:39 <calamari> oic.. I guess I need a universal turing machine - minus the udeciable part, don't I :)
00:00:53 <cpressey> just because the halting problem says that, in general, you can't decide whether a TM halts or not, doesn't mean that you can't work it out for a specific TM...
00:01:41 <calamari> I think I'm still grappling for the correct term
00:02:09 <calamari> I can create a language that computes for all finite state machines and never halts
00:02:31 <calamari> I can create a language that computes for all pushdown automata and never halts
00:02:50 <calamari> Can I create a language that computes for all deciders and never halts?
00:03:16 <calamari> the answer should be yes, if I understand correctly
00:03:23 <cpressey> i don't know what you mean by "a language that computes for all Xs"
00:03:58 <calamari> I mean that I can create a programming language where any possible finite state machine is understood and computed
00:04:17 <calamari> so given the syntax, I can type in my fsm and run it
00:04:38 <cpressey> so a language for fsm's, easy enough
00:05:04 <calamari> so the next step is a language for pda's.. no problem either
00:05:05 <cpressey> what do you mean by "and never halts"?
00:05:37 <cpressey> or did you mean "and always halts"?
00:05:48 <calamari> so there is a lnaguage for turing complete languages, for exampel bf.. but it can halt.. so I want to back up one step
00:06:21 <cpressey> ok, i think i can guess at what you're asking
00:06:36 <calamari> so a program run in this language would never halt.. but it would be a decider and not just a pda
00:06:58 <cpressey> but first i'm pretty sure you're typing "never halt" when you mean "always halt" :)
00:07:22 <cpressey> fsm's alwyays halt. (for finite input strings, anyway)
00:08:38 <calamari> you're right.. I want the language to always halt
00:09:54 <calamari> it just seems like there is a missing machine between the universal pda and universal tm, I'd call it the universal decider
00:09:59 <cpressey> ok, so... say you have a language for describing deciders... will it always halt? yes, because deciders always halt. HOWEVER - the problem is - how is it that your language only describes deciders? how do you know that you can't accidentally describe a Turing machine in your language? that's the hard part.
00:10:24 <cpressey> it's probably not impossible though
00:10:34 <cpressey> there are several "missing" languages
00:10:58 <cpressey> it disturbs me slightly that deterministic and non-deterministic PDA's accept different languages
00:11:28 <calamari> right, the deterministic pda is also glossed over .. but still more powerful than a fsm
00:12:26 <calamari> so I guess the question is, is it possible to construct a universal decider?
00:14:11 <calamari> http://en.wikipedia.org/wiki/Machines_that_always_halt
00:14:16 <cpressey> well... what exactly do you mean by "universal" in this context? i wasn't aware that there was a "universal" PDA
00:15:51 <calamari> It should be possible to make a programming language that takes any arbitrary pda and computes it..
00:15:55 <cpressey> well... ok, i guess there sort of is, in the weak sense that all context-free languages are equivalent to balanced parentheses... if you ignore the details... but that's sort of unsatisfying
00:16:17 <cpressey> a language-for-describing-pda's
00:16:35 <calamari> so I need a language-for-describing-deciders
00:16:42 <cpressey> but, could that meta-language be processed by a PDA, itself?
00:17:07 <calamari> oic.. universal doesn't work there :)
00:17:43 <cpressey> easier to think about for fsm's though
00:17:59 <calamari> that wiki page I think answers it
00:18:01 <cpressey> would be hard to imagine a language-for-describing-fsm's that could itself be described by an fsm
00:18:08 <calamari> In practice, a machine that always halts can be implemented as a programming language with restricted flow control instructions, so that no program (i.e. description) will ever cause the machine to enter an infinite loop. Note that this does not imply that the language is free of looping capabilities ? all we require is that such loops be finite
00:18:48 <calamari> so basically my if statement language is right.. because that's just a loop unrolling
00:18:50 <cpressey> calamari: check out the book that's referenced on that wiki article, if you can
00:20:11 <calamari> I don't have Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation
00:21:00 <cpressey> what i mean is: check your local math library :) it's not actually a very good book, but they explain what they mean by PL-{GOTO} better than the wiki article does
00:21:51 <calamari> I guess you don't mean the Sipser book, because it doesn't mention PL-GOTO :)
00:22:19 <cpressey> i guess more references were added to that page since i last looked at at
00:22:29 <calamari> that's okay, I whittled it down :)
00:22:29 <cpressey> yeah, i meant brainerd & landweber.
00:23:28 <cpressey> indefinate loan, so long as i keep remembering to renew it online :)
00:23:31 <calamari> ahh.. does it describe lambda calculus?
00:24:48 -!- puzzlet has joined.
00:27:11 <cpressey> ok.... looks like the last chapter talks a little about lambda calc, but, the chapter is really about combinatory logic (SKI calculus) so it looks mostly incidental
00:27:58 <calamari> looks like I can buy it from amazon.com for 55 cents :)
00:29:30 <calamari> I don't think I can go wrong for that price.. snagging it
00:44:11 <cpressey> calamari: btw, you might be interested in this: for one of my classes we get to do a project where we do some static analysis of Java code... I was thinking of doing some sort of halting analysis... basically, for each method of an object, determine if it is guaranteed to always halt :)
00:49:44 <calamari> which class? they mentioned static analysis in my computer engineering class
00:50:04 -!- zerozero has joined.
00:52:19 <cpressey> "definition of programming languages"
00:52:54 -!- zerozero has quit (Client Quit).
00:53:36 <cpressey> which is actually a pretty cool course overall. i thought it would be easy, but i've actually learned quite a bit
00:54:34 -!- CXI has quit (Connection timed out).
01:18:59 -!- CXI has joined.
01:36:13 <lament> heh, i'm taking a course called that
01:37:25 <lament> you're not in my university are you?
01:37:42 <lament> static analysis of java code is the project we're doing as well...
01:41:05 <lament> you better not turn out to be fromD my uni, cause then i'd have to buy you a beer or something.
02:06:08 <cpressey> lament: does the name "Spotty Dotty" mean anything to you?
02:06:15 <lament> cpressey: jesus christ
02:06:30 <cpressey> you must not read the names of the posters on webct :)
02:06:50 <lament> i can't say i particularly care about that course
02:07:09 <lament> anyway, i'm the guy who sits in the front row and showed up in a mask for hallDoween
02:08:36 <cpressey> yeah, i suspected - since your name isn't exactly common
02:11:03 <lament> anyway, i must go now - see you tomorrow i guess... bizarre
02:12:28 <cpressey> ok, cya tomorrow :) bizarre, indeed.
03:58:20 -!- Robdgreat has quit (Read error: 104 (Connection reset by peer)).
04:08:33 -!- Sgep has quit.
04:45:28 -!- Arrogant has joined.
04:46:11 -!- Arrogant has quit (Client Quit).
04:47:30 -!- Arrogant has joined.
04:52:21 -!- madbrain has quit ("Christians believe Jesus can save your soul; atheists believe Hungry Man TV dinners are a quick and easy dinner solution for ).
05:09:45 -!- kipple has quit (Read error: 110 (Connection timed out)).
05:15:09 -!- Arrogant has quit ("Chatzilla 0.9.68.5.1 [Firefox 1.5/undefined]").
05:15:41 -!- Arrogant has joined.
05:32:47 -!- Keymaker has joined.
05:34:20 <Keymaker> whoaly sh!t.. does this mean lament and cpressey are in the same university?!
05:34:52 <Keymaker> what are the odds for that happening?
05:35:29 <calamari> well, I dunno.. maybe people in candaa are crazier than the rest of the world.. might skew the stats ;)
05:39:10 <GregorR> Don't you mean "It is a statistically proven fact that"
05:40:33 * calamari suggests that GregorR read the book "How to lie with statistics"
05:42:26 <calamari> GregorR: http://www.jhuapl.edu/newscenter/pressreleases/2005/051109.asp
05:42:36 <GregorR> Yes, I've heard of the book.
05:42:41 <GregorR> (Don't know if that's what that link is though :P)
06:14:52 -!- calamari has quit ("Leaving").
06:29:14 <GregorR> You walked into that brick wall ;)
06:29:38 <lament> I'm not stupid! I'm neuron challenged!
06:31:22 <Keymaker> ha! discovered some new things from roads.lzs! :D gotta go to skool now. :/
06:31:25 -!- Keymaker has left (?).
07:39:28 -!- Arrogant has quit (Read error: 110 (Connection timed out)).
07:59:59 -!- clog has quit (ended).
08:00:00 -!- clog has joined.
08:06:37 -!- Keymaker has joined.
10:29:27 -!- Keymaker has left (?).
13:42:30 -!- Keymaker has joined.
13:49:41 -!- kipple has joined.
13:50:34 <Keymaker> now i know where in the file the level data is read from
13:51:09 <kipple> what have you found out so far?
13:52:15 <Keymaker> :) in every level data piece there's the variables for how fast o2 goes down etc..
13:52:23 <Keymaker> but the actual level format is still bizarre
13:52:30 <Keymaker> i've tried changing things but it's just crazy
13:52:44 <Keymaker> i've managed to change colours
13:53:03 <Keymaker> i have no idea how the level pieces are formed, and how the coordinates are set
13:53:42 <Keymaker> once i changed only two bytes a bit, and the whole level got very strange
13:53:52 <Keymaker> so i have no idea how the blocks are placed
13:57:52 <kipple> well, I guess you just have to try more...
13:58:42 <Keymaker> actually at the moment i'm in hex editor..
14:01:52 <Keymaker> i suppose the format needs to be correct.. x)
14:08:54 <Keymaker> trekdat sounds like trackdata, so i suppose there's something vital inside, but i'd assume it's the 3d models
14:10:14 <kipple> seen this: http://skystreets.kaosfusion.com/ ?
14:10:48 <Keymaker> yeah. the "clone" sucks, and the author hasn't discovered any files except sounds
14:10:59 <Keymaker> and iirc he doesn't tell the format on the page either
14:12:57 <kipple> well the source code is available, so if you need to mod the sounds you could look at those
14:13:20 <Keymaker> yeah, although iirc the clone had own sounds, not the original ones
14:13:56 <Keymaker> by the way, just discovered muzax.lzs is really the music file, and not any game related
14:14:19 <Keymaker> i renamed the file and started the game, and when toggled the music on it crashed, since couldn't find the music file
14:14:47 -!- jix has joined.
14:18:59 <Keymaker> i really hope they don't have any bizarre compression of their own..
14:27:45 <Keymaker> trekdat seems to be exactly same in the different versions
14:28:13 <Keymaker> that means that the level data should be entirely in roads.lzs
14:32:09 <jix> .lzs lz is often lempel-ziv (compression (but there are different lz variants)
14:33:50 <jix> could you send me the roads.lzs file?
14:34:54 <Keymaker> http://www.bluemoon.ee/history/skyroads/skyroads.zip
14:36:37 <Keymaker> hmm, this is interesting -- it says on some page that Lempel-Ziv(-Welch) is a popular data compression often used in images
14:36:57 <Keymaker> it could make sense that the level data would be pictures, instead
14:37:35 <jix> yeah lzw is used in gif
14:37:45 <jix> lz77 is used in zip and gzip (in combination with huffman)
14:37:51 <jix> and in png
14:38:06 <jix> lzw was patented until april05 lz77 was always patent-free
14:38:16 <jix> that's why png uses lz77 instead of lzw
14:38:34 <Keymaker> ok :) i don't know much about compression..
14:39:03 <kipple> a lot of the lzs files share the same header CMAPr, but some don't so there is at least two different file formats I think
14:39:26 <Keymaker> yeah, all that have those are images in the game
14:39:56 <Keymaker> too all the files use the same extension for some reason
14:40:09 <kipple> anyway, it was pretty common to use the same extension on all data files regardless of format in the old days (perhaps now too)
14:40:10 <Keymaker> maybe they are all compressed with lzs, whatever it is
14:40:33 <kipple> I doubt the extension says anything at all, but it's worth checking out I guess
14:40:50 <Keymaker> yeah, but why would they use lzs?
14:41:22 <jix> maybe 0x10 0x00 0x00 0x00 is a little-endian adress (byte 13)
14:41:46 <jix> HELPMENU.LZS
14:42:02 <jix> idea! cmap == color map it contains the pallette data... PICT == picture data, contains the picture
14:42:03 <kipple> I doubt they use 32bit ints
14:42:59 <jix> and the space between CMAP and PICT are 51 bytes thats 17 3 byte pairs
14:43:42 <Keymaker> there's only ten ways to find that out, and i'll try the first: hex editoring the file
14:43:50 <kipple> I think you're on to something there. but it doesn't help for the levels
14:44:03 <Keymaker> nope, but i want to change graphics too :D
14:45:55 <Keymaker> i changed the first 3F 3F 3F of helpmenu to 3F 00 00 (red), and texts that were white show up red now
14:52:19 <Keymaker> i don't know what format it is, or how to conver it to some other format, but i know one thing: one image file can have more than one image. the helpfile has the two help screens inside it
15:01:25 <Keymaker> it's very probable the roads.lzs uses that lzw (or something) compression
15:02:23 <Keymaker> there probably are track pieces that are just connected to each other
15:04:37 <kipple> I think it's a bit unlikely that they've compressed the level data. the levels are so simple that compressing wouldn't save that much space. And decompressing is expensive on old computers
15:05:10 <Keymaker> but there's some compression in almost every game
15:08:39 <Keymaker> and there got to be something in this, too. for example, each row can have stuff on 3 level, on 7 places. that's 21 per row. and if one level has for example 100 rows, and three bytes for rgb value, that'd make 6300 bytes. even more if the stuff would be represented as integers. and the demo roads.lzs is 4k and has six tracks :)
15:10:55 <kipple> that is only if they're stored as "tiles". they could be areas
15:11:41 <kipple> and they don't need 3 bytes for color. only one
15:11:46 <Keymaker> but that'd probably mean trekdat is filled with different areas, that all of the versions use
15:12:14 <Keymaker> but there are colours that use three bytes, in the roads
15:12:27 <Keymaker> for example, i just today changed couple of them to pink, white etc..
15:12:53 <Keymaker> there definitely is colours in rgb form, in roads.lzs
15:14:00 <kipple> the video mode is MCGA I think, which only handles 256 colors (at teh same time)
15:14:12 <kipple> so there is probably a palette defined somewhere
15:14:38 <Keymaker> hmmm, the colours can be from 0 0 0 to 63 63 63 in this one
15:14:58 <Keymaker> and i have no idea how it works.. :\
15:15:22 <Keymaker> if one sets values larger than 3F (63) the colours go strange
15:15:38 <kipple> perhaps the palette has only defined 63 colors...
15:16:36 <kipple> if that is the case, then color info could possibly be stored in 6 bit integers
15:17:11 <Keymaker> yes, but i think they wouldn't try to save space that much :)
15:17:21 <kipple> don't be too sure of that
15:17:45 <fizzie> Standard VGA only has 6 bits of color for each channel.
15:18:14 <kipple> we might be on to something... :)
15:19:59 <fizzie> IIRC the palette control registers take values between 0x00 - 0x3f, too, although can't be sure of that - it's been ages since I last wrote anything that accessed hardware directly. :p
15:21:05 <Keymaker> grrh. i wish this format can be discovered some day..
15:21:44 <Keymaker> naturally we could read the exe in assembler.. and try to find out what it does.. :)
15:22:28 <Keymaker> ..but it's not that easy job..
15:37:24 <Keymaker> i wish i'd get the original level editor they used..
16:30:08 <fizzie> I've been disassembling it with ida-pro a bit, but it's still a.. mess: http://gehennom.org/~fis/skyroads-graph.png But at least I've located the fopen/fread-like functions. Next I should figure out what the routines that use those do.
16:30:47 <fizzie> I'd like to get a linux version of that thing, though - using wine is a pain.
16:32:56 <fizzie> Although I think the linux version lacks the rather usable GUI.
16:34:53 <fizzie> Now I need to go grocery-shopping. ->
16:35:30 <Keymaker> or did you mean linux version of that program? probably.. :\
16:40:22 <Keymaker> anyways, hopefuly you'll discover something, every piece of info is required! :)
16:44:15 <fizzie> I have an unverified guess that the first 128 bytes of ROADS.LZS is a header of some sort. It's too symmetric to be anything else:
16:44:18 <fizzie> fis@colin:~/tmp/skyroads$ hexdump -n 128 -x ROADS.LZS
16:44:20 <fizzie> 0000000 007c 08c0 02cb 0302 0432 064a 064c 0348
16:44:23 <fizzie> 0000010 07af 0524 096b 06e4 0b42 02a0 0c9e 0348
16:44:26 <fizzie> 0000020 0e10 05cc 101a 03d4 117c 046e 1332 0ae2
16:44:28 <fizzie> 0000030 15b9 08f8 17aa 0620 1a02 0cf6 1dc2 0afe
16:44:36 <fizzie> 0000040 21b4 077e 23d2 085e 25f9 08ea 282c 080a
16:44:36 <fizzie> 0000050 29ef 0a2c 2c6a 071c 2e86 08c0 30d5 0c40
16:44:36 <fizzie> 0000060 342a 048a 35ea 0834 37c0 0a72 3a91 0914
16:44:40 <fizzie> 0000070 3c66 0ccc 3ea7 0770 40c4 0af0 0008 0082
16:45:44 <fizzie> Note that for even columns, the higher byte seems to always be <0x10, and in odd columns it's ~0x00-0x40 and the numbers are monotonically increasing.
16:46:34 <Keymaker> i've discovered that, i'll upload my notes soon
16:49:25 <jix> i'm going to reverse engineer the picture files
16:49:52 <jix> and that without a x86 cpu!
16:49:57 <jix> (or emulator)
16:50:41 <Keymaker> jix: if you can, document everything! :)
16:50:55 <jix> i'm going to do that
16:55:24 -!- calamari has joined.
17:22:57 <Keymaker> fizzie: here's my notes about the header http://koti.mbnet.fi/yiap/skyroads/roads.txt
17:23:07 <Keymaker> here's an ugly site for this project: http://koti.mbnet.fi/yiap/skyroads/
17:24:39 * calamari notes, INT 10h, AX=1010h, Set Individual DAC Register..
17:25:32 <calamari> I should also note that quickbasic had the same 0-63 limitations.. so that's mildly scary ;)
17:25:49 <calamari> Keymaker: that's in my book, pc interrupts
17:26:15 <calamari> Keymaker: you can also look it up online, http://www.ctyme.com/rbrown.htm
17:28:07 <calamari> the executable doesn't appear to be compressed
17:29:42 <calamari> uses pupses and pops for function calls
17:30:44 <calamari> definitely not compiled quickbasic
17:31:27 -!- calamari has quit ("Leaving").
17:31:51 <Keymaker> and, it's most probably done in c or pascal, i'd guess.. may be assembler too
17:35:20 * GregorR is so glad he has long hair.
17:35:29 * GregorR never needs to buy a scarf.
17:35:49 -!- mtve2 has joined.
17:36:55 -!- mtve has quit (Read error: 110 (Connection timed out)).
17:43:11 <GregorR> Or earmuffs for that matter.
17:47:50 -!- marcan_ has joined.
17:56:13 <fizzie> It doesn't much look like compiled C either. A lot of functions pass parameters in registers, although some do use the stack too.
17:56:31 <Keymaker> fizzie, noticed that link about the header?
17:57:09 <fizzie> I'll continue digging around the disassembled exe when I have some free time. Must eat, and then there's some work to do.
17:57:32 <GregorR> It could very well have been written in ASM ... I mean, this is DOS ...
17:58:04 <Keymaker> the game is quite old, and it's 3d
18:08:51 -!- marcan has quit (Connection timed out).
18:53:29 -!- Keymaker has left (?).
19:21:46 -!- calamari has joined.
19:23:38 <calamari> after I logged off I realized I said it wrong.. the function is the one pushing and popping, to protect the registers at call
19:23:56 <calamari> anyhow.. next class in a few mins ;)
19:23:59 -!- calamari has quit (Client Quit).
19:44:12 -!- jix has quit ("Bitte waehlen Sie eine Beerdigungnachricht").
19:49:05 -!- Aardwolf has joined.
19:58:07 -!- jix has joined.
20:06:04 -!- GregorR-L has joined.
20:44:40 -!- GregorR-L has quit ("Chatzilla 0.9.68.5 [Firefox 1.0.6/20050716]").
20:48:43 -!- jix has quit ("Bitte waehlen Sie eine Beerdigungnachricht").
21:23:32 -!- Sgep has joined.
23:09:41 -!- madbrain has joined.