00:00:33 oerjan: If a TM that ignores its input is "computationally trivial", are all lambda terms "computationally trivial" as well? 00:01:04 cpressey: to be honest i don't know that i've ever seen a clear and unambiguous definition of turing-completeness once you go beyond languages of strings. the wikipedia article is certainly not one. 00:01:43 oerjan: Turing-equivalent with a Turing machine? 00:01:48 but based on other subjects i've read, i.e. complexity theory, my intuition says it is all about _reductions_ from one notion of computation to another 00:01:49 oerjan: The Wikipedia page on Turing degrees is a bit better. 00:02:19 (P and Q are said to be Turing-equivalent if one can simulate P with Q and Q with P.) 00:02:56 pikhq: but that sentence completely ignores the very I/O question which in my view is the reason for the confusing discussion i and cpressey are now having 00:03:14 it is not a _mathematical_ definition 00:03:16 oerjan: I quite agree. But the literature on reductions doesn't seem to say what to do with input. I'm sure I can map every TM to (some L program, some input). I'm equally sure I can't map every TM to (some L program). 00:03:46 oerjan: Clearly one can simply consider input and output as two one-way tapes. Help at all? 00:04:40 s/map/find a TM which maps/ (Turing-reduction) 00:04:43 cpressey: the thing is that most things you are reducing, such as NP-complete problems, don't have a program part. you are reducing input to input 00:05:04 e.g. a graph to a boolean expression 00:07:01 (for hamiltonian circuit -> SAT, e.g.) 00:07:11 Yes, but from what I know, the "-complete" in "NP-complete" was adapted from the "-complete" in "Turing-complete" (polytime reductions instead of Turing reductions.) 00:07:25 Anyway -- for the sake of argument say L is Turing-complete 00:07:43 Then the original question you answered is put into context 00:07:46 cpressey: and the RE theory simplifies everything to the bone by only using sets of _integers_ 00:08:03 oerjan: ais523: Then what would you call the property "I can map any Turing-machine to a (meaningfully different) program in this language"? 00:08:35 -!- coppro has joined. 00:08:39 oerjan: Again, I don't care too much about encoding -- unless you think there's something critical about it 00:09:46 cpressey: well it's critical for quines, which is where my first comment took inspiration. but ok, as long as program and input are encoded separately it doesn't matter for this discussion. 00:09:58 That property is a property L doesn't have, and isn't necessary for TC (if L is TC), but a lot of languages DO have. And it doesn't seem to have a name, beyond it's working title "property 2" 00:10:47 cpressey: ah i just remembered. look at the wiki's Narcissist page. 00:10:55 what does meaningfully different mean? 00:11:03 it's a notion dual to quine, with input instead 00:11:26 oerjan: accepts only itself? 00:11:32 oklopol: Well, different beyond simply renaming variable names or something trivial like that. Not a very well defined condition, I agree. 00:12:00 yeah still just a matter of cardinalities, in mathematical terms 00:12:26 cpressey: and then i can ask you, is your property essential for the _existence_ of narcissists, like the "output-complete" idea is for the existence of quines? 00:12:56 oerjan: Hm. 00:12:59 (guaranteed existence from fundamental concepts, that is) 00:13:02 -!- madbr has joined. 00:13:20 oerjan: I have no idea right now. 00:13:44 this is too complicated, let's talk about flowers 00:13:54 oh wait i know even less about those 00:14:16 my favourite is Cauliflower. 00:14:57 if you flow, are you a flower? 00:15:06 lament: did you know that is the same species as brussels sprouts? 00:15:12 * oerjan ducks 00:15:35 they are both called "kaali" in finnish 00:15:36 did you know that ducks were the same species as geese? 00:16:06 oerjan: In my head, fluttering half-memories of the "every TC language has a quine" proof... are you suggesting "Every property 2 [sigh] language has a narcissist" as a kind of dual to it? 00:17:49 yeah. 00:18:05 yeah, it sounds likely. 00:18:13 not that i've thought much about it, it was just a spur of the moment idea 00:18:24 Brain... melting... 00:18:57 note that "every TC language has a quine" is not precisely correct, which is why we invented the notion of output-completeness in that discussion. 00:19:12 Right. 00:20:02 But there is that fixpoint thing going on. There would be a fixpoint "the other way". Since all TMs can be mapped to this language, there must be one program that maps to a Narcissist. Something like that. 00:21:23 mind you it's not very different from a quine in practice, come to think of it. you just slap an == input instead of a print on your program self-construction string. 00:22:03 but of course this if you are in a language which has both sensible input and output 00:22:53 s/instead of a/inside of the/ 00:23:39 Yeah. 00:24:28 * oerjan rereads the article - oh it was your idea 00:26:00 I see there's something called a "selfinterp" on Madore's page, but it looks to be a slightly different concept. 00:27:55 Anyway, I have to be off, with head spinning. 00:28:00 link? 00:28:10 http://www.madore.org/~david/computers/quine.html 00:28:18 ah. 00:28:35 http://www.madore.org/~david/computers/quine.html#sec_selfint 00:29:54 ugggh 00:30:01 :) 00:30:04 Later, folks. 00:30:07 bye 00:30:12 -!- cpressey has left (?). 00:38:58 so who's good at math 00:39:02 i've a math question 00:39:10 what sort of math 00:39:13 silly math 00:39:36 suppose you have a bunch of opponents 00:39:47 one of them has probability P of winning against a random other opponent 00:39:51 another one has probability Q 00:40:03 make a guess about how they would do against each other! 00:40:17 is that like untransitive dice? 00:40:31 sure 00:40:56 it makes sense that if P == Q, then the guess ought to be 0.5 00:41:05 (since we have no other information) 00:41:15 and if P > Q, then the guess should be > 0.5 00:41:26 and if P == 1 then the guess should of course be 1 00:41:39 and if P and Q are both 1 then we're kinda screwed 00:41:44 (but that cannot happen) 00:42:42 i would bet on the one that has a bigger probability for winning against a random opponent. 00:42:58 hmmm 00:43:11 oklopol: right, me too 00:43:17 so the question is that there's say a set of people {P}u{Q}uEveryoneElse, 00:43:21 but can you quantify your guess, other than just 1 or 0? 00:43:46 and there's the probabilities for P winning against {Q}uEveryoneElse, (and similiar for Q) 00:43:50 if P is 0 or if Q is 1, the guess is 0 00:43:54 oh wait this is a famous annoying problem, isn't it 00:43:56 if P is 1 or Q is 0, the guess is 1 00:44:08 if P == Q, the guess is 0.5 00:44:14 * oerjan just got this deja vu feeling 00:44:22 what if P is like 1/4 and Q is like 3/4 ? 00:44:37 oerjan: really? I'd like to know 00:44:41 lament well I don't think there is an answer ? 00:44:54 MissPiggy: there isn't an answer, but you can definitely make a guess! 00:44:58 maybe it's just a slight resemblance. i cannot remember what it was anyhow. 00:45:10 AFAIK, the probabilites can't be calculated based on info given... I think its possible that P > Q, but when they go against each other, the one with prob Q wins more than loses... 00:45:18 no, probabilities can't be calculated. 00:45:22 that's why i keep saying guess. 00:45:50 i suppose the way to formalize is would be by trying to minimize the differences between our guesses over all opponents, compared to the real probabilities 00:46:24 and the only condition for the guess is that it can't use any other information than the values P and Q 00:46:26 indeed, you could have a bunch of people playing rock/paper/scissors somehow always choosing the same thing 00:46:26 Best guess estimate: P / (P + Q) for that with prob P, Q / (P + Q) for that with prob Q. 00:46:42 and still have just about any set of probabilities for the group 00:46:57 (er, for two members of the group) 00:47:29 probability is really confusing 00:47:32 Ilari: hm, maybe that's it 00:47:50 but doesn't look right 00:47:56 e.g 00:47:57 at least it adds to 1 :D 00:48:01 if P = 0.2, Q = 0.8 00:48:12 then P/(P+Q) is 0.2 00:48:30 but you'd expect it to be less 00:49:09 i guess one way to approach this is to assume that probabilities actually are transitive. 00:49:18 yeah but that's not a true 00:49:47 but i don't even know how to assume that :( 00:50:20 if we make all possible orderings for a set of length n, and for each ordering calculate (the ways for someone who wins p of the matches to win someone who wins q of the matches) / (all such pairs), take average and let n --> infinity 00:50:22 hm the average of all probabilities has to be 0.5 i think 00:50:36 then why wouldn't the probability be well-defined? 00:51:40 i mean you can clearly feel, using your heart, that the limit exists 00:52:13 maybe it makes sense to model it like this: 00:52:14 oklopol: the probability could depend greatly on the game played 00:52:20 our 'random opponent' is the number 1 00:52:46 say, each player's favorite strategy could have really complicated behavior when paired against others 00:52:49 our known opponents are random numbers chosen from an interval (0,x) such that the probability of the number being larger than 1 is P 00:53:02 oerjan: but if we assume the orderings are random 00:53:13 (so that x = 1/p) 00:53:38 then the guess is that a random number from (0,1/p) is greather than the one from (0,1/q) 00:53:47 *greater 00:53:51 oklopol: the thing is, for a start, two players' chance of winning against each other could be nonlinear in some "skill" 00:53:54 i think that makes sense 00:54:36 what's the point anyway, if yo uhave a probability doesn't even tell you what's going to happen 00:54:46 and i suspect you could get a lot of different functions of p and q dependent on this 00:54:51 * MissPiggy existential crisis' 00:54:56 MissPiggy: it's a best guess. It's a prior. 00:54:58 oerjan: i assume complete nonlinearity, i assume that for all pairs, it's completely random who wins. 00:55:05 it's a prior? 00:55:06 And if there is such skill, one would have to model it... 00:55:12 I thought it came from priors 00:55:40 oklopol: oh then it's 0.5 for each pair? but then all the p's and q's are 0.5 too, sorry. 00:55:57 i think he meant the probability is random for each pair 00:56:05 what? i'm assuming a finite universe 00:56:09 n players 00:56:21 oh wait you are saying p and q are the actual number of games won 00:56:26 sure 00:56:37 oklopol: ok you are interpreting p and q completely different from me then 00:56:39 the amount of players they win out of the number of all players 00:56:46 um P and Q 00:56:53 i see 00:56:54 -!- FireFly has quit (Quit: Leaving). 00:57:02 i prefer finite things 00:57:04 it's a game of chance 00:57:08 take two players 00:57:13 it's not known who wins 00:57:23 but the probability of one of them winning is known 00:57:40 if you take one player and the probability of him winning against a randomly chosen opponent - that's p 00:58:27 oklopol: i am assuming as a mental model that for each pair of players there is a given chance of each player winning (summing to 1 of course) 00:58:45 yeah 00:58:51 and P for a player is simply the average of the chances of winning against each of the others 00:58:51 i see 00:59:11 is that actually different from mine? 00:59:28 hmm 00:59:29 yes 00:59:36 or... 00:59:37 i agree with oerjan. 00:59:40 " i assume that for all 00:59:42 pairs, it's completely random who wins" 00:59:42 -!- MissPiggy has quit (Ping timeout: 256 seconds). 00:59:53 i interpreted that as 0.5 for all pairs 01:00:04 yeah, but once you know they win pn of the matches 01:00:18 couldn't you just think of it as them winning with prob p 01:00:24 but that means there is no underlying skill difference 01:00:44 and so any P and Q has no predictive power 01:01:54 there has to be an underlying probability varying between pairs if there is to be any predictive estimate 01:02:09 i don't see a fundamental difference, but if there is one, obviously yours is better 01:02:10 of course the underlying function is unknown, hm 01:02:10 er 01:02:15 of course p and q have predictive power 01:02:58 in my model, of course p and q have predictive power, because if q is large, then you know that dude is prolly not one of the p dudes player 1 wins 01:03:17 and so on 01:03:22 actually my way is too simple 01:04:04 * Sgeo_ mindboggles at FC++ 01:05:59 i predict this is extremely complicated to do properly, and will not give a fixed result. although it's probably bayesian thinking which i've never properly understood anyhow 01:06:02 oerjan: of course p and q have predictive power 01:06:06 if you want to bet on who wins 01:06:13 and you know p and q 01:06:19 you should bet on whichever's larger 01:06:24 on average, you will be ahead 01:06:29 well yeah 01:07:07 lament: i was deducing from oklopol's assumption that all pairs were random (i.e. 0.5) 01:07:28 i think by "random" he meant random values for probabilities 01:07:28 i.e. the actual player pairs 01:07:39 hm 01:07:55 but what the fuck does it matter if the pairs were random if you are actually considering some actual game with, for each pair, a predefined result for the winner 01:07:55 ah 01:08:21 they are not random in a given game 01:08:32 it's not _completely_ predefined, it's still a probability for each pair 01:08:33 all the probabilities are 1 or 0 there 01:08:45 no, in mine, you have probability 1 or 0 for each pair. 01:08:46 they don't necessarily win every time 01:08:48 ok 01:09:47 hm every actual probability distribution is a linear combination of yours... 01:10:27 probably that won't help any 01:10:42 nothing helps, someone start a simulation. 01:11:37 i like how you guys are still talking about this 01:11:45 * oerjan is stopping now 01:11:57 i made my guess 20 min ago, i think it's correct 01:12:14 though i'm not even sure how to quantify correct yet 01:12:23 lament: have you seen what happens if you put "c" and "not tc" within 10 words of each other on this chan? 01:13:00 hehe 01:13:22 C doesn't impose arbitrary limits on the filesystem 01:13:46 oh dear 01:14:49 by the way, numerically, my guess is P/2Q 01:15:05 that kinda seems wrong :) 01:15:07 that can be over 1 01:15:10 can't it 01:15:17 sure, it can 01:15:21 it's not a very good guess 01:15:36 ok i need to fix this 01:15:57 * lament sucks at probs 01:16:18 what if we have n people, each making a guess about this problem, and we take two of them, P and Q, ... 01:29:20 -!- coppro has quit (Ping timeout: 246 seconds). 01:34:18 -!- comexbot has changed nick to comex. 01:38:15 -!- coppro has joined. 01:46:09 C isn't a programming language; it's a computer processor control language. You use it to control a computer processor. 01:46:49 i profess to process 02:03:13 Given C# knowledge, how easy/difficult will it be to tutor someone in Java? 02:03:50 Sgeo_: not too hard; learn the syntax differences, and the standard library 02:03:57 not all of it, but the bits you want to teach 02:04:12 there isn't much of an attitude difference, except that java sometimes takes correctness over the top 02:04:27 Well, presumably this person is taking a class, so they'd have notes.. 02:04:46 Sgeo_: teaching Java's my day job, btw 02:04:46 Ultimately, your benefit will be from knowing *programming*, not from knowing Java specifically. 02:04:55 pikhq: agreed 02:05:04 although knowing the OO attitude helps a lot too for Java 02:05:14 After the 10 hours of Java tutoring is over, I plan on forgetting everything again 02:05:36 Knowing a specific language only is needed if it's something that's a bit "out there" compared with what you're used to. 02:05:48 (going from imperative-land to Lisp or Haskell, for instance) 02:06:07 And even that's more "knowing the general paradigm". 02:28:36 -!- coppro has quit (Remote host closed the connection). 02:29:29 -!- coppro has joined. 03:36:17 -!- coppro has quit (Ping timeout: 252 seconds). 04:06:53 http://filebin.ca/hvmcpf/candyfloss.mp4 Enjoy some MST3K 04:09:32 -!- coppro has joined. 04:10:12 I love me some illegal downloads! 04:10:59 me too 04:11:14 As illegal downloads go, that's not very illegal, it's just a short clip :P 04:13:14 JUST A SHORT PRISON STAY, THEN 04:16:55 Gregor: Just as illegal. 04:17:19 Oh stop complaining and watch the fekking clip :P 04:17:29 I did. 04:17:33 They are agents of Satan! 04:37:20 i have terabytes of illegal downloads 04:38:10 how terable 04:38:36 One person in my UNIX class was convinced that they wouldn't go after him for illegal BitTorrent stuff if, as soon as it went to 100%, he stopped it. 04:39:06 pikhq: Which Haskell graphical library should I use? Also, when coding complex programs, does one normally worry about the IO/normal code separation too much? 04:39:46 Sgeo_: somewhat true 04:40:48 If by "somewhat" 04:40:51 You mean "not" 04:43:09 coppro: "I don't, but you may want to try wxHaskell" and "Normally? It's just natural, pretty much always." 04:43:32 bsmntbombdood: I just like commenting that it's illegal. 04:43:37 s/wouldn't/less likely to/ 04:43:39 ok, thanks 04:43:47 Just to note the ridiculousness of it being illegal. 04:44:12 I just need to watch that I don't just create and discard an IO object, right? 04:44:32 coppro: ... 04:44:38 :P 04:44:55 Why are you using unsafePerformIO, and can you make it stop? 04:44:59 :P 04:47:13 I didn't know what that is. Now I do. Now I feel dirty. 04:49:21 That's the appropriate reaction. 04:53:34 coppro: i _think_ pikhq was hinting at the idea that it is unlikely you'll manage to create and discard an IO object unless you are using that. 04:54:37 oerjan: f x y = x 04:54:51 although it's not impossible... 04:54:52 f 1 getLine 04:55:04 yeah but why would you do that? 04:55:21 I don't know why; I'm just making sure that does what I expect (namely, nothing, since it didn't come through main) 04:55:35 yeah 04:55:39 f = const btw 04:57:29 -!- MizardX has quit (Ping timeout: 240 seconds). 04:57:47 coppro: Yeah, that does absolutely nothing, and does it well. 04:58:20 why is it called const? 04:58:27 constant function 05:00:21 I dun get it :( 05:00:45 a constant function is a function that takes the same value at all points 05:00:54 And const creates such a function. 05:00:58 so const 1, say, is a constant function 05:00:58 ah 05:01:01 -!- gm|lap has quit (Quit: 2 hour UPS expired. Shutting down laptop.). 05:01:19 Also, the typical non-Haskell name for \x y -> x is "K". 05:01:53 K combinator 05:02:10 Well of course it's a combinator. 05:02:11 :P 05:08:17 xkcd :D 05:09:17 :D 05:19:48 -!- Asztal has quit (Ping timeout: 256 seconds). 05:21:57 -!- Asztal has joined. 05:24:56 oerjan, I don't quite get it 05:25:43 http://en.wikipedia.org/wiki/Two-Face 05:26:04 ty 05:28:19 I thought it might be a reference to "it puts the lotion on its skin" even though I don't know waht that means 05:28:45 well neither do i 05:30:42 * Sgeo_ reads a wikipedia article 05:30:44 And nearly vomits 05:30:56 ? 05:31:34 Let's just say that the character [in Silence of the Lambs] is not a nice person 05:31:39 http://en.wikipedia.org/wiki/Jame_Gumb 05:32:26 ic (or rather i'll try not to) 05:40:57 * oerjan finds randall munroe's bug reports - unusual 05:41:04 (see blag) 05:45:32 -!- coppro has quit (Remote host closed the connection). 05:56:13 -!- coppro has joined. 06:06:57 -!- mycroftiv has quit (Ping timeout: 256 seconds). 06:08:58 -!- ais523 has changed nick to scarf. 06:09:15 -!- mycroftiv has joined. 06:11:08 -!- scarf has changed nick to ais523. 06:30:15 -!- jcp has joined. 06:59:27 -!- Pthing has joined. 06:59:30 -!- tombom has joined. 07:06:42 -!- oerjan has quit (Quit: Good night). 07:14:10 -!- zeotrope has joined. 07:16:31 -!- madbr has quit (Quit: Radiateur). 07:22:17 -!- augur has quit (Read error: Connection reset by peer). 07:22:24 -!- augur has joined. 07:30:39 -!- ais523 has quit (Remote host closed the connection). 07:44:37 -!- jcp has quit (Quit: I will do anything (almost) for a new router.). 07:49:46 -!- tombom has quit (Quit: Leaving). 07:59:59 -!- clog has quit (ended). 08:00:00 -!- clog has joined. 08:02:45 -!- FireFly has joined. 08:12:46 -!- oklopol has quit (Ping timeout: 252 seconds). 08:13:19 -!- FireFly has quit (Quit: Leaving). 08:28:49 -!- kar8nga has joined. 09:16:32 -!- SimonRC has quit (Ping timeout: 265 seconds). 09:28:56 -!- SimonRC has joined. 09:36:00 -!- oklopol has joined. 09:37:56 -!- Pthing has quit (Remote host closed the connection). 09:50:13 -!- oklopol has quit (Ping timeout: 260 seconds). 11:05:46 -!- cheater has quit (Remote host closed the connection). 11:20:45 -!- cal153 has quit. 11:22:22 -!- cheater has joined. 11:58:23 -!- Pthing has joined. 12:27:33 -!- kar8nga has quit (Remote host closed the connection). 12:30:57 -!- MizardX has joined. 13:25:24 -!- kar8nga has joined. 14:10:12 -!- ineiros has quit (Ping timeout: 260 seconds). 14:15:30 -!- MissPiggy has joined. 14:47:25 -!- kar8nga has quit (Remote host closed the connection). 14:57:03 -!- coppro has quit (Quit: I am leaving. You are about to explode.). 15:30:11 -!- cpressey has joined. 15:36:49 So, I think I'm going to give up using the term "Turing-complete", since it is woefully ill-defined (except in recursive function theory, where it means something slightly different from "universal".) 15:37:11 yay!! 15:37:28 I tend to call things mu-recursive instead of turing complete, because I'm usually talking about functions 15:39:47 There's a whole space inside the intuitive notion of "Turing-complete" that *could* be formalized, but hardly anyone's doing it, and I have no idea why. 15:39:51 (a) Encoding (b) Input composition (c) Halting (d) Initial tape configuration 15:41:19 -!- FireFly has joined. 15:44:01 tell me about (c)? 15:44:28 also I think ais has done a little bit in terms of (a) and (d) hasn't he? with the 110 stuff 15:45:17 (aaway elsewherr 15:45:21 Graa. 15:45:25 I cannot type. 15:45:58 ais has caused holy wars over (d) :P 15:48:10 -!- oerjan has joined. 15:49:16 hehe 15:54:38 -!- ineiros has joined. 15:54:42 -!- ineiros has quit (Client Quit). 15:54:57 -!- ineiros has joined. 16:01:20 MissPiggy: short version about (c): Turing machines halt, Cellular automata don't, so for a CA to simulate a TC you need some way to recognize when it has reached a particular state and you can declare it's halted. 16:01:29 s/TC/TM/ 16:01:46 turing machines halt ?? 16:01:56 MissPiggy: Traditionally, yes. It's how they decide things! 16:01:57 Yes, Turing machines can halt. 16:02:22 Cellular automata don't, but can be said to "halt" when they come to a stable position. 16:03:24 Generally TMs halt by a designated "halt" state. The same is true of CA, but their halt state may take nonconstant time to recognize. 16:03:36 pikhq: Still, you need to be able to recognize that stable position, so from a complexity point of view, you need some sort of predicate that says "has this CA halted?" and I think the complexity of that predicate has to be taken into account when you start making claims about one system being "simpler" than another. 16:03:55 Erm, the same is true of CA when you're using them to calculate something: They go to a designated "halt" state. It just so happens that they continue on, because that designation is purely human :P 16:03:59 yeah inputing encoding for CAs is usually O(n) or worse too 16:04:16 Gregor: Right, equivalently, the "halted?" predicate is trivial for TMs. 16:04:23 Yup 16:04:47 Like the "what should the symbol on the next new cell of tape I use be?" function is also trivial for TMs, not so trivial for CAs that rely on pretty patterns throughout space. 16:05:25 However, the statement "Turing-complete" makes no argument about time complexity. So long as it takes non-infinite time to encode and recognize, it's still Turing complete. Or is that exactly what you're complaining about? 16:05:57 Gregor: No, I'm taking issue with certain mathematician's claims that their system is "simpler" here :) 16:06:04 Ahhhhhhhhhhhhhhhhhhhhhhh 16:06:30 aha 16:06:31 And trying, idly, to formalize all this machinery within the Wonderful World of TC 16:06:33 "Certain mathematicians" who shall remain nameless but obvious :P 16:06:39 so in summary: simpler shmimpler 16:07:12 locally nameless :D 16:07:36 para-nameless 16:08:23 -!- MigoMipo has joined. 16:09:40 And for the record, yesterday's exciting language L was raising the question about (b). 16:10:16 L was a real language?? 16:10:22 I thuoght it was arbitrary 16:10:34 It was a language for the purpose of discussion. 16:10:58 Well, I was calling it L. But I just looked it up and there are apparently at least 3 "real" languages named L. 16:11:02 http://en.wikipedia.org/wiki/L_programming_language 16:11:13 -!- kar8nga has joined. 16:11:42 (my) L would be a good example of a pathological example of a language 16:11:52 what is your L? 16:11:57 sorry but I missed it yesterday 16:12:21 -!- BeholdMyGlory has joined. 16:12:33 A language limited to implementing a Kibble interpreter. 16:12:35 L is a language in which all programs are illegal except one: an interpreter for <>. 16:13:13 -!- Gregor has set topic: RIP sun.com | 4 days since last ehird sighting | 2 days since last alise sighting | 203 days since last graue sighting | 14 days since last calamari sighting | 1158 days since last kipple sighting | http://tunes.org/~nef/logs/esoteric/?C=M;O=D. 16:13:59 cpressey oooh hehe that's cool 16:14:24 -!- pikhq has set topic: RIP sun.com | 5 days since last ehird sighting | 3 days since last alise sighting | 204 days since last graue sighting | 15 days since last calamari sighting | 1158 days since last kipple sighting | http://tunes.org/~nef/logs/esoteric/?C=M;O=D. 16:15:33 MissPiggy: Whether it's "TC" or not seems to depend on what you think about the role of input in determining that. 16:15:48 -!- oklopol has joined. 16:16:21 For every TM, I can come up with (some L program, some input) that simulates that TM. But I can't come up with just (some L program) that simulates the TM. 16:16:25 Too bad wget doesn't have an --ignore-robots.txt option :P 16:16:41 -!- zeotrope has quit (Quit: Lost terminal). 16:16:44 Gregor: Grab the source and add it. ;) 16:18:57 I can't mirror the logs :( 16:19:08 :( 16:19:12 I mean, I have my own logs, but that relies on my unreliable connection. 16:23:50 -!- oklopol has quit (Ping timeout: 252 seconds). 16:25:34 -!- oerjan has quit (Quit: Later). 16:45:48 yrh 16:46:05 -!- cheater has quit (Read error: Connection reset by peer). 16:46:33 -!- cheater has joined. 16:46:37 Gregor: If filenames are predictable, call wget in loop? 16:47:22 Ilari: Bleh :P 16:49:28 Ilari: Dates are pretty predictable. ;) 16:55:43 I wonder if P != NP could be proved with a space complexity result, like: NP potentially generates more intermediate data than can possibly be processed in P. 16:55:50 -!- tombom has joined. 16:56:17 -!- cheater has quit (Read error: Connection reset by peer). 16:56:32 But, oh god. Here I am complaining about the vagaries of "Turing-completeness", I completely forgot what hell with models of computation they have in complexity theory. 16:56:35 * cpressey shudders 16:56:47 -!- cheater has joined. 17:06:39 But then, how one proves lower bound for intermediate data generated? 17:07:13 cpressey, did you reach any conclusion about the issue with L? 17:07:50 I saw it discussed in scrollback but the it was quite far too long to read, and intermixed with other discussions 17:08:01 * AnMaster goes studying for a test 17:09:43 AnMaster: Whether L is "Turing-complete" or not seems to depend on what you think about the role of input in determining that. or every TM, I can come up with (some L program, some input) that simulates that TM. But I can't come up with just (some L program) that simulates the TM. I went looking and reached the conclusion that the term "Turing-complete" relies too much on intuition, so I'm going to try to avoid using 17:09:53 s/or/For/ 17:10:06 cpressey, but not all TC languages have input separate from the program itselfd 17:10:08 itself* 17:10:15 for example, that one ais proved 17:10:31 AnMaster: depend on how you define TC :) 17:10:35 won some price from wolfram for it 17:10:38 forgot what it was called 17:10:59 ah yes: 17:11:04 http://www.wolframscience.com/prizes/tm23/ 17:11:38 AnMaster: I could say such languages are not Turing complete, because their programs don't define functions. 17:11:51 I'm not sure I *would*, but I *could* :) 17:11:52 cpressey, but neither do UTMs! 17:11:53 Now fetching logs! 17:11:56 Muahahahaha 17:12:08 AnMaster: ? a UTM defines a function 17:12:13 hm 17:12:30 cpressey, depends on what exactly you mean by a function here 17:12:37 cpressey, also, wasn't GOL proved TC? 17:12:45 AnMaster: maps some set of inputs to some set of outputs 17:12:54 cpressey, well, what about game of life 17:13:00 it is well established to be tc 17:13:24 AnMaster: Please understand, since I just decided that the term "Turing-complete" is not well-defined, I don't think that languages can be proved to be it or not. 17:13:53 cpressey, then what exactly do we prove when when implement brainfuck or whatever in a given language 17:14:16 (bf with infinite tape of course) 17:14:25 Maybe I'll stick the logs in hg, if it's not too big. 17:14:28 AnMaster: I don't know anymore :) We prove that brainfuck can be implemented in it, at least... 17:14:30 Which it will be :P 17:14:47 cpressey, and a host of other languages, if those can be implemented in brainfuck 17:15:37 like: a bignum-space befunge98 is able to implement a brainfuck interpreter with infinite tape 17:15:47 AnMaster: I'm sure it would be possible to prove it was TC if we could get a definition of TC that wasn't mostly intuitive. It would have to address several things, which I listed previously (encoding, halting, input composition, initial tape contents, maybe others) 17:16:28 Like: I think the term TC can be formalized, but I don't think it has been yet. I think there would probably be multiple formalizations, too. 17:16:40 cpressey, able to implement an UTM in. And yes L is TC then. So we need a TC-not-bloody-silly one for practical purposes 17:16:54 hehe 17:17:05 * Gregor reappears mid-conversation. 17:17:08 AnMaster: right, or TC needs to be "split up" into a bunch of different properties (some of which imply others) 17:17:16 Is the problem with L's reduction that it results in a huge time complexity? 17:17:23 Gregor, what? 17:17:43 Gregor, L is scheme but with restrictions added so it can *only* implement an interpreter for another tc language 17:17:43 Gregor: No, no complexity or encoding issues that I'm aware of. 17:17:47 a specific one 17:17:55 Gregor: It's an input issue. 17:18:00 Ah 17:18:01 Gregor, thus, is L itself TC? 17:19:18 I should maybe put this all on the wiki at some point. 17:20:57 cpressey, might be a good idea 17:21:17 anyway, formalising TC might be stuff for a thesis 17:22:05 AnMaster: Sure, but what advisor in their right mind would let their student work on it? :) 17:23:31 cpressey, none 17:28:22 -!- cal153 has joined. 17:38:10 -!- kar8nga has quit (Remote host closed the connection). 17:43:07