00:00:15 <fizzie> And one Lindsay Tanner Swett, but I daresay that's not it.
00:00:41 <oerjan> oh wait it _is_ warrigal
00:01:26 <oerjan> uorygl: darn i thought it was just a moment ago you were 14 :D
00:02:58 <oerjan> 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 <fizzie> 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 <oerjan> 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 <uorygl> oerjan: indeed, I have joined university.
02:32:56 <uorygl> fizzie: there are three of me? Darn, what happened to my monopoly?
02:33:29 <oerjan> i think you failed to show up to your anti-trust proceedings, so there was a default judgement
02:33:52 <uorygl> 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 <oerjan> probably in your spam folder somewhere
02:34:22 -!- pikhq has quit (Read error: Connection reset by peer).
02:35:05 <uorygl> Anyway, I'm the white, fuzzy one.
02:35:35 <uorygl> Standing on a solar panel in outer space.
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 <augur> 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 <uorygl> augur: Grand Valley State.
03:47:42 -!- pikhq has joined.
03:48:20 <uorygl> Grand Valley State Universirty.
03:51:19 <oerjan> very gud speeling progarm
04:23:39 -!- zzo38 has joined.
04:24:34 <Gregor> I DONE GONE TUH UNIVERSIRTY
04:26:59 <zzo38> Can you please review my program to see if it is good?
04:27:10 <zzo38> Can you please review my program to see if it is good enough?
04:27:45 <zzo38> 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 <coppro> I hate my school board's internet connection
05:54:45 <coppro> 51 packets transmitted, 0 received, 100% packet loss, time 50254ms
05:59:06 <coppro> 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:41:52 -!- Pthing has joined.
06:52:57 <coppro> 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.
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.
13:05:23 <ais523> hmm, that was a bit slow
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 <oklopol> 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 <oerjan> <oklopol> 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 <fizzie> That looks like an OID, except not quite.
15:59:37 <fizzie> 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 <fizzie> 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 <fizzie> 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 <oerjan> well, to me that looks pretty out of hand too.
16:31:10 -!- MissPiggy has joined.
16:31:15 <AnMaster> oerjan, that version number, what is it for?
16:32:32 <oerjan> a joke, AnMaster, a joke
16:32:45 -!- MissPiggy has quit (Changing host).
16:32:45 -!- MissPiggy has joined.
16:32:46 <oerjan> or alternatively, ask oklopol not me
16:41:11 <AnMaster> oklopol, what is that version number for?
16:41:47 <AnMaster> fizzie, what do you actually use snmp for. Just status info?
16:43:53 <fizzie> I don't use it, I just know these things. (To the bus now →)
16:49:36 <fizzie> 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 <fizzie> 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 <AnMaster> fizzie, can you do any setting changes over snmp?
18:27:59 <AnMaster> ais523, hi there, back in your old nick I see
18:28:10 <AnMaster> about strange courses and other university issues
18:28:17 <ais523> oh, I'm helping some people play NetHack
18:28:20 <ais523> changing nick would confuse them
18:29:06 <AnMaster> ais523, I currently have a "module" in math that consists two sub-modules. Submodule two comes before submodule 1
18:30:19 <AnMaster> 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:43 <AnMaster> of course, having module 2 before module 1 also causes all sorts of confusion for *new* students
18:31:29 <AnMaster> apparently they are considering renaming them to A and B instead of 2 and 1, hoping that might cause less confusion
18:33:12 <AnMaster> 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
19:04:35 -!- kar8nga has quit (Remote host closed the connection).
19:22:37 <cpressey> I have a question about Turing-completeness proofs.
19:24:17 -!- cheater2 has quit (Ping timeout: 240 seconds).
19:24:25 <cpressey> 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:28:21 <cpressey> 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:30:06 <lament> of course it's not turing-complete
19:30:32 <pikhq> lament: Sure it is. It is evaluating a TC language, and therefore must be Turing-complete.
19:30:55 <fizzie> 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 <lament> pikhq: that's like saying a box with an apple inside is an apple.
19:31:47 <pikhq> lament: No. It's like saying a box with an apple possesses an apple.
19:32:51 <pikhq> Turing-complete means that it can evaluate a UTM and that a UTM can evaluate it.
19:33:02 <pikhq> A Kipple interpreter can be considered a UTM.
19:33:24 <pikhq> And I presume that L can be implemented on a TC system.
19:33:49 <cpressey> L is a subset of Scheme, and Scheme can be implemented on a TC system, so yes
19:34:06 <pikhq> cpressey: Then clearly L must be Turing-complete.
19:34:14 <cpressey> Scheme and Kipple of course just being concrete examples of TC languages, you could pick any you liked.
19:34:36 <lament> pikhq: a Kipple interpreter cannot be considered an UTM because it isn't.
19:34:59 <cpressey> 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 <pikhq> lament: Is Kipple Turing-complete?
19:35:21 <cpressey> I can only write them in Kipple-interpreted-by-L.
19:35:25 <pikhq> lament: Then it is equivalent to a UTM.
19:35:27 <AnMaster> isn't this like asking if HQ9+ extended with something like "b - interpret the rest of the code as brainfuck" is TC
19:35:41 <pikhq> AnMaster: Sure it is.
19:36:16 <cpressey> Sure, L could be that if you like.
19:36:19 <lament> because you can write arbitrary programs in HQ9+b but not in L
19:36:35 <pikhq> lament: But you certainly can.
19:36:49 <lament> cpressey: "interpret the rest of the *code* as brainfuck"? Sure you can
19:36:52 <cpressey> I thought the point of HQ9+ was that you couldn't. If you can, it doesn't count.
19:37:03 <AnMaster> 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 <AnMaster> rather than having it in the same file
19:37:12 <lament> AnMaster: right, then it's not TC
19:37:39 <pikhq> It's just got two inputs for code.
19:37:56 <lament> you're confusing levels of abstraction
19:38:12 -!- Pthing has quit (Remote host closed the connection).
19:38:31 <pikhq> No, you're pretending there's a difference between a seperate file and an arbitrary string in the program.
19:38:32 <cpressey> 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 <lament> 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 <lament> therefore, L is not TC
19:39:18 <lament> pikhq: well, either we're talking about L
19:39:27 <pikhq> 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 <lament> 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 <AnMaster> 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 <lament> in the latter case, the device we're questioning the TCness of is not L, it's your Unix machine
19:39:54 <lament> and yes, your unix machine is TC
19:40:36 <cpressey> 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 <lament> AnMaster: then the system comprised of the interpreter and a filesystem is TC
19:40:44 <pikhq> lament: But the L interpreter is simply reading a different tape for actually being universal rather than from the *same* tape.
19:42:06 <AnMaster> with limited length of tapes but infinite number of tapes
19:42:19 <pikhq> There exists an interpreter for a Turing-complete language in L, therefore *L is Turing complete*. Quod erat demonstrandum.
19:43:10 <cpressey> 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:37 <cpressey> You would instead have to show that *any* UTM has a mapping to a program in the language.
19:43:38 <lament> cpressey: we need to look at the spirit of TC definition
19:43:57 <pikhq> lament: Math doesn't have "spirt".
19:44:01 <lament> is the rationale for def-n of TC being able to run any program?
19:44:16 <lament> pikhq: er, of course it does
19:44:55 <lament> I would say that this is the spirit of TCness (quoting Wikipedia):
19:44:56 <pikhq> "Two computers P and Q are called Turing equivalent if P can simulate Q and Q can simulate P."
19:44:58 <lament> "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 <lament> the reason turing machines are interesting is because they can run any algorithm
19:45:36 <pikhq> And L can run any algorithm.
19:45:49 <lament> *Kipple* can run any algorithm.
19:45:56 <pikhq> But Kipple can, and it can run any Kipple algorithm.
19:45:57 <cpressey> L can run any algorithm written in Kipple.
19:46:10 <cpressey> That statement was absurd, no? :)
19:46:40 <pikhq> 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 <pikhq> So L and Kipple are Turing-equivalent.
19:47:09 <lament> "The computer L" cannot print a list of primes
19:47:10 <pikhq> Since Kipple and any TC language are *also* Turing-equivalent... L is TC.
19:47:11 <MissPiggy> have anyone proved church turing thesis??
19:47:17 <pikhq> lament: Yes it can.
19:47:22 <cpressey> lament: Well, it can, but only on the right input.
19:47:22 <MissPiggy> quantum physics is evidence for church turing isn't it
19:47:24 <lament> there exists an algorithm to print a list of primes, L cannot do it, therefore L is not TC
19:47:33 <pikhq> lament: But L can do it.
19:47:45 <cpressey> The computer L, given no input, cannot print a list of primes.
19:48:04 <MissPiggy> lament you have be careful there because imagine a language that always printed HELLO when it started
19:48:21 <MissPiggy> it's cannot print hte list of primes without first printing HELLO, but it could still be TC
19:48:26 <cpressey> 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 <MissPiggy> in general... you have to worry about input/output interpretations
19:48:34 -!- Asztal has joined.
19:48:59 <AnMaster> cpressey, either way this results in some issues for the esolang community as far as I can tell
19:49:02 <pikhq> MissPiggy: Church-Turing thesis is trivially proven.
19:49:02 <lament> cpressey: I agree with pikhq
19:49:12 <lament> cpressey: we just consider the input to be part of the program code
19:49:23 <AnMaster> either TC doesn't really mean much, or a lot of the proofs are invalid
19:49:23 <pikhq> MissPiggy: See compilers.
19:49:26 <lament> cpressey: because what else can we consider it as? turing machines don't have IO
19:49:28 <MissPiggy> you might be thinking of a different theorem than me pikhq
19:49:37 <lament> cpressey: with that clarification, L is obviously TC
19:49:58 <pikhq> lament: Yes they do -- Tape. :P
19:50:37 <pikhq> MissPiggy: If an algorithm exists, there exists an equivalent Turing machine for it.
19:50:47 <MissPiggy> pikhq and you know how to prove it??
19:51:08 <AnMaster> it should be possible to write a brainfuck compiler in befunge93 btw
19:51:16 <pikhq> I have several algorithms for converting algorithms to Turing-complete languages.
19:51:23 <AnMaster> I mean, it is trivial to compile it to unoptimised C
19:52:09 <MissPiggy> are you reading it as: if a turing machin exists, there exists an equivalent turing machine for it?
19:54:11 <pikhq> MissPiggy: Turing machines aren't algorithms.
19:54:27 <pikhq> Though by the Church-Turing thesis, they can be equivalent to them.
19:54:40 <MissPiggy> okay I can't see what you mean really
19:54:42 <cpressey> Algorithms always halt, by many definitions.
19:57:41 <MissPiggy> http://plato.stanford.edu/entries/church-turing/
19:59:58 <cpressey> If an algorithm can be described, it can be described with a Turing machine, is how I take pikhq's statement.
20:00:31 <AnMaster> <cpressey> 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:01:37 <pikhq> Please, speak English?
20:02:45 <cpressey> AnMaster: Well, people seem to abuse the word "algorithm" a lot too. To me a heuristic is not an algorithm
20:03:12 <cpressey> Maybe there is an "algorithm" for interpreting brainfuck, even though it may never halt
20:03:32 <cpressey> But I think someone famous (Knuth?) wrote a definition of algorithm, and "always halt" was in it.
20:03:49 <AnMaster> cpressey, what about an algorithm for parsing a stream of unknown length, it would depend on the length of the stream
20:04:09 <lament> if you define algorithms as processes that can be described by a turing-machine, then church-turing is trivially true
20:04:21 <lament> but that's not really how they're defined for the purposes of the thesis itself
20:04:28 <MissPiggy> lament yeah which is why I don't think that's a correct interpretation of church-turng
20:04:30 <pikhq> lament: More of a tautology, really.
20:04:42 <MissPiggy> the link I have given goes into this in some detail
20:04:46 <lament> now church and turing were pretty smart guys
20:04:52 <lament> and they didn't think this was a tautology
20:05:02 <MissPiggy> lament you are really good at explaining
20:05:10 <AnMaster> <pikhq> lament: More of a tautology, really. <-- a tautology is trivially true though
20:05:13 -!- gm|lap has joined.
20:05:19 <pikhq> AnMaster: Well, of course.
20:05:32 <pikhq> AnMaster: That's a tautology right there. ;)
20:06:35 <cpressey> 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 <MissPiggy> '"a tautology is trivially true" is trivially true is a tautology' is trivially true
20:07:21 <MissPiggy> yeah like what if you happend upon a HALTING ORACLE one day
20:07:31 <MissPiggy> then turing machines aren't enough
20:07:50 <MissPiggy> quantum computation IS turing equivalent though
20:07:56 <pikhq> MissPiggy: By merit of having a halting oracle, you're out of the realm of Turing machines. ;)
20:08:04 <MissPiggy> (in terms of /what/, but not in terms of algorithmic complexity)
20:08:13 <cpressey> 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 <MissPiggy> so I think that gives EVIDENCE for Church-Turing
20:08:58 <pikhq> This is *math*, not science!
20:09:30 <cpressey> Church-Turing is philosophy, not math.
20:10:13 <MissPiggy> I thought Church-Turing Thesis was philosophy
20:10:29 <pikhq> Somewhere in the math/philosophy overlap.
20:12:44 <cpressey> 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 <cpressey> 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:15:50 <AnMaster> 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:16 <cpressey> That would be rather humorous.
20:16:42 <oklopol> "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 <AnMaster> 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 <AnMaster> 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 <AnMaster> thus the resulting disagreement
20:18:15 <oklopol> can you elaborate on that?
20:18:35 <AnMaster> oklopol, I'm sure you are familiar with the phrase "necessary and sufficient"?
20:19:04 <AnMaster> well, we know some things are necessary for TC, everyone agrees on some minimums.
20:19:07 <oklopol> but what are the known necessaries and sufficients here
20:19:16 <AnMaster> Also, we know some sufficient examples of them
20:19:25 <AnMaster> it is just that we don't know the minimum sufficient set
20:19:54 <AnMaster> oklopol, did that make it clearer?
20:21:08 <cpressey> 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 <cpressey> At least, not outside ivory towers.
20:21:36 <oklopol> cpressey: no, it really didn't
20:21:44 <AnMaster> cpressey, oh? Also what exactly is recursive sets. It sounds like something that allows Russell's paradox
20:22:36 <oklopol> AnMaster: it means the set of languages that are recursive, the sets aren't recursive in any way
20:22:55 -!- ais523 has changed nick to scarf.
20:22:55 <cpressey> http://www.amazon.com/Recursively-Enumerable-Sets-Degrees-Perspectives/dp/0387152997
20:22:58 -!- scarf has changed nick to ais523.
20:23:05 <AnMaster> 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:22 <scarf> AnMaster: not deliberate, client bug
20:23:37 <cpressey> Yeah, "recursive set" is kind of a misnomer - the sets of values defined by recursive functions, is where i think it comes from
20:24:38 <cpressey> oklopol: I'd be surprised if it didn't have a fairly good definition w.r.t. sets.
20:24:52 <oklopol> R is the set of languages for which there it a tm that accepts them and always halts
20:25:02 <oklopol> RE is the set of languages for which there is a tm that accepts them
20:26:19 <oklopol> AnMaster: the language of such words that if you put them on the tape and run the tm, ...
20:26:28 <cpressey> As in, FSA accept certain languages (= sets of strings), yes.
20:26:38 <AnMaster> ah same meaning of "language" then
20:27:37 <AnMaster> 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 <cpressey> I thought in this context your set was "Turing-complete" if there was a surjection from your set onto RE
20:28:59 <oklopol> is it a set that is turing complete, or a computational model?
20:29:31 <oklopol> (i've never heard the term in recursion theory context.d)
20:29:36 <cpressey> In recursive function theory, it's a set. But it can be the set of strings (= language) accepted by a computer.
20:30:30 <cpressey> 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 <AnMaster> 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 <oklopol> so, what kind of surjection exactly? there's a surjection from the naturals to RE.
20:30:53 <cpressey> oklopol: I have no idea. I only half-remember this stuff. But it's in that book.
20:31:19 <AnMaster> cpressey, hm is L just TC or is it actually equivalent to an UTM or to lambda calculus or such?
20:31:30 <cpressey> 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 <AnMaster> that might be the key to this (word trickery that is)
20:32:02 <cpressey> 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 <oklopol> 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 <AnMaster> cpressey, by the way, I don't think I ever seen any example of an uncomputable problem
20:32:47 <cpressey> AnMaster: um. Halting problem?
20:32:50 <oklopol> cpressey: i have no idea what an isomorphism is in this context
20:32:52 <MissPiggy> AnMaster, rendering the mandelbrot set
20:33:21 <cpressey> AnMaster: but still semi-decidable :)
20:33:30 <oklopol> still that's just a question of cardinality, i don't see how that helps
20:33:31 <AnMaster> MissPiggy, I mean, isn't that fractable one of the most popular ones arround
20:33:31 <cpressey> oklopol: Sorry, that was what I meant.
20:33:48 <AnMaster> MissPiggy, so how can it then be uncomputable?
20:34:01 <MissPiggy> another thing that's uncomputable is solomonoff inductioon
20:34:12 <oklopol> cpressey: no worries, it's the isomorphism of the category Set
20:34:34 <AnMaster> MissPiggy, "solomonoff inductioon"?
20:35:50 <AnMaster> MissPiggy, right, I wasn't sure about the first being correctly spelt either
20:35:55 <cpressey> 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:59 <AnMaster> also I thought the halting problem was *undecidable* not *uncomputable*
20:36:59 <cpressey> 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 <AnMaster> but maybe they are the same thing?
20:37:10 <oklopol> 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 <cpressey> AnMaster: I think they are more or less the same thing.
20:37:57 <cpressey> RE intersect co-RE, that's the "completely undecidable" set I was thinking of
20:38:29 <oklopol> cpressey: it's pretty non-contrived to check if a given first-order arithmetic formula if true
20:38:55 <oklopol> you can implement tm's in that easily, and obviously it's in RE iff it's in co-RE
20:39:20 <oklopol> for a very non-obvious meaning of obvious, i suppose
20:39:58 <oklopol> "cpressey: RE intersect co-RE, that's the "completely undecidable" set I was thinking of" <<< no that's R
20:40:05 <oklopol> the completely decidable set
20:40:51 <cpressey> Still, I don't see how "check if a given first-order arithmetic formula is true" isn't in RE
20:41:11 <cpressey> Check each one, if it's true, spit it out?
20:41:12 <AnMaster> it sounds like equation solving? Or maybe I completely misread that
20:41:37 <oklopol> the arithmetic formulas are first-order, they can quantify over integers
20:42:10 <cpressey> oklopol: Try all possible proofs of its truth nondeterministically?
20:42:31 <oklopol> and who says everything has a proof?
20:42:38 <AnMaster> what exactly is a "first-order arithmetic formula"
20:42:42 <oklopol> in fact, this is one proof that there is no proof for everything
20:43:34 <oklopol> AnMaster: you have universal and existential quantification over integers, addition, multiplication and equality check, and then boolean operators.
20:43:57 <cpressey> AnMaster: For example: For all integers x, x * 1 = x.
20:44:19 <AnMaster> oklopol, you mean like Exists x ( x * 2 = 4 ) ?
20:44:25 <cpressey> I had forgotten how slippery those were :)
20:44:42 <AnMaster> oklopol, well that is easy to prove. equation solving
20:44:56 <cpressey> Still seems like you could enumerate the ones that do have proofs.
20:44:57 <oklopol> yeah, that one is easy to prove
20:45:05 <AnMaster> can't* be solved exactly you can often solve them numerically afaik
20:45:24 <oklopol> you did hear these are integers, right?
20:45:35 <AnMaster> oklopol, is that first order as in "no differentiation"?
20:45:49 <oklopol> it's as in no quantification over more complicated things than numbers
20:46:33 <oklopol> differentiation is not very sensible with integers
20:48:24 <cpressey> 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 <oklopol> do you realize that's just a matter of cardinalities?
20:49:02 <cpressey> Now that I typed it out, yes :)
20:49:06 <oklopol> i mean you can just take an arbitrary set that has the same amount of elements
20:49:26 <oklopol> so, i think we need a slightly different definition
20:49:41 <cpressey> So I'm misremembering it. Maybe it was "computable mapping", for some definition of "computable".
20:49:54 <cpressey> Turing-machine computable would be most likely
20:54:01 <AnMaster> 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 <cpressey> http://en.wikipedia.org/wiki/Turing_degree
20:54:39 <AnMaster> MissPiggy, well yes, if you just had square root it would be trivial to match it up to Q
20:54:46 <cpressey> Turing complete = Turing degree 0'
20:55:00 <AnMaster> then it would be much larger I suspect
20:55:23 <MissPiggy> Q x N because you can represent the n'th root of q as a pair: (q,n)
20:55:43 <MissPiggy> because countable x countable is countable (cantors zig-zagonalization theorem)
20:55:44 <AnMaster> MissPiggy, true, But do show where you would begin counting
20:57:35 <oklopol> "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 <oklopol> (so first problem set has you writing stuff in thue, you gotta love aocp)
20:59:14 <Ilari> Isn't set of algebraic numbers also countably infinite (and set of all integer roots of all rationals is strict subset)?
21:00:48 <oklopol> 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 <oklopol> unless by rationals you mean rational polynomials or something
21:01:29 <AnMaster> oklopol, "aocp"? did you mean "taocp"?
21:01:52 <pikhq> I call it The Art of Computer Programming.
21:02:58 <AnMaster> oklopol, aocp took me a few seconds to figure out what it meant. And only managed it because Knuth was mentioned in there
21:03:26 <oklopol> AnMaster: i've used taocp and being told it's usually called aocp.
21:03:42 <AnMaster> oklopol, I never heard aocp before. Often heard taocp though
21:04:30 <Ilari> 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 <MissPiggy> computable reals are countable too
21:05:13 <MissPiggy> and that set is equivalent wrt all first order theorems, I think (?)
21:05:14 <oklopol> 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 <AnMaster> oklopol, googling: taocp gives relevant hits. aocp doesn't give any relevant hits
21:05:19 <oklopol> now if you want to to be a field...
21:05:27 <AnMaster> only checked first result page for each
21:05:45 <pikhq> MissPiggy: Sure, sure; G"odel numbering of programs to compute them.
21:05:50 <cpressey> oklopol: Going over that Turing degree page, I do believe it was "a mapping computable by TM" (Turing-reducible) now.
21:05:53 <oklopol> AnMaster: okay, then maybe whoever told me to say aocp was a weird-ass weirdo.
21:06:10 <AnMaster> at least it looked like that here
21:06:27 <pikhq> AnMaster: My attempt to type an umlaut. And didn't compose.
21:06:52 <AnMaster> pikhq, also you don't need to compose, it has it's own letter in unicode
21:06:58 <Ilari> 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 <pikhq> AnMaster: The compose *key*.
21:07:32 <oklopol> that's obvious really, you can just take all its integer multiples or something
21:07:35 <pikhq> Type it and an appropriate sequence and it generates Unicode.
21:07:36 <AnMaster> any sane keyboard layout has it
21:07:45 <oklopol> if one of them was an algebraic number, then the original would've been too
21:07:48 <pikhq> AnMaster: US-QWERTY doesn't.
21:07:56 <AnMaster> pikhq, I know what compose is, I have it on my menu key
21:08:14 <pikhq> I've got compose on the Win key.
21:08:26 <AnMaster> pikhq, don't mess with my super!
21:08:33 <pikhq> AnMaster: UNIX can treat the right AltGr just fine.
21:08:41 <pikhq> Erm. Right Alt as AltGR.
21:09:23 <AnMaster> interesting btw, tell me if you find a compose for ö
21:09:41 <AnMaster> pikhq, just reverse the order of them
21:10:05 <pikhq> AnMaster: I just didn't realise that my compose key doesn't work at all. :P
21:10:16 <Ilari> 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 <AnMaster> pikhq, oh? well then it isn't mapped there any more I guess ;P
21:10:58 <oklopol> i do like the idea of "infinite sum operator"
21:11:12 <oklopol> maybe you could just have the "limit" keyword
21:11:52 <Ilari> 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 <oklopol> Ilari: you are joking right?
21:13:07 <oklopol> also obviously an infinite sum operator can compute also the algebraic numbers, you don't need the polynomial root operator
21:13:10 <AnMaster> well, it makes perfect sense. It is just that it would be impossible to run any program in it I think
21:13:24 <oklopol> also does it take an infinite amount of rationals and sum them or what?
21:13:26 <Ilari> e = infinite_sum(1/n!,n=0...), pi = sqrt(6 * infinite_sum(1/n^2,n=1...))
21:13:43 <oklopol> Ilari: so it takes as input what exactly?
21:14:07 <olsner> I wished this was all obvious to me
21:14:09 <Ilari> oklopol: One-argument function and lower bound.
21:14:28 -!- scarf has changed nick to ais523.
21:14:37 <Ilari> oklopol: lower bound, lower bound + 1, ...
21:14:50 <AnMaster> Ilari, just use Σ and put a ∞ on top
21:15:09 <cpressey> If you take more sophisticated operations as primitives, you can consider more sophisticated sets computable. Surprise! :)
21:15:47 <Ilari> But one never reaches reals...
21:15:48 <cpressey> Now I think we have to argue about what operations are "obviously" the most primitive.
21:15:54 <oklopol> 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:17:10 <oklopol> 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 <oklopol> well, or an infinite set anyway
21:18:04 <Ilari> oklopol: Lower bound is 0 there.
21:18:58 <oklopol> then you have lower bound + 1, ..., so... you'll have 1 in there, then 2, 3, ...?
21:19:13 <Ilari> 0, 1, 2, 3, 4, 5, 6, 7, 8...
21:19:29 <oklopol> and where exactly, i don't think you're being very clear
21:20:24 <oklopol> 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:53 <oklopol> "Ilari: oklopol: One-argument function and lower bound." <<< totally misinterpreted this, sorry
21:21:28 <oklopol> so, basically you just give it an infinite set of rationals, and it returns the corresponding real
21:21:45 <oklopol> but obviously you still get exactly the computable reals, because you have to express the set somehow
21:21:52 <oklopol> in your case with a function
21:24:22 <oklopol> 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 <Ilari> Statistics fun: Generate random numbers [0,1). Then map them by x -> 1/(1-x)². Calculate approximate expectation value. Heh, heh...
21:39:31 <cpressey> 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:47 <cpressey> 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 <MissPiggy> Ilari the expected value is divergent?
21:42:41 <Ilari> 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 <ais523> cpressey: haven't been paying attention
21:43:47 <cpressey> 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:44:08 <MissPiggy> whichs sucks because I went to classes for it..
21:44:29 <Ilari> MissPiggy: Some distributions are extremely ill-behaved.
21:45:06 <olsner> cpressey: I smell a HQ9+ dialect
21:45:22 <ais523> cpressey: yes, I think
21:49:27 <cpressey> 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 <ais523> hmm, rather than program + input, like TCness requires
21:50:14 <Ilari> 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 <ais523> cpressey: I'm not sure that there is a name
21:51:30 <ais523> although it's an interesting property
21:54:38 <cpressey> 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 <ais523> 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:56:11 <ais523> we can put bounds on "definitely TC" and "definitely not TC", but there's a grey area
21:56:50 <cpressey> 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:35 <cpressey> 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:51 <cpressey> "property 2" is a terrible name though
21:58:24 <ais523> it has a kind-of ring to it
21:58:31 <Gregor> "Where do you live?" "Compound 3, property 2."
22:07:59 <Ilari> 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: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 <oerjan> <AnMaster> 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 <oerjan> the cardinality of the set of algebraic numbers is still aleph_0, if that's what you mean
23:20:15 <oerjan> there are only a countable number of polynomials, and a finite number of roots of each
23:20:24 <lament> he said "all the roots" though
23:20:26 <oerjan> *polynomials over the rationals
23:20:31 <lament> that's a lot of roots!
23:20:52 <oerjan> um the algebraic numbers _are_ all the roots of rational polynomials
23:21:00 <oerjan> essentially by definition
23:26:09 <oerjan> <cpressey> 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 <oerjan> 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 <oerjan> basically both would have to do with not having to translate IO
23:28:07 <oerjan> (i don't recall those terms were official though, we may have just made them up on the spot)
23:29:10 <oerjan> 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 <cpressey> oerjan: I think you're talking about something largely different.
23:29:37 <Sgeo_> 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 <cpressey> Alphabet doesn't enter into this problem at all that I can tell.
23:30:14 <oerjan> cpressey: um in that case i don't know what you mean
23:30:59 <oerjan> or maybe you mean that the program and input must be translated _separately_?
23:31:11 <cpressey> 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 <oerjan> remember, TMs take input on their tape, in their alphabet
23:31:52 <oerjan> you can write a computable reduction from any TM with input to an L program with input.
23:32:10 <cpressey> but scratch "input" from your statement, and you can't
23:32:34 <oerjan> but there are TC concepts with no input at all
23:32:52 <oerjan> you have to include input in the whole, otherwise TC makes no sense
23:33:07 <oerjan> e.g. a lambda calculus computation has no input
23:33:19 <oerjan> it's just a reduction of a term
23:33:54 <cpressey> Then, is it a function? What is its domain?
23:34:10 <oerjan> um what is a function?
23:34:22 <cpressey> A mapping from one set to another?
23:34:51 <oerjan> *um what are you asking whether is a function
23:35:01 <cpressey> Is your lambda term a function?
23:35:30 <oerjan> a lambda term is a string, at least that's one way of modeling them
23:35:46 <pikhq> cpressey: A "lambda term" is one way of *defining* a function.
23:36:00 <pikhq> That is, defining what "function" means.
23:36:22 <cpressey> pikhq: OK. What is the domain of the function defined by a lambda term?
23:36:29 <oerjan> pikhq: i think that confuses things even more
23:36:33 <oerjan> cpressey: ignore pikhq
23:36:57 <pikhq> cpressey: Set of functions to set of functions? :P
23:37:05 <oerjan> 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:54 <oerjan> a lambda term can be reduced using the alpha, beta, and if you want eta reductions
23:38:21 <oerjan> then you can ask whether this reduction can ever reach a given term, such as \x y -> x
23:38:36 <oerjan> (a common implementation of a boolean value)
23:39:23 <cpressey> I just realized you never gave me a direct answer. Is L Turing-complete?
23:39:33 <oerjan> 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:41:04 <cpressey> For the record, I'm leaning towards: I don't think it is.
23:41:58 <cpressey> Now I'm all confused about lambda terms, and I don't know where to begin explaining why, though.
23:42:49 <oerjan> (i've been using haskell notation for the lambda terms btw)
23:43:35 <cpressey> 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 <oerjan> i didn't say a single lambda term was TC
23:44:41 <cpressey> Well, you said "but there are TC concepts with no input at all" -- what should I make of that?
23:45:13 <ais523> you have a program that runs all turing machines in parallel
23:45:17 <ais523> and report when each one halts
23:45:22 <ais523> that's a UTM even without input
23:46:35 <oerjan> cpressey: i was just presenting LC as an example of a TC concept without input
23:46:53 <oerjan> or rather, without input distinct from the program
23:48:08 <cpressey> 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 <oerjan> 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 <oerjan> cpressey: ah but L takes an input: a program + that program's input
23:49:11 <cpressey> oerjan: Yes. But L *requires* certain inputs to do certain things. Lambda terms, TMs, etc don't.
23:49:37 <cpressey> A TM can overwrite all of the input given to it with "hardcoded" stuff of its own choosing. L can't.
23:49:58 <oerjan> 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 <cpressey> There's only one, and it can't.
23:51:33 <oerjan> 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 <oklopol> cpressey: oh obviously RE-complete has a good definition. it's just that isn't a decent definition for turing-completeness
23:52:30 <cpressey> 'k, I'm officially completely lost.
23:54:42 <cpressey> oerjan: What does the "that" in "that's just because..." refer to?
23:55:26 <oerjan> cpressey: that TMs can overwrite things - this is irrelevant to what they can _compute_
23:56:05 <oerjan> that's just mechanics.
23:56:09 <cpressey> 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 <oerjan> well sure but a TM that ignores its input is trivial, computationally
23:57:21 <oerjan> the computational content of a TM is its function from input tapes to final state, and possibly output tape
23:57:49 <oklopol> cpressey: because some people want more complex starting patterns than finite strings
23:58:09 <oklopol> for recursion theoretical purposes
23:58:39 <cpressey> 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 <oklopol> IO stuff is obviously another issue, but we can just ignore that completely i guess
23:59:00 <oklopol> or say it's part of the program