00:00:09 oic.. I guess I 00:00:39 oic.. I guess I need a universal turing machine - minus the udeciable part, don't I :) 00:00:53 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:00:56 udeciable -> undecidable 00:01:41 I think I'm still grappling for the correct term 00:01:45 for example: 00:02:09 I can create a language that computes for all finite state machines and never halts 00:02:31 I can create a language that computes for all pushdown automata and never halts 00:02:50 Can I create a language that computes for all deciders and never halts? 00:03:16 the answer should be yes, if I understand correctly 00:03:23 i don't know what you mean by "a language that computes for all Xs" 00:03:37 ahh 00:03:58 I mean that I can create a programming language where any possible finite state machine is understood and computed 00:04:17 so given the syntax, I can type in my fsm and run it 00:04:27 ok. 00:04:38 so a language for fsm's, easy enough 00:04:58 but 00:05:04 so the next step is a language for pda's.. no problem either 00:05:05 what do you mean by "and never halts"? 00:05:37 or did you mean "and always halts"? 00:05:48 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 ok, i think i can guess at what you're asking 00:06:36 so a program run in this language would never halt.. but it would be a decider and not just a pda 00:06:58 but first i'm pretty sure you're typing "never halt" when you mean "always halt" :) 00:07:07 deciders always halt. 00:07:22 fsm's alwyays halt. (for finite input strings, anyway) 00:08:38 you're right.. I want the language to always halt 00:09:54 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 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:18 yeah hehe 00:10:24 it's probably not impossible though 00:10:26 and yeah 00:10:34 there are several "missing" languages 00:10:58 it disturbs me slightly that deterministic and non-deterministic PDA's accept different languages 00:11:28 right, the deterministic pda is also glossed over .. but still more powerful than a fsm 00:12:26 so I guess the question is, is it possible to construct a universal decider? 00:14:11 http://en.wikipedia.org/wiki/Machines_that_always_halt 00:14:16 well... what exactly do you mean by "universal" in this context? i wasn't aware that there was a "universal" PDA 00:14:45 that's my fault 00:15:51 It should be possible to make a programming language that takes any arbitrary pda and computes it.. 00:15:55 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:10 yeah, ok 00:16:17 a language-for-describing-pda's 00:16:22 right 00:16:22 sort of a meta-language 00:16:35 so I need a language-for-describing-deciders 00:16:42 but, could that meta-language be processed by a PDA, itself? 00:16:43 well want, not need :) 00:17:07 oic.. universal doesn't work there :) 00:17:25 hmmm 00:17:29 yeah, i don't think it does 00:17:43 easier to think about for fsm's though 00:17:59 that wiki page I think answers it 00:18:01 would be hard to imagine a language-for-describing-fsm's that could itself be described by an fsm 00:18:08 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:27 right 00:18:48 so basically my if statement language is right.. because that's just a loop unrolling 00:18:50 calamari: check out the book that's referenced on that wiki article, if you can 00:19:17 which 00:19:49 I have the Sipser book 00:20:11 I don't have Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation 00:20:20 if that's what you mean 00:21:00 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 I guess you don't mean the Sipser book, because it doesn't mention PL-GOTO :) 00:22:05 oh, sorry 00:22:19 i guess more references were added to that page since i last looked at at 00:22:29 that's okay, I whittled it down :) 00:22:29 yeah, i meant brainerd & landweber. 00:22:56 do you own the book? 00:23:17 no, i just have it on loan 00:23:28 indefinate loan, so long as i keep remembering to renew it online :) 00:23:31 ahh.. does it describe lambda calculus? 00:23:40 hm, not sure. one sec 00:24:48 -!- puzzlet has joined. 00:25:07 cool, university has it 00:27:11 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:32 cool 00:27:58 looks like I can buy it from amazon.com for 55 cents :) 00:28:05 thanks for looking that up 00:28:33 55 cents?!?? 00:28:37 no problem :) 00:29:30 I don't think I can go wrong for that price.. snagging it 00:31:18 yup, 55 cents... wild. 00:44:11 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 which class? they mentioned static analysis in my computer engineering class 00:50:04 -!- zerozero has joined. 00:52:19 "definition of programming languages" 00:52:54 -!- zerozero has quit (Client Quit). 00:53:36 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 heh, i'm taking a course called that 01:37:25 you're not in my university are you? 01:37:42 static analysis of java code is the project we're doing as well... 01:41:05 you better not turn out to be fromD my uni, cause then i'd have to buy you a beer or something. 02:05:48 heh. 02:06:08 lament: does the name "Spotty Dotty" mean anything to you? 02:06:15 cpressey: jesus christ 02:06:21 hahahaha 02:06:28 i never suspected! 02:06:30 you must not read the names of the posters on webct :) 02:06:42 i never went there 02:06:50 i can't say i particularly care about that course 02:07:09 anyway, i'm the guy who sits in the front row and showed up in a mask for hallDoween 02:08:36 yeah, i suspected - since your name isn't exactly common 02:11:03 anyway, i must go now - see you tomorrow i guess... bizarre 02:12:28 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 whoaly sh!t.. does this mean lament and cpressey are in the same university?! 05:34:33 and the same class 05:34:41 woah! 05:34:52 what are the odds for that happening? 05:35:29 well, I dunno.. maybe people in candaa are crazier than the rest of the world.. might skew the stats ;) 05:35:38 `:) 05:35:43 awesome 05:39:02 "Maybe"? 05:39:10 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:41:22 Heh 05:42:26 GregorR: http://www.jhuapl.edu/newscenter/pressreleases/2005/051109.asp 05:42:36 Yes, I've heard of the book. 05:42:41 (Don't know if that's what that link is though :P) 05:42:52 nope 05:43:09 Oooh, cool. 05:47:14 hmm, back to the skyroads :) 05:53:14 *yawn* 06:14:52 -!- calamari has quit ("Leaving"). 06:25:28 dum dum dum 06:26:50 Yeah you are HAHAHAHAHAH 06:26:53 :P 06:27:01 :( 06:29:14 You walked into that brick wall ;) 06:29:28 :( 06:29:38 I'm not stupid! I'm neuron challenged! 06:31:22 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. 08:11:39 (back for four hours.. :)) 10:29:26 gotta go, need food. 10:29:27 -!- Keymaker has left (?). 13:42:30 -!- Keymaker has joined. 13:49:41 -!- kipple has joined. 13:49:45 kipple! 13:49:50 hello 13:50:13 ho 13:50:34 now i know where in the file the level data is read from 13:51:00 good question... 13:51:07 i said i know :) 13:51:09 what have you found out so far? 13:51:12 aha 13:51:14 hehe 13:51:18 sorry. I misread 13:51:21 ok 13:51:41 now != how ;) 13:52:15 :) in every level data piece there's the variables for how fast o2 goes down etc.. 13:52:23 but the actual level format is still bizarre 13:52:30 i've tried changing things but it's just crazy 13:52:44 i've managed to change colours 13:53:03 i have no idea how the level pieces are formed, and how the coordinates are set 13:53:42 once i changed only two bytes a bit, and the whole level got very strange 13:53:52 so i have no idea how the blocks are placed 13:57:52 well, I guess you just have to try more... 13:58:20 i will 13:58:42 actually at the moment i'm in hex editor.. 14:00:16 hmm, it crashed.. 14:01:10 hm 14:01:52 i suppose the format needs to be correct.. x) 14:08:54 trekdat sounds like trackdata, so i suppose there's something vital inside, but i'd assume it's the 3d models 14:10:14 seen this: http://skystreets.kaosfusion.com/ ? 14:10:48 yeah. the "clone" sucks, and the author hasn't discovered any files except sounds 14:10:59 and iirc he doesn't tell the format on the page either 14:11:11 too bad 14:11:27 yeah 14:12:57 well the source code is available, so if you need to mod the sounds you could look at those 14:13:20 yeah, although iirc the clone had own sounds, not the original ones 14:13:56 by the way, just discovered muzax.lzs is really the music file, and not any game related 14:14:19 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 i really hope they don't have any bizarre compression of their own.. 14:27:45 trekdat seems to be exactly same in the different versions 14:27:50 thanks heaven 14:28:13 that means that the level data should be entirely in roads.lzs 14:32:09 .lzs lz is often lempel-ziv (compression (but there are different lz variants) 14:32:10 ) 14:33:01 hmmm 14:33:05 cheers 14:33:50 could you send me the roads.lzs file? 14:34:54 http://www.bluemoon.ee/history/skyroads/skyroads.zip 14:36:37 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 it could make sense that the level data would be pictures, instead 14:37:03 or dunno 14:37:35 yeah lzw is used in gif 14:37:42 ok 14:37:45 lz77 is used in zip and gzip (in combination with huffman) 14:37:51 and in png 14:38:06 lzw was patented until april05 lz77 was always patent-free 14:38:16 that's why png uses lz77 instead of lzw 14:38:34 ok :) i don't know much about compression.. 14:39:03 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 yeah, all that have those are images in the game 14:39:56 too all the files use the same extension for some reason 14:40:09 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 maybe they are all compressed with lzs, whatever it is 14:40:17 yeah 14:40:24 i know, but it's annoying :) 14:40:33 I doubt the extension says anything at all, but it's worth checking out I guess 14:40:50 yeah, but why would they use lzs? 14:40:53 it doesn't make any sense 14:40:59 the game is called skyroads 14:41:22 maybe 0x10 0x00 0x00 0x00 is a little-endian adress (byte 13) 14:41:41 in which file? 14:41:46 HELPMENU.LZS 14:41:59 no idea 14:42:02 idea! cmap == color map it contains the pallette data... PICT == picture data, contains the picture 14:42:03 I doubt they use 32bit ints 14:42:15 hmm! 14:42:33 good idea 14:42:36 really good 14:42:45 let's see.. 14:42:59 and the space between CMAP and PICT are 51 bytes thats 17 3 byte pairs 14:43:06 whoops 14:43:08 bbl 14:43:13 ok 14:43:42 there's only ten ways to find that out, and i'll try the first: hex editoring the file 14:43:50 I think you're on to something there. but it doesn't help for the levels 14:44:03 nope, but i want to change graphics too :D 14:45:10 jix is right! yes! 14:45:55 i changed the first 3F 3F 3F of helpmenu to 3F 00 00 (red), and texts that were white show up red now 14:51:16 cool :) 14:52:19 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 it's very probable the roads.lzs uses that lzw (or something) compression 15:02:23 there probably are track pieces that are just connected to each other 15:04:37 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:04:49 hmmm 15:05:10 but there's some compression in almost every game 15:05:15 including the old ones 15:08:39 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 that is only if they're stored as "tiles". they could be areas 15:11:15 yeah 15:11:41 and they don't need 3 bytes for color. only one 15:11:46 but that'd probably mean trekdat is filled with different areas, that all of the versions use 15:12:14 but there are colours that use three bytes, in the roads 15:12:26 what do you mean? 15:12:27 for example, i just today changed couple of them to pink, white etc.. 15:12:53 there definitely is colours in rgb form, in roads.lzs 15:14:00 the video mode is MCGA I think, which only handles 256 colors (at teh same time) 15:14:12 so there is probably a palette defined somewhere 15:14:24 but maybe I'm wrong 15:14:38 hmmm, the colours can be from 0 0 0 to 63 63 63 in this one 15:14:58 and i have no idea how it works.. :\ 15:15:22 if one sets values larger than 3F (63) the colours go strange 15:15:38 perhaps the palette has only defined 63 colors... 15:15:45 64 I mean :) 15:15:48 hehe 15:16:36 if that is the case, then color info could possibly be stored in 6 bit integers 15:17:11 yes, but i think they wouldn't try to save space that much :) 15:17:21 don't be too sure of that 15:17:45 Standard VGA only has 6 bits of color for each channel. 15:17:52 hmm 15:18:14 we might be on to something... :) 15:18:18 :) 15:19:59 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:20:17 :) 15:21:05 grrh. i wish this format can be discovered some day.. 15:21:44 naturally we could read the exe in assembler.. and try to find out what it does.. :) 15:21:49 *disassembler 15:22:28 ..but it's not that easy job.. 15:37:24 i wish i'd get the original level editor they used.. 16:30:08 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 I'd like to get a linux version of that thing, though - using wine is a pain. 16:32:56 Although I think the linux version lacks the rather usable GUI. 16:34:28 cool! 16:34:53 Now I need to go grocery-shopping. -> 16:34:55 try dosbox 16:35:03 when you're back 16:35:10 dosbox.sourceforge.net 16:35:30 or did you mean linux version of that program? probably.. :\ 16:40:22 anyways, hopefuly you'll discover something, every piece of info is required! :) 16:44:15 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 fis@colin:~/tmp/skyroads$ hexdump -n 128 -x ROADS.LZS 16:44:20 0000000 007c 08c0 02cb 0302 0432 064a 064c 0348 16:44:23 0000010 07af 0524 096b 06e4 0b42 02a0 0c9e 0348 16:44:26 0000020 0e10 05cc 101a 03d4 117c 046e 1332 0ae2 16:44:28 0000030 15b9 08f8 17aa 0620 1a02 0cf6 1dc2 0afe 16:44:36 0000040 21b4 077e 23d2 085e 25f9 08ea 282c 080a 16:44:36 0000050 29ef 0a2c 2c6a 071c 2e86 08c0 30d5 0c40 16:44:36 0000060 342a 048a 35ea 0834 37c0 0a72 3a91 0914 16:44:40 0000070 3c66 0ccc 3ea7 0770 40c4 0af0 0008 0082 16:45:44 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:08 Right, the shop. -> 16:46:25 yeah, it's a header 16:46:34 re 16:46:34 i've discovered that, i'll upload my notes soon 16:49:25 i'm going to reverse engineer the picture files 16:49:31 cool! 16:49:39 that'd be awesome 16:49:52 and that without a x86 cpu! 16:49:57 (or emulator) 16:50:01 :) 16:50:41 jix: if you can, document everything! :) 16:50:55 i'm going to do that 16:51:00 ok 16:55:24 -!- calamari has joined. 17:22:57 fizzie: here's my notes about the header http://koti.mbnet.fi/yiap/skyroads/roads.txt 17:23:07 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:24:56 that's what sets rgb 0-63 17:25:21 where? 17:25:28 (in which file, i mean) 17:25:32 I should also note that quickbasic had the same 0-63 limitations.. so that's mildly scary ;) 17:25:49 Keymaker: that's in my book, pc interrupts 17:26:00 ok 17:26:15 Keymaker: you can also look it up online, http://www.ctyme.com/rbrown.htm 17:28:07 the executable doesn't appear to be compressed 17:29:42 uses pupses and pops for function calls 17:29:52 pupses -> pushes 17:30:12 :) 17:30:44 definitely not compiled quickbasic 17:31:00 I know what that looks like 17:31:25 ok.. time for class 17:31:27 -!- calamari has quit ("Leaving"). 17:31:28 ok 17:31:51 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:28 hah :) 17:36:55 -!- mtve has quit (Read error: 110 (Connection timed out)). 17:43:11 Or earmuffs for that matter. 17:47:50 -!- marcan_ has joined. 17:56:13 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 fizzie, noticed that link about the header? 17:56:42 Yes. 17:56:46 o-k 17:57:09 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:30 ok 17:57:32 It could very well have been written in ASM ... I mean, this is DOS ... 17:57:37 thanks for the help! 17:57:52 yes, could be 17:58:04 the game is quite old, and it's 3d 18:08:51 -!- marcan has quit (Connection timed out). 18:52:57 well, gotta go. 18:53:29 -!- Keymaker has left (?). 19:21:46 -!- calamari has joined. 19:21:49 hi 19:23:38 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 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.