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