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

02:33:29 <oerjan> i think you failed to show up to your anti-trust proceedings, so there was a default judgement

04:27:45 <zzo38> Also, did you read that: http://notalwaysright.com/its-difficult-to-make-it-any-simpler/4160

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: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: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.

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: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: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:34:14 <cpressey> Scheme and Kipple of course just being concrete examples of TC languages, you could pick any you liked.

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: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: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: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: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: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: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: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: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: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:47:24 <lament> there exists an algorithm to print a list of primes, L cannot do it, therefore L is not TC

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:59 <AnMaster> cpressey, either way this results in some issues for the esolang community as far as I can tell

19:50:37 <pikhq> MissPiggy: If an algorithm exists, there exists an equivalent Turing machine for it.

19:52:09 <MissPiggy> are you reading it as: if a turing machin exists, there exists an equivalent turing machine for it?

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: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:28 <MissPiggy> lament yeah which is why I don't think that's a correct interpretation of church-turng

20:05:10 <AnMaster> <pikhq> lament: More of a tautology, really. <-- a tautology is trivially true though

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:56 <pikhq> MissPiggy: By merit of having a halting oracle, you're out of the realm of Turing machines. ;)

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: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: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: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:19:04 <AnMaster> well, we know some things are necessary for TC, everyone agrees on some minimums.

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: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 <cpressey> http://www.amazon.com/Recursively-Enumerable-Sets-Degrees-Perspectives/dp/0387152997

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:26:19 <oklopol> AnMaster: the language of such words that if you put them on the tape and run the tm, ...

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: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: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: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 <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: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: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:58 <oklopol> "cpressey: RE intersect co-RE, that's the "completely undecidable" set I was thinking of" <<< no that's R

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:43:34 <oklopol> AnMaster: you have universal and existential quantification over integers, addition, multiplication and equality check, and then boolean operators.

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:49:41 <cpressey> So I'm misremembering it. Maybe it was "computable mapping", for some definition of "computable".

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:39 <AnMaster> MissPiggy, well yes, if you just had square root it would be trivial to match it up to Q

20:55:43 <MissPiggy> because countable x countable is countable (cantors zig-zagonalization theorem)

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: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: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: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: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: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:50 <cpressey> oklopol: Going over that Turing degree page, I do believe it was "a mapping computable by TM" (Turing-reducible) now.

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: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: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: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:15:09 <cpressey> If you take more sophisticated operations as primitives, you can consider more sophisticated sets computable. Surprise! :)

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:18:58 <oklopol> then you have lower bound + 1, ..., so... you'll have 1 in there, then 2, 3, ...?

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: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: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: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: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: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

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.

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: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: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: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: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:52 <oerjan> you can write a computable reduction from any TM with input to an L program with input.

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: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:58 <cpressey> Now I'm all confused about lambda terms, and I don't know where to begin explaining why, though.

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:41 <cpressey> Well, you said "but there are TC concepts with no input at all" -- what should I make of that?

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: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: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:55:26 <oerjan> cpressey: that TMs can overwrite things - this is irrelevant to what they can _compute_

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: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: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