00:00:15 And one Lindsay Tanner Swett, but I daresay that's not it. 00:00:26 night 00:00:41 oh wait it _is_ warrigal 00:01:26 uorygl: darn i thought it was just a moment ago you were 14 :D 00:02:58 well i guess you're at least old enough to reveal your real name then 00:04:24 * Sgeo didn't reveal his real name until he was 17 00:05:08 -!- pikhq has joined. 00:05:22 Misread that as "Sgeo didn't learn his real name until he was 17"; that sounds like a funny environment to grow up in. 00:06:06 well _i_ thought about how surprised his parents must have been when he revealed it 00:06:33 -!- pikhq has quit (Read error: Connection reset by peer). 00:14:57 -!- cpressey has left (?). 00:21:09 -!- pikhq has joined. 00:22:48 -!- pikhq has quit (Read error: Connection reset by peer). 00:37:08 -!- pikhq has joined. 00:38:07 -!- pikhq has quit (Read error: Connection reset by peer). 00:41:55 -!- pikhq has joined. 01:14:22 -!- jcp has joined. 01:25:01 -!- MissPiggy has quit (Quit: Lost terminal). 01:28:48 -!- pikhq has quit (Read error: Connection reset by peer). 01:35:20 -!- pikhq has joined. 01:35:59 -!- pikhq has quit (Read error: Connection reset by peer). 01:40:35 -!- pikhq has joined. 01:41:57 -!- pikhq has quit (Read error: Connection reset by peer). 01:46:06 -!- pikhq has joined. 01:46:55 -!- pikhq has quit (Read error: Connection reset by peer). 01:50:31 -!- pikhq has joined. 02:06:21 -!- pikhq has quit (Read error: Connection reset by peer). 02:12:02 -!- pikhq has joined. 02:12:30 -!- pikhq has quit (Read error: Connection reset by peer). 02:22:22 -!- pikhq has joined. 02:23:25 -!- pikhq has quit (Read error: Connection reset by peer). 02:25:29 -!- Asztal has quit (Ping timeout: 248 seconds). 02:28:07 -!- pikhq has joined. 02:29:23 -!- pikhq has quit (Read error: Connection reset by peer). 02:32:45 oerjan: indeed, I have joined university. 02:32:56 fizzie: there are three of me? Darn, what happened to my monopoly? 02:33:29 i think you failed to show up to your anti-trust proceedings, so there was a default judgement 02:33:52 Aww. And I never even got the letter. It must have gotten lost in the mail. 02:33:59 -!- pikhq has joined. 02:34:02 probably in your spam folder somewhere 02:34:22 -!- pikhq has quit (Read error: Connection reset by peer). 02:35:05 Anyway, I'm the white, fuzzy one. 02:35:35 Standing on a solar panel in outer space. 02:35:58 ah 02:38:24 -!- pikhq has joined. 02:38:48 -!- pikhq has quit (Read error: Connection reset by peer). 02:43:23 -!- pikhq has joined. 02:54:14 -!- iamcal has quit. 03:01:10 -!- cal153 has joined. 03:08:13 uorygl: which university? 03:10:00 -!- cheater2 has quit (Ping timeout: 252 seconds). 03:22:44 -!- zzo38 has joined. 03:25:47 -!- olsner has quit (Ping timeout: 265 seconds). 03:29:52 -!- zzo38 has quit (Quit: Washizu Mahjong...:F:ALKSF:LAKSF:KJSDMCP#RC)I(UM@!$X<)!U@$#). 03:33:58 -!- pikhq has quit (Read error: Connection reset by peer). 03:40:05 -!- olsner has joined. 03:40:18 -!- pikhq has joined. 03:41:08 -!- pikhq has quit (Read error: Connection reset by peer). 03:47:30 augur: Grand Valley State. 03:47:42 -!- pikhq has joined. 03:47:57 what 03:48:20 Grand Valley State Universirty. 03:48:23 s/r// 03:48:44 Univesirty? 03:51:19 very gud speeling progarm 04:09:02 wheres that ey 04:23:39 -!- zzo38 has joined. 04:24:34 I DONE GONE TUH UNIVERSIRTY 04:26:59 Can you please review my program to see if it is good? 04:27:10 Can you please review my program to see if it is good enough? 04:27:45 Also, did you read that: http://notalwaysright.com/its-difficult-to-make-it-any-simpler/4160 04:38:19 -!- zzo38 has quit (Remote host closed the connection). 04:56:56 -!- augur has quit (Ping timeout: 272 seconds). 05:36:36 -!- puzzlet has quit (Changing host). 05:36:36 -!- puzzlet has joined. 05:54:23 I hate my school board's internet connection 05:54:45 51 packets transmitted, 0 received, 100% packet loss, time 50254ms 05:59:06 It's amazing I can connect at all 06:01:24 -!- jcp has quit (Quit: I will do anything (almost) for a new router.). 06:06:17 -!- MizardX has quit (Ping timeout: 240 seconds). 06:21:13 -!- augur has joined. 06:21:31 o hai 06:22:15 hi 06:22:53 hai ku 06:41:52 -!- Pthing has joined. 06:52:57 http://www.haskell.org/haskellwiki/Do_notation_considered_harmful is about LYAH 07:00:07 -!- tombom has joined. 07:04:06 -!- oerjan has quit (Quit: Good night). 07:09:55 -!- dbc has quit (Quit: Seeeeeya). 07:14:27 -!- dbc has joined. 07:46:46 -!- FireFly has joined. 07:49:51 -!- tombom has quit (Quit: Leaving). 07:59:59 -!- clog has quit (ended). 08:00:00 -!- clog has joined. 08:15:40 -!- cheater2 has joined. 08:17:21 -!- FireFly has quit (Quit: Leaving). 08:24:21 -!- Gracenotes has quit (Ping timeout: 252 seconds). 08:39:37 -!- Slereah has joined. 08:49:18 -!- Lageron has joined. 08:52:36 Hi! 09:14:18 -!- gm|lap has quit (Quit: 2 hour UPS expired. Shutting down laptop.). 09:26:47 -!- Gracenotes has joined. 09:30:28 -!- adam_d has joined. 09:51:42 -!- adam_d has quit (Quit: Leaving). 09:56:44 -!- Lageron has quit (Read error: Connection reset by peer). 10:41:07 -!- ais523 has joined. 10:50:47 -!- mosasaur1 has joined. 11:00:03 -!- mosasaur1 has quit (Ping timeout: 252 seconds). 11:07:57 -!- coppro has quit (Ping timeout: 256 seconds). 12:12:51 -!- kernel51 has joined. 12:13:02 Greetings 13:05:15 hi 13:05:23 hmm, that was a bit slow 13:05:25 hi kernel51 13:06:46 -!- ais523 has quit (Changing host). 13:06:46 -!- ais523 has joined. 13:06:46 -!- ais523 has quit (Changing host). 13:06:46 -!- ais523 has joined. 13:12:35 -!- ais523 has quit (Quit: Page closed). 13:16:58 -!- kernel51 has left (?). 13:17:45 -!- Pthing has quit (Remote host closed the connection). 13:18:42 -!- MizardX has joined. 13:19:38 -!- scarf has joined. 13:19:51 -!- scarf has changed nick to ais523. 13:41:14 -!- FireFly has joined. 13:44:49 -!- MizardX has quit (Ping timeout: 260 seconds). 13:51:43 -!- ais523 has quit (Remote host closed the connection). 14:03:22 -!- Sgeo_ has joined. 14:06:02 -!- Sgeo has quit (Ping timeout: 272 seconds). 14:09:37 -!- Pthing has joined. 14:20:01 -!- Slereah has left (?). 14:49:48 -!- scarf has joined. 14:49:57 -!- scarf has changed nick to ais523. 15:00:37 -!- MizardX has joined. 15:22:06 -!- kar8nga has joined. 15:29:44 7.0.0.5.770.5.8.7.0.0.5.4...1... 15:34:07 -!- cpressey has joined. 15:37:35 -!- oerjan has joined. 15:40:11 7.0.0.5.770.5.8.7.0.0.5.4...1... <-- i think version numbering has got out of hand 15:57:10 That looks like an OID, except not quite. 15:59:37 For example, SNMP request for the uptime of a system will end up looking for object 1.3.6.1.2.1.1.3, or (with the symbolic names) iso.org.dod.internet.mgmt.mib-2.system.sysUpTime. And that's among the simple ones. 16:01:45 A sample OID given elsewhere is 1.3.6.1.4.868.2.4.1.2.1.1.1.3.3562.3: iso.org.dod.internet.private.transition.products.chassis.card.slotCps.cpsSlotSummary.cpsModuleTable.cpsModuleEntry.cpsModuleModel.3562.3 -- they haven't even bothered to invent symbolic names for the last two levels of the hierarchy. 16:02:32 Have to say I like that all those standard SNMP MIB objects are hierarchically speaking under United States Department of Defense. 16:06:18 -!- BeholdMyGlory has joined. 16:06:40 well, to me that looks pretty out of hand too. 16:31:10 -!- MissPiggy has joined. 16:31:15 oerjan, that version number, what is it for? 16:32:32 a joke, AnMaster, a joke 16:32:45 -!- MissPiggy has quit (Changing host). 16:32:45 -!- MissPiggy has joined. 16:32:46 or alternatively, ask oklopol not me 16:41:04 oerjan, ah wrong nick 16:41:11 oklopol, what is that version number for? 16:41:47 fizzie, what do you actually use snmp for. Just status info? 16:43:50 it's not a version number 16:43:53 I don't use it, I just know these things. (To the bus now →) 16:43:58 sry 16:44:04 merry bus 16:44:19 it's busmas! 16:48:08 my back is killing me 16:49:36 The ADSL modem I have does traffic counters over SNMP, I used to have a mrtg-based traffic graph, but it was boring. 16:52:57 I'd be more interested in the negotiated line speeds (to monitor I'm getting my money's worth) but annoyingly that datum is not reported over SNMP, just a lot of useless junk. 16:55:36 -!- oerjan has quit (Quit: Later). 16:56:03 -!- lament has joined. 17:08:40 -!- tombom has joined. 17:10:38 -!- MigoMipo has joined. 17:49:54 fizzie, can you do any setting changes over snmp? 18:27:59 ais523, hi there, back in your old nick I see 18:28:10 about strange courses and other university issues 18:28:17 oh, I'm helping some people play NetHack 18:28:20 changing nick would confuse them 18:28:34 new nick? :o 18:29:06 ais523, I currently have a "module" in math that consists two sub-modules. Submodule two comes before submodule 1 18:29:11 I mean, in scheduling 18:29:12 heh 18:30:19 ais523, reason: they switched order of them before, but the confusing when trying to renumber them was too great. People taking a "omtenta" (not sure what it is in English, it is what you do when you fail at a test for a module, and have to do it again) ended up taking it for the wrong submodule and such 18:30:31 "retake" in english 18:30:43 of course, having module 2 before module 1 also causes all sorts of confusion for *new* students 18:31:29 apparently they are considering renaming them to A and B instead of 2 and 1, hoping that might cause less confusion 18:33:12 ais523, btw, know anyway to make that gvfs thing not claim the cd? It causes all sorts of issues when it mounts audio cds. At to moment the only way to eject an audio cd is sudo eject /dev/sr0 18:33:26 brb 18:33:34 AnMaster: no 19:04:35 -!- kar8nga has quit (Remote host closed the connection). 19:22:37 I have a question about Turing-completeness proofs. 19:24:17 -!- cheater2 has quit (Ping timeout: 240 seconds). 19:24:25 Let's say I have a language, let's call it L. L is based on some indisputably Turing-complete language, say Scheme, except it has a huge number of arbitrary constraints and restrictions placed on it. 19:24:34 cpressey! 19:24:35 hi 19:24:49 Hi lament :) 19:28:21 So anyway, L has a huge number of constraints on it. So many, in fact, that it's only possible to write 3 programs in L: Ackermann's function, Hunt the Wumpus, and a Kipple interpreter. 19:28:29 Is L Turing-complete? 19:29:21 Is Kipple? 19:29:37 Let's assume Kipple is TC. 19:29:45 Then yes. 19:29:59 er 19:30:06 of course it's not turing-complete 19:30:32 lament: Sure it is. It is evaluating a TC language, and therefore must be Turing-complete. 19:30:39 what therefore? 19:30:49 So you see why I asked :) 19:30:55 AnMaster: I think the ADSL box's SNMP bit is completely read-only, so no. Unless you're asking about the protocol in general, which does allow making configuration changes. 19:31:31 pikhq: that's like saying a box with an apple inside is an apple. 19:31:47 lament: No. It's like saying a box with an apple possesses an apple. 19:31:54 no. 19:32:51 Turing-complete means that it can evaluate a UTM and that a UTM can evaluate it. 19:33:02 A Kipple interpreter can be considered a UTM. 19:33:24 And I presume that L can be implemented on a TC system. 19:33:47 fizzie, it was in general 19:33:49 L is a subset of Scheme, and Scheme can be implemented on a TC system, so yes 19:34:06 cpressey: Then clearly L must be Turing-complete. 19:34:14 Scheme and Kipple of course just being concrete examples of TC languages, you could pick any you liked. 19:34:36 pikhq: a Kipple interpreter cannot be considered an UTM because it isn't. 19:34:46 well 19:34:59 pikhq: I might agree. But then, I would still have to say that there is still a sense in which L is not 'universal', because I can't write arbitrary programs in L. 19:35:06 lament: Is Kipple Turing-complete? 19:35:15 let's assume it is. 19:35:21 I can only write them in Kipple-interpreted-by-L. 19:35:25 lament: Then it is equivalent to a UTM. 19:35:27 isn't this like asking if HQ9+ extended with something like "b - interpret the rest of the code as brainfuck" is TC 19:35:29 I'm not sure it is 19:35:41 AnMaster: Sure it is. 19:35:47 AnMaster: sure, it is 19:35:53 hm 19:35:53 unlike L 19:35:59 why isn't L that then? 19:36:16 Sure, L could be that if you like. 19:36:19 because you can write arbitrary programs in HQ9+b but not in L 19:36:32 lament: You can? 19:36:35 lament: But you certainly can. 19:36:49 cpressey: "interpret the rest of the *code* as brainfuck"? Sure you can 19:36:52 I thought the point of HQ9+ was that you couldn't. If you can, it doesn't count. 19:37:03 lament, what about changing it to "interpret a file given as a command line argument to the HQ9+b interpreter as brainfuck" 19:37:07 rather than having it in the same file 19:37:09 lament: Ah, OK. 19:37:10 is it still tc? 19:37:12 AnMaster: right, then it's not TC 19:37:24 Sure it is. 19:37:39 It's just got two inputs for code. 19:37:46 true 19:37:56 you're confusing levels of abstraction 19:38:07 and that's bad 19:38:12 -!- Pthing has quit (Remote host closed the connection). 19:38:31 No, you're pretending there's a difference between a seperate file and an arbitrary string in the program. 19:38:32 I might agree that L is not TC, too, but then i'd still have to say that there is still a sense in which is it 'universal', because it can 'host' a single UTM (and that UTM could host any other UTM). 19:38:36 on the level of L, the kipple interpreter is just a single object; it doesn't have any properties since there're no operations on it 19:38:42 therefore, L is not TC 19:39:18 pikhq: well, either we're talking about L 19:39:27 lament: It's like having a TM with two tapes -- one of which is attached to a machine that can only pretend to be a specific UTM, the other is the tape for that machine. 19:39:31 or we're talking about Unix machine which has L in it, and you can also run the Kipple interpreter it produces 19:39:46 lament, what then if a language requires each command to be in a separate file. Lets say bf but you can only have one char in each file and it reads the files sequentially (according to file name in C locale sorting) to get the program 19:39:48 in the latter case, the device we're questioning the TCness of is not L, it's your Unix machine 19:39:49 is that then TC 19:39:54 and yes, your unix machine is TC 19:40:17 lament: ... 19:40:36 Here's another thing to consider: "For some input x, and some L program p, does p halt on x?" is undecidable (even though there are only 3 possibilities for p) 19:40:38 AnMaster: then the system comprised of the interpreter and a filesystem is TC 19:40:44 lament: But the L interpreter is simply reading a different tape for actually being universal rather than from the *same* tape. 19:40:54 pikhq: idgi 19:41:52 isn't there a multi-tape bf 19:42:06 with limited length of tapes but infinite number of tapes 19:42:19 There exists an interpreter for a Turing-complete language in L, therefore *L is Turing complete*. Quod erat demonstrandum. 19:43:10 One reason I brought this up is because there are lots of proofs of Turing-completeness out there that have the form "I wrote a UTM in this language, therefore this language is TC." If L isn't TC, then all those proofs are invalid. 19:43:28 ??????? 19:43:37 You would instead have to show that *any* UTM has a mapping to a program in the language. 19:43:38 cpressey: we need to look at the spirit of TC definition 19:43:46 where's it? 19:43:57 lament: Math doesn't have "spirt". 19:44:00 Spirit, even 19:44:01 is the rationale for def-n of TC being able to run any program? 19:44:05 pikhq yeah it does 19:44:16 pikhq: er, of course it does 19:44:55 Anyways. 19:44:55 I would say that this is the spirit of TCness (quoting Wikipedia): 19:44:56 "Two computers P and Q are called Turing equivalent if P can simulate Q and Q can simulate P." 19:44:58 "Church–Turing thesis states that if an algorithm (a procedure that terminates) exists then there is an equivalent Turing machine, recursively-definable function, or applicable λ-function, for that algorithm." 19:45:15 the reason turing machines are interesting is because they can run any algorithm 19:45:36 And L can run any algorithm. 19:45:43 sure it can't 19:45:49 *Kipple* can run any algorithm. 19:45:56 But Kipple can, and it can run any Kipple algorithm. 19:45:57 L can run any algorithm written in Kipple. 19:46:10 That statement was absurd, no? :) 19:46:21 i think so. 19:46:40 The computer L can simulate Kipple. And the computer Kipple (by merit of being TC) can simulate Scheme, a superset of L. 19:46:46 So L and Kipple are Turing-equivalent. 19:47:09 "The computer L" cannot print a list of primes 19:47:10 Since Kipple and any TC language are *also* Turing-equivalent... L is TC. 19:47:11 have anyone proved church turing thesis?? 19:47:17 lament: Yes it can. 19:47:22 lament: Well, it can, but only on the right input. 19:47:22 quantum physics is evidence for church turing isn't it 19:47:24 there exists an algorithm to print a list of primes, L cannot do it, therefore L is not TC 19:47:33 lament: But L can do it. 19:47:45 fine. L is TC then. 19:47:45 The computer L, given no input, cannot print a list of primes. 19:48:03 ok you win L is TC 19:48:04 lament you have be careful there because imagine a language that always printed HELLO when it started 19:48:21 it's cannot print hte list of primes without first printing HELLO, but it could still be TC 19:48:26 I have no problem saying L is TC, but then I have to think of TC as not telling you as much about a language as you might like to know. 19:48:34 in general... you have to worry about input/output interpretations 19:48:34 -!- Asztal has joined. 19:48:59 cpressey, either way this results in some issues for the esolang community as far as I can tell 19:49:02 MissPiggy: Church-Turing thesis is trivially proven. 19:49:02 cpressey: I agree with pikhq 19:49:07 what 19:49:12 cpressey: we just consider the input to be part of the program code 19:49:23 either TC doesn't really mean much, or a lot of the proofs are invalid 19:49:23 MissPiggy: See compilers. 19:49:26 cpressey: because what else can we consider it as? turing machines don't have IO 19:49:28 you might be thinking of a different theorem than me pikhq 19:49:37 cpressey: with that clarification, L is obviously TC 19:49:58 lament: Yes they do -- Tape. :P 19:50:07 what's your statement of it? 19:50:17 well yeah. 19:50:27 code = data .. 19:50:37 MissPiggy: If an algorithm exists, there exists an equivalent Turing machine for it. 19:50:47 pikhq and you know how to prove it?? 19:50:54 hm 19:51:08 it should be possible to write a brainfuck compiler in befunge93 btw 19:51:16 I have several algorithms for converting algorithms to Turing-complete languages. 19:51:22 :/ 19:51:23 I mean, it is trivial to compile it to unoptimised C 19:52:09 are you reading it as: if a turing machin exists, there exists an equivalent turing machine for it? 19:52:15 because that's now how I read it 19:54:11 MissPiggy: Turing machines aren't algorithms. 19:54:27 Though by the Church-Turing thesis, they can be equivalent to them. 19:54:40 okay I can't see what you mean really 19:54:42 Algorithms always halt, by many definitions. 19:57:41 what about 19:57:41 http://plato.stanford.edu/entries/church-turing/ 19:57:41 "Misunderstandings of the Thesis" 19:59:58 If an algorithm can be described, it can be described with a Turing machine, is how I take pikhq's statement. 20:00:31 Algorithms always halt, by many definitions. <-- oh? So anything that may go on forever (say, an algorithm over the natural numbers) wouldn't be an algorithm 20:00:36 that is, over all of them 20:01:09 AnMaster: Quite. 20:01:19 what do you can it then 20:01:32 ... English? 20:01:37 Please, speak English? 20:01:37 lol 20:02:43 har 20:02:45 AnMaster: Well, people seem to abuse the word "algorithm" a lot too. To me a heuristic is not an algorithm 20:03:12 Maybe there is an "algorithm" for interpreting brainfuck, even though it may never halt 20:03:19 eople abuse church turing 20:03:32 But I think someone famous (Knuth?) wrote a definition of algorithm, and "always halt" was in it. 20:03:49 cpressey, what about an algorithm for parsing a stream of unknown length, it would depend on the length of the stream 20:04:03 productive 20:04:09 if you define algorithms as processes that can be described by a turing-machine, then church-turing is trivially true 20:04:21 but that's not really how they're defined for the purposes of the thesis itself 20:04:28 lament yeah which is why I don't think that's a correct interpretation of church-turng 20:04:30 lament: More of a tautology, really. 20:04:31 yes 20:04:38 pikhq: right 20:04:42 the link I have given goes into this in some detail 20:04:46 now church and turing were pretty smart guys 20:04:51 ^^^^^^^^^^^^^^ 20:04:52 and they didn't think this was a tautology 20:05:02 lament you are really good at explaining 20:05:10 lament: More of a tautology, really. <-- a tautology is trivially true though 20:05:13 -!- gm|lap has joined. 20:05:13 ty 20:05:19 AnMasterXD 20:05:19 AnMaster: Well, of course. 20:05:32 AnMaster: That's a tautology right there. ;) 20:05:42 pikhq, quite 20:06:32 haha 20:06:35 I think the operative word in the Church-Turing stuff is "effective", which AFAICT has a specific meaning in the philosophy of mathematics. I think of it as close to "can be described." But that implies that the person doing the describing is using a particular language to describe it in, etc etc 20:06:48 '"a tautology is trivially true" is trivially true is a tautology' is trivially true 20:07:21 yeah like what if you happend upon a HALTING ORACLE one day 20:07:25 and you made a computer out of it 20:07:31 then turing machines aren't enough 20:07:38 MissPiggy, exactly 20:07:50 quantum computation IS turing equivalent though 20:07:56 MissPiggy: By merit of having a halting oracle, you're out of the realm of Turing machines. ;) 20:08:04 (in terms of /what/, but not in terms of algorithmic complexity) 20:08:13 And the halting oracle is like Bigfoot. No one's caught one, but they can't prove it's not out there somewhere. 20:08:13 so I think that gives EVIDENCE for Church-Turing 20:08:58 This is *math*, not science! 20:09:30 Church-Turing is philosophy, not math. 20:09:45 Turing-*complete* is math :) 20:10:13 I thought Church-Turing Thesis was philosophy 20:10:15 not really math ? 20:10:29 Somewhere in the math/philosophy overlap. 20:12:44 So if L is TC, what do we call the other property -- "I can express any algorithm directly in L, without relying on a particular input"? 20:13:50 Or "For each unique TM x, there is a unique L-program y, where x and y compute the same function." I think you have to say unique, otherwise you could just map all TMs to the same L program. 20:13:51 -!- oklopol has left (?). 20:13:58 -!- oklopol has joined. 20:14:06 argh 20:15:50 cpressey, hm... for the latter, if L allows some variable names to be changed or other such trivial things, then that isn't enough 20:16:07 AnMaster: Damn, you're right. 20:16:16 That would be rather humorous. 20:16:42 "cpressey: Is L Turing-complete?" <<< turing completeness doesn't have a definition, people disagree on cases like this; well, if you can make the kipple interpreter, make it run an arbitrary program, and redirect IO to it, then "obviously" you have a tc language, but i'm assuming you can just say interpret input as kipple or something. 20:16:48 cpressey, well yes, it could allow the function name and variable names to be changed, plus maybe the order of statements that doesn't depend on each other 20:17:48 oklopol, I think the known "sufficient" isn't equal to the known "necessary" for defining TC. At least that is my impression 20:17:57 thus the resulting disagreement 20:18:15 can you elaborate on that? 20:18:35 oklopol, I'm sure you are familiar with the phrase "necessary and sufficient"? 20:18:44 sure 20:19:04 well, we know some things are necessary for TC, everyone agrees on some minimums. 20:19:07 but what are the known necessaries and sufficients here 20:19:09 hmm 20:19:16 yeah i suppose 20:19:16 Also, we know some sufficient examples of them 20:19:25 it is just that we don't know the minimum sufficient set 20:19:54 oklopol, did that make it clearer? 20:20:20 yep 20:21:08 I get the impression Turing-complete had a good definition back when it was established in "recursive set theory" -- unfortunately, no one thinks in terms of recursive sets much anymore. 20:21:25 At least, not outside ivory towers. 20:21:36 cpressey: no, it really didn't 20:21:44 cpressey, oh? Also what exactly is recursive sets. It sounds like something that allows Russell's paradox 20:22:36 AnMaster: it means the set of languages that are recursive, the sets aren't recursive in any way 20:22:40 R 20:22:55 -!- ais523 has changed nick to scarf. 20:22:55 http://www.amazon.com/Recursively-Enumerable-Sets-Degrees-Perspectives/dp/0387152997 20:22:58 -!- scarf has changed nick to ais523. 20:23:05 oklopol, ah well, as long as we avoid mathematical barbers I'm happy ;) 20:23:06 -!- ais523 has changed nick to scarf. 20:23:09 -!- scarf has changed nick to ais523. 20:23:10 -!- ais523 has changed nick to scarf. 20:23:15 scarf, stop it 20:23:22 AnMaster: not deliberate, client bug 20:23:24 well freenode rate limits it 20:23:28 thank god for that 20:23:37 Yeah, "recursive set" is kind of a misnomer - the sets of values defined by recursive functions, is where i think it comes from 20:23:40 wow anmaster calm down 20:24:07 scarf, good 20:24:38 oklopol: I'd be surprised if it didn't have a fairly good definition w.r.t. sets. 20:24:52 R is the set of languages for which there it a tm that accepts them and always halts 20:25:02 RE is the set of languages for which there is a tm that accepts them 20:25:16 (halts on trues) 20:25:21 a language = a set of inputs? 20:25:38 Yes 20:25:46 as in a FSA? 20:26:08 cpressey, ^ 20:26:19 AnMaster: the language of such words that if you put them on the tape and run the tm, ... 20:26:28 As in, FSA accept certain languages (= sets of strings), yes. 20:26:38 ah same meaning of "language" then 20:26:39 right 20:27:37 why do you have to tell vlc what sort of disc you want to play? I mean, can't it check the reader and see "oops, that wasn't an audio cd, lets try a dvd..." 20:28:08 I thought in this context your set was "Turing-complete" if there was a surjection from your set onto RE 20:28:12 Or something like that 20:28:26 from what set? 20:28:28 uhu 20:28:59 is it a set that is turing complete, or a computational model? 20:29:31 (i've never heard the term in recursion theory context.d) 20:29:33 *-d 20:29:36 In recursive function theory, it's a set. But it can be the set of strings (= language) accepted by a computer. 20:30:30 In what I've read, it's only sets that can be TC. Through convenient abuse of terminology, computers "are" TC because they accept a TC set. 20:30:38 anyway, I would be interested in a good definition of this def that L is not a part in but languages like brainfuck, befunge98, and an UTM *are* part of 20:30:39 so, what kind of surjection exactly? there's a surjection from the naturals to RE. 20:30:43 err 20:30:49 well reals at laest 20:30:53 oklopol: I have no idea. I only half-remember this stuff. But it's in that book. 20:30:56 *reals 20:31:01 i see 20:31:19 cpressey, hm is L just TC or is it actually equivalent to an UTM or to lambda calculus or such? 20:31:30 I might have surjection wrong. But I don't think it's an isomorphism. It's very possible for an (uncomputable) set to be "more than" TC. 20:31:32 that might be the key to this (word trickery that is) 20:32:02 And of course, you'd never find the idea that TC applies to sets on TC's wikipedia page, because wikipedia doesn't work that way. :) 20:32:19 in any case, the original (turing's?) definition from what i've heard was that the inputs to the machine need to be finite + infinite amount of zeroes, that's another thing people disagree about (and much harder to fix) 20:32:21 cpressey, by the way, I don't think I ever seen any example of an uncomputable problem 20:32:47 AnMaster: um. Halting problem? 20:32:50 cpressey: i have no idea what an isomorphism is in this context 20:32:52 AnMaster, rendering the mandelbrot set 20:32:56 cpressey, oh duh 20:32:56 it's uncomputable 20:33:06 oklopol: one-to-one and onto? 20:33:12 MissPiggy, err? 20:33:12 that's a bijection 20:33:15 MissPiggy, how so? 20:33:21 AnMaster: but still semi-decidable :) 20:33:30 still that's just a question of cardinality, i don't see how that helps 20:33:31 MissPiggy, I mean, isn't that fractable one of the most popular ones arround 20:33:31 oklopol: Sorry, that was what I meant. 20:33:33 around* 20:33:38 cpressey, true 20:33:38 yes that's why I mentioned it 20:33:48 MissPiggy, so how can it then be uncomputable? 20:34:01 another thing that's uncomputable is solomonoff inductioon 20:34:12 cpressey: no worries, it's the isomorphism of the category Set 20:34:34 MissPiggy, "solomonoff inductioon"? 20:34:39 sure about that spelling? 20:35:19 :/ 20:35:20 what the fuck 20:35:28 that was obviously a typo 20:35:50 MissPiggy, right, I wasn't sure about the first being correctly spelt either 20:35:55 AnMaster: I'm not sure I've ever seen a non-contrived problem that wasn't even semi-decidable, although there are sets that aren't (but you can just construct those with intersection etc) 20:36:13 cpressey, hrrm 20:36:59 also I thought the halting problem was *undecidable* not *uncomputable* 20:36:59 There's a name for "not even semi-decidable" but I don't remember it. They start getting into capital greek letters with superscript numerals and stuff. 20:37:05 but maybe they are the same thing? 20:37:10 AnMaster: whether a tm does not halt with a given input is not in RE and therefore not in R either (it's obviously in co-RE though), whether it accepts everything is neither in RE nor co-RE 20:37:13 AnMaster: I think they are more or less the same thing. 20:37:46 hm okay 20:37:57 RE intersect co-RE, that's the "completely undecidable" set I was thinking of 20:38:06 It's been a while though. 20:38:29 cpressey: it's pretty non-contrived to check if a given first-order arithmetic formula if true 20:38:45 oklopol: But isn't that RE? 20:38:55 you can implement tm's in that easily, and obviously it's in RE iff it's in co-RE 20:39:03 so it can't be in either. 20:39:20 for a very non-obvious meaning of obvious, i suppose 20:39:53 hm 20:39:58 "cpressey: RE intersect co-RE, that's the "completely undecidable" set I was thinking of" <<< no that's R 20:40:05 the completely decidable set 20:40:14 oklopol: Indeed. 20:40:51 Still, I don't see how "check if a given first-order arithmetic formula is true" isn't in RE 20:41:00 Can't I enumerate them? 20:41:11 Check each one, if it's true, spit it out? 20:41:12 it sounds like equation solving? Or maybe I completely misread that 20:41:24 how do you check one? 20:41:24 If it runs forever, so be it? 20:41:37 the arithmetic formulas are first-order, they can quantify over integers 20:42:10 oklopol: Try all possible proofs of its truth nondeterministically? 20:42:31 and who says everything has a proof? 20:42:38 what exactly is a "first-order arithmetic formula" 20:42:42 in fact, this is one proof that there is no proof for everything 20:43:02 oklopol: Granted. 20:43:34 AnMaster: you have universal and existential quantification over integers, addition, multiplication and equality check, and then boolean operators. 20:43:57 AnMaster: For example: For all integers x, x * 1 = x. 20:44:19 oklopol, you mean like Exists x ( x * 2 = 4 ) ? 20:44:24 yes 20:44:25 I had forgotten how slippery those were :) 20:44:42 oklopol, well that is easy to prove. equation solving 20:44:50 and even it can 20:44:56 Still seems like you could enumerate the ones that do have proofs. 20:44:57 yeah, that one is easy to prove 20:45:05 can't* be solved exactly you can often solve them numerically afaik 20:45:12 at least for first order ones 20:45:15 numerically, huh 20:45:24 you did hear these are integers, right? 20:45:35 oklopol, is that first order as in "no differentiation"? 20:45:39 no 20:45:49 it's as in no quantification over more complicated things than numbers 20:46:33 differentiation is not very sensible with integers 20:48:20 differentation no foobars 20:48:24 oklopol: At any rate, I thought the definition of a set S being TC was that there was a mapping from every member of S onto every member of (I guess) RE. 20:48:52 do you realize that's just a matter of cardinalities? 20:49:02 Now that I typed it out, yes :) 20:49:06 i mean you can just take an arbitrary set that has the same amount of elements 20:49:26 so, i think we need a slightly different definition 20:49:41 So I'm misremembering it. Maybe it was "computable mapping", for some definition of "computable". 20:49:54 Turing-machine computable would be most likely 20:51:44 oklopol, ah okay 20:54:01 what is the cardinality of Q but with all the roots for each one appended. I guess it wouldn't be aleph_0 any more? 20:54:19 http://en.wikipedia.org/wiki/Turing_degree 20:54:22 all the roots? 20:54:39 MissPiggy, well yes, if you just had square root it would be trivial to match it up to Q 20:54:46 Turing complete = Turing degree 0' 20:54:52 with cube root and so on 20:55:00 then it would be much larger I suspect 20:55:03 oh well it's Q x N I guess 20:55:08 which is countable again 20:55:12 MissPiggy, oh? really? 20:55:23 Q x N because you can represent the n'th root of q as a pair: (q,n) 20:55:24 how would it be countable 20:55:43 because countable x countable is countable (cantors zig-zagonalization theorem) 20:55:44 MissPiggy, true, But do show where you would begin counting 20:55:52 hm 20:55:54 oh right 20:55:57 you could go like that 20:55:59 indeed 20:56:03 duh 20:57:35 "cpressey: But I think someone famous (Knuth?) wrote a definition of algorithm, and "always halt" was in it." <<< aocp starts with a definition of algorithm, then "of course we can never give an exact definition of an algorithm", then a description of a string rewriting system as a formal model. 20:58:17 (so first problem set has you writing stuff in thue, you gotta love aocp) 20:58:39 wow 20:58:44 I can't do ANYTHING with thue 20:58:50 I should get this book 20:59:14 Isn't set of algebraic numbers also countably infinite (and set of all integer roots of all rationals is strict subset)? 20:59:48 4. He's *Knuth*. 21:00:11 :( 21:00:24 Ilari: sure 21:00:48 well i don't get the part in parens 21:01:12 -!- pikhq has set topic: RIP sun.com | 4 days since last ehird sighting | 2 days since last alise sighting | http://tunes.org/~nef/logs/esoteric/?C=M;O=D. 21:01:23 unless by rationals you mean rational polynomials or something 21:01:29 oklopol, "aocp"? did you mean "taocp"? 21:01:35 i've heard aocp more 21:01:38 used to call it taocp 21:01:52 I call it The Art of Computer Programming. 21:02:58 oklopol, aocp took me a few seconds to figure out what it meant. And only managed it because Knuth was mentioned in there 21:02:59 fancy 21:03:26 AnMaster: i've used taocp and being told it's usually called aocp. 21:03:31 been 21:03:42 oklopol, I never heard aocp before. Often heard taocp though 21:04:11 well fuck 21:04:30 Actually, there are strict supersets of even algebraic numbers that are countably infinite (and those sets contain infinite number of numbers that are not algebraic). 21:04:50 computable reals are countable too 21:04:52 Ilari: no that's not true 21:05:13 and that set is equivalent wrt all first order theorems, I think (?) 21:05:14 you can just take say pi, and have a countable superset that does not contain an infinite number of numbers that are not algebraic 21:05:17 oklopol, googling: taocp gives relevant hits. aocp doesn't give any relevant hits 21:05:19 now if you want to to be a field... 21:05:27 only checked first result page for each 21:05:45 MissPiggy: Sure, sure; G"odel numbering of programs to compute them. 21:05:50 oklopol: Going over that Turing degree page, I do believe it was "a mapping computable by TM" (Turing-reducible) now. 21:05:53 pikhq, what was that? 21:05:53 AnMaster: okay, then maybe whoever told me to say aocp was a weird-ass weirdo. 21:05:57 pikhq, "o ? 21:06:10 at least it looked like that here 21:06:27 AnMaster: My attempt to type an umlaut. And didn't compose. 21:06:52 pikhq, also you don't need to compose, it has it's own letter in unicode 21:06:58 In fact, any field that is countably infinite and is strict superfield of algebraic numbers has infinite amount of numbers that are not algebraic. 21:07:07 AnMaster: The compose *key*. 21:07:09 Ilari: sure 21:07:20 pikhq, oh 21:07:30 pikhq, try: ö 21:07:32 that's obvious really, you can just take all its integer multiples or something 21:07:35 Type it and an appropriate sequence and it generates Unicode. 21:07:36 any sane keyboard layout has it 21:07:37 ;P 21:07:45 if one of them was an algebraic number, then the original would've been too 21:07:48 AnMaster: US-QWERTY doesn't. 21:07:56 pikhq, I know what compose is, I have it on my menu key 21:08:00 pikhq, I said sane 21:08:05 you don't even have altgr... 21:08:14 I've got compose on the Win key. 21:08:26 pikhq, don't mess with my super! 21:08:33 AnMaster: UNIX can treat the right AltGr just fine. 21:08:41 pikhq, well yes 21:08:41 Erm. Right Alt as AltGR. 21:09:23 interesting btw, tell me if you find a compose for ö 21:09:35 ah found it 21:09:37 "o 21:09:41 pikhq, just reverse the order of them 21:09:43 and it works 21:09:48 as in o" 21:10:05 AnMaster: I just didn't realise that my compose key doesn't work at all. :P 21:10:16 Take some TC language, add true real number datatype, infinite sum operator and polynomial root operator to it and one can compute all manners of numbers. 21:10:21 pikhq, oh? well then it isn't mapped there any more I guess ;P 21:10:30 I guess. 21:10:58 i do like the idea of "infinite sum operator" 21:11:12 maybe you could just have the "limit" keyword 21:11:18 Ilari, sounds like a CAS? 21:11:52 Just polynomial root operator plus fixed constants can be used to compute any algebraic number. Infinite sum operator can compute e, pi and those, etc... 21:12:15 Ilari: you are joking right? 21:12:20 Ilari, Taylor series? 21:12:29 infinite sum operator? 21:12:39 I don't beleive we've met 21:13:07 also obviously an infinite sum operator can compute also the algebraic numbers, you don't need the polynomial root operator 21:13:10 well, it makes perfect sense. It is just that it would be impossible to run any program in it I think 21:13:24 also does it take an infinite amount of rationals and sum them or what? 21:13:26 e = infinite_sum(1/n!,n=0...), pi = sqrt(6 * infinite_sum(1/n^2,n=1...)) 21:13:39 pi = sqrt(2) 21:13:43 Ilari: so it takes as input what exactly? 21:14:07 I wished this was all obvious to me 21:14:09 oklopol: One-argument function and lower bound. 21:14:16 one argument? 21:14:21 seems useful 21:14:21 and what's that argument 21:14:28 -!- scarf has changed nick to ais523. 21:14:36 an infinite set? 21:14:37 oklopol: lower bound, lower bound + 1, ... 21:14:50 Ilari, just use Σ and put a ∞ on top 21:14:58 what 21:15:05 idgi 21:15:09 If you take more sophisticated operations as primitives, you can consider more sophisticated sets computable. Surprise! :) 21:15:47 But one never reaches reals... 21:15:48 Now I think we have to argue about what operations are "obviously" the most primitive. 21:15:54 Ilari: why do you need infinite sums, why not just an operator that takes a cauchy sequence of rationals and returns the corresponding real? 21:16:36 so 21:17:10 e = infinite_sum(1/n!,n=0...) <<< clearly the sum takes, here, an infinite amount of inputs, i have no idea what you mean by "lower bound, lower bound + 1, ..." 21:17:21 well, or an infinite set anyway 21:18:04 oklopol: Lower bound is 0 there. 21:18:31 lower bound for e? 21:18:37 e < 2 21:18:58 then you have lower bound + 1, ..., so... you'll have 1 in there, then 2, 3, ...? 21:19:13 0, 1, 2, 3, 4, 5, 6, 7, 8... 21:19:29 and where exactly, i don't think you're being very clear 21:19:57 ohhhhh 21:19:58 while (true) n := n + 1 ??? 21:20:02 okay so 21:20:24 do you mean it takes a lower bound, and a function, then takes the infinite sum of f(lower bound), f(lower bound + 1), ...? 21:20:33 ahhhhh 21:20:53 "Ilari: oklopol: One-argument function and lower bound." <<< totally misinterpreted this, sorry 21:21:28 so, basically you just give it an infinite set of rationals, and it returns the corresponding real 21:21:45 but obviously you still get exactly the computable reals, because you have to express the set somehow 21:21:52 in your case with a function 21:24:22 and i don't see how the sum actually helps with anything, why not just give it a set of rationals and take their limit, or alternatively just give a function that returns one by one the digits of the real. 21:27:46 Statistics fun: Generate random numbers [0,1). Then map them by x -> 1/(1-x)². Calculate approximate expectation value. Heh, heh... 21:39:31 Complexity theory took the "-complete" terminology from computability theory and reused it for "NP-complete". A problem p is NP-complete iff every other problem in NP can be mapped to p by a polynomial-time algorithm. This comes from: A language L is Turing-complete (=RE-complete) iff every other language in RE can be mapped to L by a Turing machine. 21:40:29 So! 21:40:47 I think this means it is *not* enough to just say "There, I've coded a TM in my language, my language is TC." 21:41:06 Ilari the expected value is divergent? 21:41:13 I'm just guessing 21:41:16 But I'm not sure. 21:42:41 MissPiggy: The expectation value is "infinite". 21:42:49 * cpressey would be interested to hear what ais523 has to say about all this. 21:42:58 cpressey: haven't been paying attention 21:43:00 summary? 21:43:47 Is a language Turing-complete if I can only write one program in that language *but* that program is an interpreter for a different Turing-complete language? 21:43:51 okay 21:43:58 I don't know statistics :P 21:44:08 whichs sucks because I went to classes for it.. 21:44:29 MissPiggy: Some distributions are extremely ill-behaved. 21:45:06 cpressey: I smell a HQ9+ dialect 21:45:22 cpressey: yes, I think 21:49:27 ais523: Then what would you call the property "I can map any Turing-machine to a (meaningfully different) program in this language"? 21:49:50 hmm, rather than program + input, like TCness requires 21:50:14 MissPiggy: Things that can go wrong in statistics (#N+1, etc...): Assuming distribution to be normal when its not. Using formulas made for normal distribution with power laws, etc... 21:51:26 cpressey: I'm not sure that there is a name 21:51:30 although it's an interesting property 21:54:38 ais523: I've been trying to recall my studies in computability, and the definition of Turing-complete used in recursive function theory, and it sounds more like it's not literally Turing-complete. The ability to consider the input seems like a bit of a relaxation of the definition. Of course, I doubt I'm recalling it all accurately. 21:55:03 cpressey: I had a row with some of the world's best mathematicians on the subject as to this, and didn't really come to a conclusion 21:55:28 Indeed :) 21:56:11 we can put bounds on "definitely TC" and "definitely not TC", but there's a grey area 21:56:50 btw, I think I have a "fixed" version of Burro, and I think it is TC (or rather -- that I can code up arbitrary Turing machines in it :) ) 21:57:27 yay 21:57:35 Well, "property 2" does imply TC -- if I can map an arbitrary TM into a language, that language must contain at least one UTM 21:57:45 yep 21:57:51 "property 2" is a terrible name though 21:58:24 it has a kind-of ring to it 21:58:31 "Where do you live?" "Compound 3, property 2." 22:07:59 Oddball brainfuck derivates: IP space is 3x3x3xN tube. Placeable operators include set IP direction (uncoditional and conditional on current cell being nonzero). Crossing to middle does direction-dependent one of the 6 BF basic operations. 22:08:47 -!- SimonRC has quit (Ping timeout: 246 seconds). 22:13:29 tubes are cool. 22:18:02 * MissPiggy tubes lament 22:19:20 -!- SimonRC has joined. 22:22:46 -!- BeholdMyGlory has quit (Read error: Connection reset by peer). 22:27:45 -!- tombom has quit (Quit: Leaving). 22:33:28 -!- MigoMipo has quit (Remote host closed the connection). 23:09:13 -!- oerjan has joined. 23:19:34 what is the cardinality of Q but with all the roots for each one appended. I guess it wouldn't be aleph_0 any more? 23:19:56 the cardinality of the set of algebraic numbers is still aleph_0, if that's what you mean 23:20:15 there are only a countable number of polynomials, and a finite number of roots of each 23:20:24 he said "all the roots" though 23:20:26 *polynomials over the rationals 23:20:31 that's a lot of roots! 23:20:52 um the algebraic numbers _are_ all the roots of rational polynomials 23:21:00 essentially by definition 23:26:09 ais523: Then what would you call the property "I can map any Turing-machine to a (meaningfully different) program in this language"? 23:26:58 we were discussing the concept of output-completeness in relation to quines once. i think this would be a similar concept of input-completeness (or IO, if the TM had output) 23:27:32 basically both would have to do with not having to translate IO 23:28:07 (i don't recall those terms were official though, we may have just made them up on the spot) 23:29:10 of course given that TMs don't all have the same tape alphabet, it's still a bit wishy-washy to say you need no translation. although of course 2 letters is enough for a UTM 23:29:24 oerjan: I think you're talking about something largely different. 23:29:37 Should I write a BF interpreter in Haskell? (Yes, I know there is one already, but this is for my own education) 23:29:44 Alphabet doesn't enter into this problem at all that I can tell. 23:30:14 cpressey: um in that case i don't know what you mean 23:30:59 or maybe you mean that the program and input must be translated _separately_? 23:31:11 oerjan: I have a language, L. I can only write one program in L. *But* that program is an interpreter for ((insert your favorite Turing-complete language)). 23:31:11 remember, TMs take input on their tape, in their alphabet 23:31:19 oerjan: Is L Turing-complete? 23:31:52 you can write a computable reduction from any TM with input to an L program with input. 23:32:10 but scratch "input" from your statement, and you can't 23:32:34 but there are TC concepts with no input at all 23:32:52 you have to include input in the whole, otherwise TC makes no sense 23:33:07 e.g. a lambda calculus computation has no input 23:33:19 it's just a reduction of a term 23:33:54 Then, is it a function? What is its domain? 23:34:10 um what is a function? 23:34:22 A mapping from one set to another? 23:34:39 er ambiguous question 23:34:51 *um what are you asking whether is a function 23:34:54 Sorry. 23:35:01 Is your lambda term a function? 23:35:30 a lambda term is a string, at least that's one way of modeling them 23:35:46 cpressey: A "lambda term" is one way of *defining* a function. 23:36:00 That is, defining what "function" means. 23:36:22 pikhq: OK. What is the domain of the function defined by a lambda term? 23:36:29 pikhq: i think that confuses things even more 23:36:33 cpressey: ignore pikhq 23:36:38 Okay, then. 23:36:57 cpressey: Set of functions to set of functions? :P 23:37:00 Anyways. 23:37:05 a lambda function is a _symbolic_ term. that it can be interpreted as a function is irrelevant to the TC-ness of LC 23:37:07 Carry on, Oerjan. 23:37:54 a lambda term can be reduced using the alpha, beta, and if you want eta reductions 23:38:21 then you can ask whether this reduction can ever reach a given term, such as \x y -> x 23:38:36 (a common implementation of a boolean value) 23:39:08 One sec. 23:39:23 I just realized you never gave me a direct answer. Is L Turing-complete? 23:39:33 and that question is enough to make LC TC, because you can encode any turing machine computation (with yes/no answer) into the question of whether an LC term reduces to \x y -> x or \x y -> y 23:39:38 cpressey: i think so 23:41:04 For the record, I'm leaning towards: I don't think it is. 23:41:58 Now I'm all confused about lambda terms, and I don't know where to begin explaining why, though. 23:42:49 (i've been using haskell notation for the lambda terms btw) 23:43:35 I don't dispute that LC is TC, but how can a single lambda term be TC? To "encode the input into the term:" is a bit of a dodge, because now we're talking about a set of terms. 23:44:21 i didn't say a single lambda term was TC 23:44:41 Well, you said "but there are TC concepts with no input at all" -- what should I make of that? 23:45:06 cpressey: there are 23:45:13 you have a program that runs all turing machines in parallel 23:45:17 and report when each one halts 23:45:22 that's a UTM even without input 23:45:26 *and reports 23:45:38 O_o 23:46:35 cpressey: i was just presenting LC as an example of a TC concept without input 23:46:53 or rather, without input distinct from the program 23:48:08 See, that's where I'm starting to take exception. I think making that distinct between input and program is critical. Lambda calculus itself, for example, takes an "input" (a term to be reduced). If it didn't, it wouldn't be lamdba calculus. 23:48:08 of course lambda calculus makes it easy to encode program and input as two separate terms and apply one to the other, but that's not fundamental 23:48:36 cpressey: ah but L takes an input: a program + that program's input 23:49:11 oerjan: Yes. But L *requires* certain inputs to do certain things. Lambda terms, TMs, etc don't. 23:49:37 A TM can overwrite all of the input given to it with "hardcoded" stuff of its own choosing. L can't. 23:49:55 I mean, L programs can't. 23:49:58 the thing i am saying is that for TC-ness it is wrong to distinguish a part of input that is called the "program" 23:50:00 There's only one, and it can't. 23:51:33 cpressey: that's just because TMs are imperative with mutability. in fact for certain purposes (e.g. space use analysis) it is common to give the TM its initial input on a separate, read-only tape 23:51:37 cpressey: oh obviously RE-complete has a good definition. it's just that isn't a decent definition for turing-completeness 23:52:30 'k, I'm officially completely lost. 23:53:36 oklopol: Why not? 23:54:42 oerjan: What does the "that" in "that's just because..." refer to? 23:55:26 cpressey: that TMs can overwrite things - this is irrelevant to what they can _compute_ 23:56:05 that's just mechanics. 23:56:09 oerjan: My point was that there are TM's that act independent of their input. Overwriting it was just one example. They could also ignore it. 23:56:38 well sure but a TM that ignores its input is trivial, computationally 23:57:21 the computational content of a TM is its function from input tapes to final state, and possibly output tape 23:57:49 cpressey: because some people want more complex starting patterns than finite strings 23:58:00 i guess no other reason 23:58:09 for recursion theoretical purposes 23:58:39 oklopol: Fair enough, I suppose. I'll get back to you on that b/c I can only keep track of one discussion at a time :) 23:58:48 IO stuff is obviously another issue, but we can just ignore that completely i guess 23:59:00 or say it's part of the program 23:59:02 or something