< 1265673615 0 :fizzie!unknown@unknown.invalid PRIVMSG #esoteric :And one Lindsay Tanner Swett, but I daresay that's not it.
< 1265673626 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :night
< 1265673641 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :oh wait it _is_ warrigal
< 1265673686 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :uorygl: darn i thought it was just a moment ago you were 14 :D
< 1265673778 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :well i guess you're at least old enough to reveal your real name then
< 1265673864 0 :Sgeo!unknown@unknown.invalid PRIVMSG #esoteric :ACTION didn't reveal his real name until he was 17
< 1265673908 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265673922 0 :fizzie!unknown@unknown.invalid PRIVMSG #esoteric :Misread that as "Sgeo didn't learn his real name until he was 17"; that sounds like a funny environment to grow up in.
< 1265673966 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :well _i_ thought about how surprised his parents must have been when he revealed it
< 1265673993 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265674497 0 :cpressey!unknown@unknown.invalid PART #esoteric :?
< 1265674869 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265674968 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265675828 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265675887 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265676115 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265678062 0 :jcp!~jw@bzflag/contributor/javawizard2539 JOIN :#esoteric
< 1265678701 0 :MissPiggy!unknown@unknown.invalid QUIT :Quit: Lost terminal
< 1265678928 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265679320 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265679359 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265679635 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265679717 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265679966 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265680015 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265680231 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265681181 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265681522 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265681550 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265682142 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265682205 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265682329 0 :Asztal!unknown@unknown.invalid QUIT :Ping timeout: 248 seconds
< 1265682487 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265682563 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265682765 0 :uorygl!unknown@unknown.invalid PRIVMSG #esoteric :oerjan: indeed, I have joined university.
< 1265682776 0 :uorygl!unknown@unknown.invalid PRIVMSG #esoteric :fizzie: there are three of me? Darn, what happened to my monopoly?
< 1265682809 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :i think you failed to show up to your anti-trust proceedings, so there was a default judgement
< 1265682832 0 :uorygl!unknown@unknown.invalid PRIVMSG #esoteric :Aww. And I never even got the letter. It must have gotten lost in the mail.
< 1265682839 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265682842 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :probably in your spam folder somewhere
< 1265682862 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265682905 0 :uorygl!unknown@unknown.invalid PRIVMSG #esoteric :Anyway, I'm the white, fuzzy one.
< 1265682935 0 :uorygl!unknown@unknown.invalid PRIVMSG #esoteric :Standing on a solar panel in outer space.
< 1265682958 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :ah
< 1265683104 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265683128 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265683403 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265684054 0 :iamcal!unknown@unknown.invalid QUIT :
< 1265684470 0 :cal153!~cal@c-69-181-46-213.hsd1.ca.comcast.net JOIN :#esoteric
< 1265684893 0 :augur!unknown@unknown.invalid PRIVMSG #esoteric :uorygl: which university?
< 1265685000 0 :cheater2!unknown@unknown.invalid QUIT :Ping timeout: 252 seconds
< 1265685764 0 :zzo38!~zzo38@h24-207-48-53.dlt.dccnet.com JOIN :#esoteric
< 1265685947 0 :olsner!unknown@unknown.invalid QUIT :Ping timeout: 265 seconds
< 1265686192 0 :zzo38!unknown@unknown.invalid QUIT :Quit: Washizu Mahjong...:F:ALKSF:LAKSF:KJSDMCP#RC)I(UM@!$X<)!U@$#
< 1265686438 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265686805 0 :olsner!~salparot@c83-252-161-133.bredband.comhem.se JOIN :#esoteric
< 1265686818 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265686868 0 :pikhq!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265687250 0 :uorygl!unknown@unknown.invalid PRIVMSG #esoteric :augur: Grand Valley State.
< 1265687262 0 :pikhq!~pikhq@75-106-100-139.cust.wildblue.net JOIN :#esoteric
< 1265687277 0 :augur!unknown@unknown.invalid PRIVMSG #esoteric :what
< 1265687300 0 :uorygl!unknown@unknown.invalid PRIVMSG #esoteric :Grand Valley State Universirty.
< 1265687303 0 :uorygl!unknown@unknown.invalid PRIVMSG #esoteric :s/r//
< 1265687324 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Univesirty?
< 1265687479 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :very gud speeling progarm
< 1265688542 0 :augur!unknown@unknown.invalid PRIVMSG #esoteric :wheres that ey
< 1265689419 0 :zzo38!~zzo38@h24-207-48-53.dlt.dccnet.com JOIN :#esoteric
< 1265689474 0 :Gregor!unknown@unknown.invalid PRIVMSG #esoteric :I DONE GONE TUH UNIVERSIRTY
< 1265689619 0 :zzo38!unknown@unknown.invalid PRIVMSG #esoteric :Can you please review my program to see if it is good?
< 1265689630 0 :zzo38!unknown@unknown.invalid PRIVMSG #esoteric :Can you please review my program to see if it is good enough?
< 1265689665 0 :zzo38!unknown@unknown.invalid PRIVMSG #esoteric :Also, did you read that: http://notalwaysright.com/its-difficult-to-make-it-any-simpler/4160
< 1265690299 0 :zzo38!unknown@unknown.invalid QUIT :Remote host closed the connection
< 1265691416 0 :augur!unknown@unknown.invalid QUIT :Ping timeout: 272 seconds
< 1265693796 0 :puzzlet!unknown@unknown.invalid QUIT :Changing host
< 1265693796 0 :puzzlet!~puzzlet@wikipedia/PuzzletChung JOIN :#esoteric
< 1265694863 0 :coppro!unknown@unknown.invalid PRIVMSG #esoteric :I hate my school board's internet connection
< 1265694885 0 :coppro!unknown@unknown.invalid PRIVMSG #esoteric :51 packets transmitted, 0 received, 100% packet loss, time 50254ms
< 1265695146 0 :coppro!unknown@unknown.invalid PRIVMSG #esoteric :It's amazing I can connect at all
< 1265695284 0 :jcp!unknown@unknown.invalid QUIT :Quit: I will do anything (almost) for a new router.
< 1265695577 0 :MizardX!unknown@unknown.invalid QUIT :Ping timeout: 240 seconds
< 1265696473 0 :augur!~augur@216-164-33-76.c3-0.slvr-ubr2.lnh-slvr.md.cable.rcn.com JOIN :#esoteric
< 1265696491 0 :augur!unknown@unknown.invalid PRIVMSG #esoteric :o hai
< 1265696535 0 :coppro!unknown@unknown.invalid PRIVMSG #esoteric :hi
< 1265696573 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :hai ku
< 1265697712 0 :Pthing!~pthing@cpc11-pres4-0-0-cust168.pres.cable.virginmedia.com JOIN :#esoteric
< 1265698377 0 :coppro!unknown@unknown.invalid PRIVMSG #esoteric :http://www.haskell.org/haskellwiki/Do_notation_considered_harmful is about LYAH
< 1265698807 0 :tombom!tombom@wikipedia/Tombomp JOIN :#esoteric
< 1265699046 0 :oerjan!unknown@unknown.invalid QUIT :Quit: Good night
< 1265699395 0 :dbc!unknown@unknown.invalid QUIT :Quit: Seeeeeya
< 1265699667 0 :dbc!~daniel@130-94-161-238-dsl.hevanet.com JOIN :#esoteric
< 1265701606 0 :FireFly!~firefly@unaffiliated/firefly JOIN :#esoteric
< 1265701791 0 :tombom!unknown@unknown.invalid QUIT :Quit: Leaving
< 1265702399 0 :clog!unknown@unknown.invalid QUIT :ended
< 1265702400 0 :clog!unknown@unknown.invalid JOIN :#esoteric
< 1265703340 0 :cheater2!~cheater@ip-80-226-224-192.vodafone-net.de JOIN :#esoteric
< 1265703441 0 :FireFly!unknown@unknown.invalid QUIT :Quit: Leaving
< 1265703861 0 :Gracenotes!unknown@unknown.invalid QUIT :Ping timeout: 252 seconds
< 1265704777 0 :Slereah!~lereah@nanpc301.in2p3.fr JOIN :#esoteric
< 1265705358 0 :Lageron!~Lageron@91.82.25.45.pool.invitel.hu JOIN :#esoteric
< 1265705556 0 :Lageron!unknown@unknown.invalid PRIVMSG #esoteric :Hi!
< 1265706858 0 :gm|lap!unknown@unknown.invalid QUIT :Quit: 2 hour UPS expired. Shutting down laptop.
< 1265707607 0 :Gracenotes!~person@wikipedia/Gracenotes JOIN :#esoteric
< 1265707828 0 :adam_d!~Adam@cpc2-acto6-0-0-cust48.brnt.cable.ntl.com JOIN :#esoteric
< 1265709102 0 :adam_d!unknown@unknown.invalid QUIT :Quit: Leaving
< 1265709404 0 :Lageron!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265712067 0 :ais523!~93bcc029@gateway/web/freenode/x-xsqtesvsvtkzirug JOIN :#esoteric
< 1265712647 0 :mosasaur1!~mosasaur@84.26.40.63 JOIN :#esoteric
< 1265713203 0 :mosasaur1!unknown@unknown.invalid QUIT :Ping timeout: 252 seconds
< 1265713677 0 :coppro!unknown@unknown.invalid QUIT :Ping timeout: 256 seconds
< 1265717571 0 :kernel51!~user@213.30.189.66 JOIN :#esoteric
< 1265717582 0 :kernel51!unknown@unknown.invalid PRIVMSG #esoteric :Greetings
< 1265720715 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :hi
< 1265720723 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :hmm, that was a bit slow
< 1265720725 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :hi kernel51
< 1265720806 0 :ais523!unknown@unknown.invalid QUIT :Changing host
< 1265720806 0 :ais523!~93bcc029@unaffiliated/ais523 JOIN :#esoteric
< 1265720806 0 :ais523!unknown@unknown.invalid QUIT :Changing host
< 1265720806 0 :ais523!~93bcc029@gateway/web/freenode/x-xsqtesvsvtkzirug JOIN :#esoteric
< 1265721155 0 :ais523!unknown@unknown.invalid QUIT :Quit: Page closed
< 1265721418 0 :kernel51!unknown@unknown.invalid PART #esoteric :?
< 1265721465 0 :Pthing!unknown@unknown.invalid QUIT :Remote host closed the connection
< 1265721522 0 :MizardX!~MizardX@unaffiliated/mizardx JOIN :#esoteric
< 1265721578 0 :scarf!~scarf@unaffiliated/ais523 JOIN :#esoteric
< 1265721591 0 :scarf!unknown@unknown.invalid NICK :ais523
< 1265722874 0 :FireFly!~firefly@unaffiliated/firefly JOIN :#esoteric
< 1265723089 0 :MizardX!unknown@unknown.invalid QUIT :Ping timeout: 260 seconds
< 1265723503 0 :ais523!unknown@unknown.invalid QUIT :Remote host closed the connection
< 1265724202 0 :Sgeo_!~Sgeo@ool-18bf618a.dyn.optonline.net JOIN :#esoteric
< 1265724362 0 :Sgeo!unknown@unknown.invalid QUIT :Ping timeout: 272 seconds
< 1265724577 0 :Pthing!~pthing@cpc11-pres4-0-0-cust168.pres.cable.virginmedia.com JOIN :#esoteric
< 1265725201 0 :Slereah!unknown@unknown.invalid PART #esoteric :?
< 1265726988 0 :scarf!~scarf@unaffiliated/ais523 JOIN :#esoteric
< 1265726997 0 :scarf!unknown@unknown.invalid NICK :ais523
< 1265727637 0 :MizardX!~MizardX@unaffiliated/mizardx JOIN :#esoteric
< 1265728926 0 :kar8nga!~kar8nga@jol13-1-82-66-176-74.fbx.proxad.net JOIN :#esoteric
< 1265729384 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :7.0.0.5.770.5.8.7.0.0.5.4...1...
< 1265729647 0 :cpressey!~CPressey@173-9-215-173-Illinois.hfc.comcastbusiness.net JOIN :#esoteric
< 1265729855 0 :oerjan!~oerjan@hagbart.nvg.ntnu.no JOIN :#esoteric
< 1265730011 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric : 7.0.0.5.770.5.8.7.0.0.5.4...1... <-- i think version numbering has got out of hand
< 1265731030 0 :fizzie!unknown@unknown.invalid PRIVMSG #esoteric :That looks like an OID, except not quite.
< 1265731177 0 :fizzie!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265731305 0 :fizzie!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265731352 0 :fizzie!unknown@unknown.invalid PRIVMSG #esoteric :Have to say I like that all those standard SNMP MIB objects are hierarchically speaking under United States Department of Defense.
< 1265731578 0 :BeholdMyGlory!~behold@unaffiliated/beholdmyglory JOIN :#esoteric
< 1265731600 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :well, to me that looks pretty out of hand too.
< 1265733070 0 :MissPiggy!~quantum@amcant.demon.co.uk JOIN :#esoteric
< 1265733075 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oerjan, that version number, what is it for?
< 1265733152 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :a joke, AnMaster, a joke
< 1265733165 0 :MissPiggy!unknown@unknown.invalid QUIT :Changing host
< 1265733165 0 :MissPiggy!~quantum@unaffiliated/fax JOIN :#esoteric
< 1265733166 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :or alternatively, ask oklopol not me
< 1265733664 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oerjan, ah wrong nick
< 1265733671 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oklopol, what is that version number for?
< 1265733707 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :fizzie, what do you actually use snmp for. Just status info?
< 1265733830 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :it's not a version number
< 1265733833 0 :fizzie!unknown@unknown.invalid PRIVMSG #esoteric :I don't use it, I just know these things. (To the bus now →)
< 1265733838 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :sry
< 1265733844 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :merry bus
< 1265733859 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :it's busmas!
< 1265734088 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :my back is killing me
< 1265734176 0 :fizzie!unknown@unknown.invalid PRIVMSG #esoteric :The ADSL modem I have does traffic counters over SNMP, I used to have a mrtg-based traffic graph, but it was boring.
< 1265734377 0 :fizzie!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265734536 0 :oerjan!unknown@unknown.invalid QUIT :Quit: Later
< 1265734563 0 :lament!~lament@S0106001b63f462cc.vc.shawcable.net JOIN :#esoteric
< 1265735320 0 :tombom!tombom@wikipedia/Tombomp JOIN :#esoteric
< 1265735438 0 :MigoMipo!~migomipo@84-217-4-139.tn.glocalnet.net JOIN :#esoteric
< 1265737794 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :fizzie, can you do any setting changes over snmp?
< 1265740079 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :ais523, hi there, back in your old nick I see
< 1265740090 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :about strange courses and other university issues
< 1265740097 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :oh, I'm helping some people play NetHack
< 1265740100 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :changing nick would confuse them
< 1265740114 0 :Gracenotes!unknown@unknown.invalid PRIVMSG #esoteric :new nick? :o
< 1265740146 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :ais523, I currently have a "module" in math that consists two sub-modules. Submodule two comes before submodule 1
< 1265740151 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :I mean, in scheduling
< 1265740152 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :heh
< 1265740219 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :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
< 1265740231 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :"retake" in english
< 1265740243 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :of course, having module 2 before module 1 also causes all sorts of confusion for *new* students
< 1265740289 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :apparently they are considering renaming them to A and B instead of 2 and 1, hoping that might cause less confusion
< 1265740392 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :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
< 1265740406 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :brb
< 1265740414 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: no
< 1265742275 0 :kar8nga!unknown@unknown.invalid QUIT :Remote host closed the connection
< 1265743357 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :I have a question about Turing-completeness proofs.
< 1265743457 0 :cheater2!unknown@unknown.invalid QUIT :Ping timeout: 240 seconds
< 1265743465 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265743474 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :cpressey!
< 1265743475 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :hi
< 1265743489 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Hi lament :)
< 1265743701 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265743709 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Is L Turing-complete?
< 1265743761 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Is Kipple?
< 1265743777 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Let's assume Kipple is TC.
< 1265743785 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Then yes.
< 1265743799 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :er
< 1265743806 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :of course it's not turing-complete
< 1265743832 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :lament: Sure it is. It is evaluating a TC language, and therefore must be Turing-complete.
< 1265743839 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :what therefore?
< 1265743849 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :So you see why I asked :)
< 1265743855 0 :fizzie!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265743891 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :pikhq: that's like saying a box with an apple inside is an apple.
< 1265743907 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :lament: No. It's like saying a box with an apple possesses an apple.
< 1265743914 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :no.
< 1265743971 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Turing-complete means that it can evaluate a UTM and that a UTM can evaluate it.
< 1265743982 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :A Kipple interpreter can be considered a UTM.
< 1265744004 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :And I presume that L can be implemented on a TC system.
< 1265744027 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :fizzie, it was in general
< 1265744029 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :L is a subset of Scheme, and Scheme can be implemented on a TC system, so yes
< 1265744046 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: Then clearly L must be Turing-complete.
< 1265744054 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Scheme and Kipple of course just being concrete examples of TC languages, you could pick any you liked.
< 1265744076 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :pikhq: a Kipple interpreter cannot be considered an UTM because it isn't.
< 1265744086 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :well
< 1265744099 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265744106 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :lament: Is Kipple Turing-complete?
< 1265744115 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :let's assume it is.
< 1265744121 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :I can only write them in Kipple-interpreted-by-L.
< 1265744125 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :lament: Then it is equivalent to a UTM.
< 1265744127 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :isn't this like asking if HQ9+ extended with something like "b - interpret the rest of the code as brainfuck" is TC
< 1265744129 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :I'm not sure it is
< 1265744141 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: Sure it is.
< 1265744147 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: sure, it is
< 1265744153 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :hm
< 1265744153 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :unlike L
< 1265744159 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :why isn't L that then?
< 1265744176 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Sure, L could be that if you like.
< 1265744179 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :because you can write arbitrary programs in HQ9+b but not in L
< 1265744192 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :lament: You can?
< 1265744195 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :lament: But you certainly can.
< 1265744209 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: "interpret the rest of the *code* as brainfuck"? Sure you can
< 1265744212 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :I thought the point of HQ9+ was that you couldn't. If you can, it doesn't count.
< 1265744223 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :lament, what about changing it to "interpret a file given as a command line argument to the HQ9+b interpreter as brainfuck"
< 1265744227 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :rather than having it in the same file
< 1265744229 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :lament: Ah, OK.
< 1265744230 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :is it still tc?
< 1265744232 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: right, then it's not TC
< 1265744244 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Sure it is.
< 1265744259 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :It's just got two inputs for code.
< 1265744266 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :true
< 1265744276 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :you're confusing levels of abstraction
< 1265744287 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :and that's bad
< 1265744292 0 :Pthing!unknown@unknown.invalid QUIT :Remote host closed the connection
< 1265744311 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :No, you're pretending there's a difference between a seperate file and an arbitrary string in the program.
< 1265744312 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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).
< 1265744316 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :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
< 1265744322 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :therefore, L is not TC
< 1265744358 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :pikhq: well, either we're talking about L
< 1265744367 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265744371 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :or we're talking about Unix machine which has L in it, and you can also run the Kipple interpreter it produces
< 1265744386 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :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
< 1265744388 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :in the latter case, the device we're questioning the TCness of is not L, it's your Unix machine
< 1265744389 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :is that then TC
< 1265744394 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :and yes, your unix machine is TC
< 1265744417 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :lament: ...
< 1265744436 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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)
< 1265744438 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: then the system comprised of the interpreter and a filesystem is TC
< 1265744444 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :lament: But the L interpreter is simply reading a different tape for actually being universal rather than from the *same* tape.
< 1265744454 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :pikhq: idgi
< 1265744512 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :isn't there a multi-tape bf
< 1265744526 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :with limited length of tapes but infinite number of tapes
< 1265744539 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :There exists an interpreter for a Turing-complete language in L, therefore *L is Turing complete*. Quod erat demonstrandum.
< 1265744590 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265744608 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :???????
< 1265744617 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :You would instead have to show that *any* UTM has a mapping to a program in the language.
< 1265744618 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: we need to look at the spirit of TC definition
< 1265744626 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :where's it?
< 1265744637 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :lament: Math doesn't have "spirt".
< 1265744640 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Spirit, even
< 1265744641 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :is the rationale for def-n of TC being able to run any program?
< 1265744645 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :pikhq yeah it does
< 1265744656 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :pikhq: er, of course it does
< 1265744695 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Anyways.
< 1265744695 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :I would say that this is the spirit of TCness (quoting Wikipedia):
< 1265744696 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :"Two computers P and Q are called Turing equivalent if P can simulate Q and Q can simulate P."
< 1265744698 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :"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."
< 1265744715 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :the reason turing machines are interesting is because they can run any algorithm
< 1265744736 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :And L can run any algorithm.
< 1265744743 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :sure it can't
< 1265744749 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :*Kipple* can run any algorithm.
< 1265744756 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :But Kipple can, and it can run any Kipple algorithm.
< 1265744757 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :L can run any algorithm written in Kipple.
< 1265744770 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :That statement was absurd, no? :)
< 1265744781 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :i think so.
< 1265744800 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :The computer L can simulate Kipple. And the computer Kipple (by merit of being TC) can simulate Scheme, a superset of L.
< 1265744806 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :So L and Kipple are Turing-equivalent.
< 1265744829 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :"The computer L" cannot print a list of primes
< 1265744830 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Since Kipple and any TC language are *also* Turing-equivalent... L is TC.
< 1265744831 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :have anyone proved church turing thesis??
< 1265744837 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :lament: Yes it can.
< 1265744842 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :lament: Well, it can, but only on the right input.
< 1265744842 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :quantum physics is evidence for church turing isn't it
< 1265744844 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :there exists an algorithm to print a list of primes, L cannot do it, therefore L is not TC
< 1265744853 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :lament: But L can do it.
< 1265744865 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :fine. L is TC then.
< 1265744865 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :The computer L, given no input, cannot print a list of primes.
< 1265744883 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :ok you win L is TC
< 1265744884 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :lament you have be careful there because imagine a language that always printed HELLO when it started
< 1265744901 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :it's cannot print hte list of primes without first printing HELLO, but it could still be TC
< 1265744906 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265744914 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :in general... you have to worry about input/output interpretations
< 1265744914 0 :Asztal!~asztal@host86-169-6-12.range86-169.btcentralplus.com JOIN :#esoteric
< 1265744939 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :cpressey, either way this results in some issues for the esolang community as far as I can tell
< 1265744942 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy: Church-Turing thesis is trivially proven.
< 1265744942 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: I agree with pikhq
< 1265744947 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :what
< 1265744952 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: we just consider the input to be part of the program code
< 1265744963 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :either TC doesn't really mean much, or a lot of the proofs are invalid
< 1265744963 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy: See compilers.
< 1265744966 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: because what else can we consider it as? turing machines don't have IO
< 1265744968 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :you might be thinking of a different theorem than me pikhq
< 1265744977 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: with that clarification, L is obviously TC
< 1265744998 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :lament: Yes they do -- Tape. :P
< 1265745007 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :what's your statement of it?
< 1265745017 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :well yeah.
< 1265745027 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :code = data ..
< 1265745037 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy: If an algorithm exists, there exists an equivalent Turing machine for it.
< 1265745047 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :pikhq and you know how to prove it??
< 1265745054 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :hm
< 1265745068 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :it should be possible to write a brainfuck compiler in befunge93 btw
< 1265745076 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :I have several algorithms for converting algorithms to Turing-complete languages.
< 1265745082 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric ::/
< 1265745083 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :I mean, it is trivial to compile it to unoptimised C
< 1265745129 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :are you reading it as: if a turing machin exists, there exists an equivalent turing machine for it?
< 1265745135 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :because that's now how I read it
< 1265745251 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy: Turing machines aren't algorithms.
< 1265745267 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Though by the Church-Turing thesis, they can be equivalent to them.
< 1265745280 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :okay I can't see what you mean really
< 1265745282 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Algorithms always halt, by many definitions.
< 1265745461 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :what about
< 1265745461 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :http://plato.stanford.edu/entries/church-turing/
< 1265745461 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :"Misunderstandings of the Thesis"
< 1265745598 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :If an algorithm can be described, it can be described with a Turing machine, is how I take pikhq's statement.
< 1265745631 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric : 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
< 1265745636 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :that is, over all of them
< 1265745669 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: Quite.
< 1265745679 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :what do you can it then
< 1265745692 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :... English?
< 1265745697 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Please, speak English?
< 1265745697 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :lol
< 1265745763 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :har
< 1265745765 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: Well, people seem to abuse the word "algorithm" a lot too. To me a heuristic is not an algorithm
< 1265745792 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Maybe there is an "algorithm" for interpreting brainfuck, even though it may never halt
< 1265745799 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :eople abuse church turing
< 1265745812 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :But I think someone famous (Knuth?) wrote a definition of algorithm, and "always halt" was in it.
< 1265745829 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :cpressey, what about an algorithm for parsing a stream of unknown length, it would depend on the length of the stream
< 1265745843 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :productive
< 1265745849 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :if you define algorithms as processes that can be described by a turing-machine, then church-turing is trivially true
< 1265745861 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :but that's not really how they're defined for the purposes of the thesis itself
< 1265745868 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :lament yeah which is why I don't think that's a correct interpretation of church-turng
< 1265745870 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :lament: More of a tautology, really.
< 1265745871 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :yes
< 1265745878 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :pikhq: right
< 1265745882 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :the link I have given goes into this in some detail
< 1265745886 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :now church and turing were pretty smart guys
< 1265745891 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :^^^^^^^^^^^^^^
< 1265745892 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :and they didn't think this was a tautology
< 1265745902 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :lament you are really good at explaining
< 1265745910 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric : lament: More of a tautology, really. <-- a tautology is trivially true though
< 1265745913 0 :gm|lap!~gm@unaffiliated/greasemonkey JOIN :#esoteric
< 1265745913 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :ty
< 1265745919 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :AnMasterXD
< 1265745919 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: Well, of course.
< 1265745932 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: That's a tautology right there. ;)
< 1265745942 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :pikhq, quite
< 1265745992 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :haha
< 1265745995 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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
< 1265746008 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :'"a tautology is trivially true" is trivially true is a tautology' is trivially true
< 1265746041 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :yeah like what if you happend upon a HALTING ORACLE one day
< 1265746045 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :and you made a computer out of it
< 1265746051 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :then turing machines aren't enough
< 1265746058 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy, exactly
< 1265746070 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :quantum computation IS turing equivalent though
< 1265746076 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy: By merit of having a halting oracle, you're out of the realm of Turing machines. ;)
< 1265746084 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :(in terms of /what/, but not in terms of algorithmic complexity)
< 1265746093 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :And the halting oracle is like Bigfoot. No one's caught one, but they can't prove it's not out there somewhere.
< 1265746093 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :so I think that gives EVIDENCE for Church-Turing
< 1265746138 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :This is *math*, not science!
< 1265746170 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Church-Turing is philosophy, not math.
< 1265746185 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Turing-*complete* is math :)
< 1265746213 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :I thought Church-Turing Thesis was philosophy
< 1265746215 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :not really math ?
< 1265746229 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Somewhere in the math/philosophy overlap.
< 1265746364 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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"?
< 1265746430 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265746431 0 :oklopol!unknown@unknown.invalid PART #esoteric :?
< 1265746438 0 :oklopol!~oklopol@a91-153-117-63.elisa-laajakaista.fi JOIN :#esoteric
< 1265746446 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :argh
< 1265746550 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :cpressey, hm... for the latter, if L allows some variable names to be changed or other such trivial things, then that isn't enough
< 1265746567 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: Damn, you're right.
< 1265746576 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :That would be rather humorous.
< 1265746602 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :"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.
< 1265746608 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :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
< 1265746668 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oklopol, I think the known "sufficient" isn't equal to the known "necessary" for defining TC. At least that is my impression
< 1265746677 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :thus the resulting disagreement
< 1265746695 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :can you elaborate on that?
< 1265746715 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oklopol, I'm sure you are familiar with the phrase "necessary and sufficient"?
< 1265746724 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :sure
< 1265746744 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :well, we know some things are necessary for TC, everyone agrees on some minimums.
< 1265746747 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :but what are the known necessaries and sufficients here
< 1265746749 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :hmm
< 1265746756 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :yeah i suppose
< 1265746756 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :Also, we know some sufficient examples of them
< 1265746765 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :it is just that we don't know the minimum sufficient set
< 1265746794 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oklopol, did that make it clearer?
< 1265746820 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :yep
< 1265746868 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265746885 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :At least, not outside ivory towers.
< 1265746896 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: no, it really didn't
< 1265746904 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :cpressey, oh? Also what exactly is recursive sets. It sounds like something that allows Russell's paradox
< 1265746956 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: it means the set of languages that are recursive, the sets aren't recursive in any way
< 1265746960 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :R
< 1265746975 0 :ais523!unknown@unknown.invalid NICK :scarf
< 1265746975 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :http://www.amazon.com/Recursively-Enumerable-Sets-Degrees-Perspectives/dp/0387152997
< 1265746978 0 :scarf!unknown@unknown.invalid NICK :ais523
< 1265746985 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oklopol, ah well, as long as we avoid mathematical barbers I'm happy ;)
< 1265746986 0 :ais523!unknown@unknown.invalid NICK :scarf
< 1265746989 0 :scarf!unknown@unknown.invalid NICK :ais523
< 1265746990 0 :ais523!unknown@unknown.invalid NICK :scarf
< 1265746995 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :scarf, stop it
< 1265747002 0 :scarf!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: not deliberate, client bug
< 1265747004 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :well freenode rate limits it
< 1265747008 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :thank god for that
< 1265747017 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Yeah, "recursive set" is kind of a misnomer - the sets of values defined by recursive functions, is where i think it comes from
< 1265747020 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :wow anmaster calm down
< 1265747047 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :scarf, good
< 1265747078 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :oklopol: I'd be surprised if it didn't have a fairly good definition w.r.t. sets.
< 1265747092 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :R is the set of languages for which there it a tm that accepts them and always halts
< 1265747102 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :RE is the set of languages for which there is a tm that accepts them
< 1265747116 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :(halts on trues)
< 1265747121 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :a language = a set of inputs?
< 1265747138 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Yes
< 1265747146 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :as in a FSA?
< 1265747168 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :cpressey, ^
< 1265747179 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: the language of such words that if you put them on the tape and run the tm, ...
< 1265747188 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :As in, FSA accept certain languages (= sets of strings), yes.
< 1265747198 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :ah same meaning of "language" then
< 1265747199 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :right
< 1265747257 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :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..."
< 1265747288 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :I thought in this context your set was "Turing-complete" if there was a surjection from your set onto RE
< 1265747292 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Or something like that
< 1265747306 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :from what set?
< 1265747308 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :uhu
< 1265747339 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :is it a set that is turing complete, or a computational model?
< 1265747371 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :(i've never heard the term in recursion theory context.d)
< 1265747373 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :*-d
< 1265747376 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :In recursive function theory, it's a set. But it can be the set of strings (= language) accepted by a computer.
< 1265747430 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265747438 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :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
< 1265747439 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :so, what kind of surjection exactly? there's a surjection from the naturals to RE.
< 1265747443 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :err
< 1265747449 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :well reals at laest
< 1265747453 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :oklopol: I have no idea. I only half-remember this stuff. But it's in that book.
< 1265747456 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :*reals
< 1265747461 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :i see
< 1265747479 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :cpressey, hm is L just TC or is it actually equivalent to an UTM or to lambda calculus or such?
< 1265747490 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265747492 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :that might be the key to this (word trickery that is)
< 1265747522 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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. :)
< 1265747539 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :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)
< 1265747541 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :cpressey, by the way, I don't think I ever seen any example of an uncomputable problem
< 1265747567 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: um. Halting problem?
< 1265747570 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: i have no idea what an isomorphism is in this context
< 1265747572 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster, rendering the mandelbrot set
< 1265747576 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :cpressey, oh duh
< 1265747576 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :it's uncomputable
< 1265747586 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :oklopol: one-to-one and onto?
< 1265747592 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy, err?
< 1265747592 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :that's a bijection
< 1265747595 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy, how so?
< 1265747601 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: but still semi-decidable :)
< 1265747610 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :still that's just a question of cardinality, i don't see how that helps
< 1265747611 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy, I mean, isn't that fractable one of the most popular ones arround
< 1265747611 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :oklopol: Sorry, that was what I meant.
< 1265747613 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :around*
< 1265747618 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :cpressey, true
< 1265747618 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :yes that's why I mentioned it
< 1265747628 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy, so how can it then be uncomputable?
< 1265747641 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :another thing that's uncomputable is solomonoff inductioon
< 1265747652 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: no worries, it's the isomorphism of the category Set
< 1265747674 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy, "solomonoff inductioon"?
< 1265747679 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :sure about that spelling?
< 1265747719 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric ::/
< 1265747720 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :what the fuck
< 1265747728 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :that was obviously a typo
< 1265747750 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy, right, I wasn't sure about the first being correctly spelt either
< 1265747755 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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)
< 1265747773 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :cpressey, hrrm
< 1265747819 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :also I thought the halting problem was *undecidable* not *uncomputable*
< 1265747819 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265747825 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :but maybe they are the same thing?
< 1265747830 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :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
< 1265747833 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: I think they are more or less the same thing.
< 1265747866 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :hm okay
< 1265747877 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :RE intersect co-RE, that's the "completely undecidable" set I was thinking of
< 1265747886 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :It's been a while though.
< 1265747909 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: it's pretty non-contrived to check if a given first-order arithmetic formula if true
< 1265747925 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :oklopol: But isn't that RE?
< 1265747935 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :you can implement tm's in that easily, and obviously it's in RE iff it's in co-RE
< 1265747943 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :so it can't be in either.
< 1265747960 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :for a very non-obvious meaning of obvious, i suppose
< 1265747993 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :hm
< 1265747998 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :"cpressey: RE intersect co-RE, that's the "completely undecidable" set I was thinking of" <<< no that's R
< 1265748005 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :the completely decidable set
< 1265748014 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :oklopol: Indeed.
< 1265748051 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Still, I don't see how "check if a given first-order arithmetic formula is true" isn't in RE
< 1265748060 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Can't I enumerate them?
< 1265748071 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Check each one, if it's true, spit it out?
< 1265748072 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :it sounds like equation solving? Or maybe I completely misread that
< 1265748084 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :how do you check one?
< 1265748084 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :If it runs forever, so be it?
< 1265748097 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :the arithmetic formulas are first-order, they can quantify over integers
< 1265748130 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :oklopol: Try all possible proofs of its truth nondeterministically?
< 1265748151 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :and who says everything has a proof?
< 1265748158 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :what exactly is a "first-order arithmetic formula"
< 1265748162 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :in fact, this is one proof that there is no proof for everything
< 1265748182 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :oklopol: Granted.
< 1265748214 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: you have universal and existential quantification over integers, addition, multiplication and equality check, and then boolean operators.
< 1265748237 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: For example: For all integers x, x * 1 = x.
< 1265748259 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oklopol, you mean like Exists x ( x * 2 = 4 ) ?
< 1265748264 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :yes
< 1265748265 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :I had forgotten how slippery those were :)
< 1265748282 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oklopol, well that is easy to prove. equation solving
< 1265748290 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :and even it can
< 1265748296 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Still seems like you could enumerate the ones that do have proofs.
< 1265748297 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :yeah, that one is easy to prove
< 1265748305 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :can't* be solved exactly you can often solve them numerically afaik
< 1265748312 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :at least for first order ones
< 1265748315 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :numerically, huh
< 1265748324 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :you did hear these are integers, right?
< 1265748335 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oklopol, is that first order as in "no differentiation"?
< 1265748339 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :no
< 1265748349 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :it's as in no quantification over more complicated things than numbers
< 1265748393 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :differentiation is not very sensible with integers
< 1265748500 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :differentation no foobars
< 1265748504 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265748532 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :do you realize that's just a matter of cardinalities?
< 1265748542 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Now that I typed it out, yes :)
< 1265748546 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :i mean you can just take an arbitrary set that has the same amount of elements
< 1265748566 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :so, i think we need a slightly different definition
< 1265748581 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :So I'm misremembering it. Maybe it was "computable mapping", for some definition of "computable".
< 1265748594 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Turing-machine computable would be most likely
< 1265748704 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oklopol, ah okay
< 1265748841 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :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?
< 1265748859 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :http://en.wikipedia.org/wiki/Turing_degree
< 1265748862 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :all the roots?
< 1265748879 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy, well yes, if you just had square root it would be trivial to match it up to Q
< 1265748886 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Turing complete = Turing degree 0'
< 1265748892 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :with cube root and so on
< 1265748900 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :then it would be much larger I suspect
< 1265748903 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :oh well it's Q x N I guess
< 1265748908 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :which is countable again
< 1265748912 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy, oh? really?
< 1265748923 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :Q x N because you can represent the n'th root of q as a pair: (q,n)
< 1265748924 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :how would it be countable
< 1265748943 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :because countable x countable is countable (cantors zig-zagonalization theorem)
< 1265748944 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy, true, But do show where you would begin counting
< 1265748952 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :hm
< 1265748954 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oh right
< 1265748957 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :you could go like that
< 1265748959 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :indeed
< 1265748963 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :duh
< 1265749055 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :"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.
< 1265749097 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :(so first problem set has you writing stuff in thue, you gotta love aocp)
< 1265749119 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :wow
< 1265749124 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :I can't do ANYTHING with thue
< 1265749130 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :I should get this book
< 1265749154 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :Isn't set of algebraic numbers also countably infinite (and set of all integer roots of all rationals is strict subset)?
< 1265749188 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :4. He's *Knuth*.
< 1265749211 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric ::(
< 1265749224 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :Ilari: sure
< 1265749248 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :well i don't get the part in parens
< 1265749272 0 :pikhq!unknown@unknown.invalid TOPIC #esoteric :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
< 1265749283 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :unless by rationals you mean rational polynomials or something
< 1265749289 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oklopol, "aocp"? did you mean "taocp"?
< 1265749295 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :i've heard aocp more
< 1265749298 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :used to call it taocp
< 1265749312 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :I call it The Art of Computer Programming.
< 1265749378 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oklopol, aocp took me a few seconds to figure out what it meant. And only managed it because Knuth was mentioned in there
< 1265749379 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :fancy
< 1265749406 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: i've used taocp and being told it's usually called aocp.
< 1265749411 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :been
< 1265749422 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oklopol, I never heard aocp before. Often heard taocp though
< 1265749451 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :well fuck
< 1265749470 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :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).
< 1265749490 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :computable reals are countable too
< 1265749492 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :Ilari: no that's not true
< 1265749513 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :and that set is equivalent wrt all first order theorems, I think (?)
< 1265749514 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :you can just take say pi, and have a countable superset that does not contain an infinite number of numbers that are not algebraic
< 1265749517 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :oklopol, googling: taocp gives relevant hits. aocp doesn't give any relevant hits
< 1265749519 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :now if you want to to be a field...
< 1265749527 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :only checked first result page for each
< 1265749545 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy: Sure, sure; G"odel numbering of programs to compute them.
< 1265749550 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :oklopol: Going over that Turing degree page, I do believe it was "a mapping computable by TM" (Turing-reducible) now.
< 1265749553 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :pikhq, what was that?
< 1265749553 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: okay, then maybe whoever told me to say aocp was a weird-ass weirdo.
< 1265749557 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :pikhq, "o ?
< 1265749570 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :at least it looked like that here
< 1265749587 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: My attempt to type an umlaut. And didn't compose.
< 1265749612 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :pikhq, also you don't need to compose, it has it's own letter in unicode
< 1265749618 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :In fact, any field that is countably infinite and is strict superfield of algebraic numbers has infinite amount of numbers that are not algebraic.
< 1265749627 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: The compose *key*.
< 1265749629 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :Ilari: sure
< 1265749640 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :pikhq, oh
< 1265749650 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :pikhq, try: ö
< 1265749652 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :that's obvious really, you can just take all its integer multiples or something
< 1265749655 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Type it and an appropriate sequence and it generates Unicode.
< 1265749656 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :any sane keyboard layout has it
< 1265749657 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :;P
< 1265749665 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :if one of them was an algebraic number, then the original would've been too
< 1265749668 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: US-QWERTY doesn't.
< 1265749676 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :pikhq, I know what compose is, I have it on my menu key
< 1265749680 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :pikhq, I said sane
< 1265749685 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :you don't even have altgr...
< 1265749694 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :I've got compose on the Win key.
< 1265749706 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :pikhq, don't mess with my super!
< 1265749713 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: UNIX can treat the right AltGr just fine.
< 1265749721 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :pikhq, well yes
< 1265749721 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Erm. Right Alt as AltGR.
< 1265749763 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :interesting btw, tell me if you find a compose for ö
< 1265749775 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :ah found it
< 1265749777 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :"o
< 1265749781 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :pikhq, just reverse the order of them
< 1265749783 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :and it works
< 1265749788 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :as in o"
< 1265749805 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :AnMaster: I just didn't realise that my compose key doesn't work at all. :P
< 1265749816 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265749821 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :pikhq, oh? well then it isn't mapped there any more I guess ;P
< 1265749830 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :I guess.
< 1265749858 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :i do like the idea of "infinite sum operator"
< 1265749872 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :maybe you could just have the "limit" keyword
< 1265749878 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :Ilari, sounds like a CAS?
< 1265749912 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :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...
< 1265749935 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :Ilari: you are joking right?
< 1265749940 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :Ilari, Taylor series?
< 1265749949 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :infinite sum operator?
< 1265749959 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :I don't beleive we've met
< 1265749987 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :also obviously an infinite sum operator can compute also the algebraic numbers, you don't need the polynomial root operator
< 1265749990 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :well, it makes perfect sense. It is just that it would be impossible to run any program in it I think
< 1265750004 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :also does it take an infinite amount of rationals and sum them or what?
< 1265750006 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :e = infinite_sum(1/n!,n=0...), pi = sqrt(6 * infinite_sum(1/n^2,n=1...))
< 1265750019 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :pi = sqrt(2)
< 1265750023 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :Ilari: so it takes as input what exactly?
< 1265750047 0 :olsner!unknown@unknown.invalid PRIVMSG #esoteric :I wished this was all obvious to me
< 1265750049 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :oklopol: One-argument function and lower bound.
< 1265750056 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :one argument?
< 1265750061 0 :olsner!unknown@unknown.invalid PRIVMSG #esoteric :seems useful
< 1265750061 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :and what's that argument
< 1265750068 0 :scarf!unknown@unknown.invalid NICK :ais523
< 1265750076 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :an infinite set?
< 1265750077 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :oklopol: lower bound, lower bound + 1, ...
< 1265750090 0 :AnMaster!unknown@unknown.invalid PRIVMSG #esoteric :Ilari, just use Σ and put a ∞ on top
< 1265750098 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :what
< 1265750105 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :idgi
< 1265750109 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :If you take more sophisticated operations as primitives, you can consider more sophisticated sets computable. Surprise! :)
< 1265750147 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :But one never reaches reals...
< 1265750148 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Now I think we have to argue about what operations are "obviously" the most primitive.
< 1265750154 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :Ilari: why do you need infinite sums, why not just an operator that takes a cauchy sequence of rationals and returns the corresponding real?
< 1265750196 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :so
< 1265750230 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :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, ..."
< 1265750241 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :well, or an infinite set anyway
< 1265750284 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :oklopol: Lower bound is 0 there.
< 1265750311 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :lower bound for e?
< 1265750317 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :e < 2
< 1265750338 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :then you have lower bound + 1, ..., so... you'll have 1 in there, then 2, 3, ...?
< 1265750353 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :0, 1, 2, 3, 4, 5, 6, 7, 8...
< 1265750369 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :and where exactly, i don't think you're being very clear
< 1265750397 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :ohhhhh
< 1265750398 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :while (true) n := n + 1 ???
< 1265750402 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :okay so
< 1265750424 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :do you mean it takes a lower bound, and a function, then takes the infinite sum of f(lower bound), f(lower bound + 1), ...?
< 1265750433 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :ahhhhh
< 1265750453 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :"Ilari: oklopol: One-argument function and lower bound." <<< totally misinterpreted this, sorry
< 1265750488 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :so, basically you just give it an infinite set of rationals, and it returns the corresponding real
< 1265750505 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :but obviously you still get exactly the computable reals, because you have to express the set somehow
< 1265750512 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :in your case with a function
< 1265750662 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265750866 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :Statistics fun: Generate random numbers [0,1). Then map them by x -> 1/(1-x)². Calculate approximate expectation value. Heh, heh...
< 1265751571 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265751629 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :So!
< 1265751647 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :I think this means it is *not* enough to just say "There, I've coded a TM in my language, my language is TC."
< 1265751666 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :Ilari the expected value is divergent?
< 1265751673 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :I'm just guessing
< 1265751676 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :But I'm not sure.
< 1265751761 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy: The expectation value is "infinite".
< 1265751769 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :ACTION would be interested to hear what ais523 has to say about all this.
< 1265751778 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: haven't been paying attention
< 1265751780 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :summary?
< 1265751827 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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?
< 1265751831 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :okay
< 1265751838 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :I don't know statistics :P
< 1265751848 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :whichs sucks because I went to classes for it..
< 1265751869 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :MissPiggy: Some distributions are extremely ill-behaved.
< 1265751906 0 :olsner!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: I smell a HQ9+ dialect
< 1265751922 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: yes, I think
< 1265752167 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :ais523: Then what would you call the property "I can map any Turing-machine to a (meaningfully different) program in this language"?
< 1265752190 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :hmm, rather than program + input, like TCness requires
< 1265752214 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :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...
< 1265752286 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: I'm not sure that there is a name
< 1265752290 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :although it's an interesting property
< 1265752478 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265752503 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :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
< 1265752528 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Indeed :)
< 1265752571 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :we can put bounds on "definitely TC" and "definitely not TC", but there's a grey area
< 1265752610 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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 :) )
< 1265752647 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :yay
< 1265752655 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Well, "property 2" does imply TC -- if I can map an arbitrary TM into a language, that language must contain at least one UTM
< 1265752665 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :yep
< 1265752671 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :"property 2" is a terrible name though
< 1265752704 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :it has a kind-of ring to it
< 1265752711 0 :Gregor!unknown@unknown.invalid PRIVMSG #esoteric :"Where do you live?" "Compound 3, property 2."
< 1265753279 0 :Ilari!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265753327 0 :SimonRC!unknown@unknown.invalid QUIT :Ping timeout: 246 seconds
< 1265753609 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :tubes are cool.
< 1265753882 0 :MissPiggy!unknown@unknown.invalid PRIVMSG #esoteric :ACTION tubes lament
< 1265753960 0 :SimonRC!~sc@fof.durge.org JOIN :#esoteric
< 1265754166 0 :BeholdMyGlory!unknown@unknown.invalid QUIT :Read error: Connection reset by peer
< 1265754465 0 :tombom!unknown@unknown.invalid QUIT :Quit: Leaving
< 1265754808 0 :MigoMipo!unknown@unknown.invalid QUIT :Remote host closed the connection
< 1265756953 0 :oerjan!~oerjan@hagbart.nvg.ntnu.no JOIN :#esoteric
< 1265757574 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric : 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?
< 1265757596 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :the cardinality of the set of algebraic numbers is still aleph_0, if that's what you mean
< 1265757615 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :there are only a countable number of polynomials, and a finite number of roots of each
< 1265757624 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :he said "all the roots" though
< 1265757626 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :*polynomials over the rationals
< 1265757631 0 :lament!unknown@unknown.invalid PRIVMSG #esoteric :that's a lot of roots!
< 1265757652 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :um the algebraic numbers _are_ all the roots of rational polynomials
< 1265757660 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :essentially by definition
< 1265757969 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric : ais523: Then what would you call the property "I can map any Turing-machine to a (meaningfully different) program in this language"?
< 1265758018 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :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)
< 1265758052 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :basically both would have to do with not having to translate IO
< 1265758087 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :(i don't recall those terms were official though, we may have just made them up on the spot)
< 1265758150 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :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
< 1265758164 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :oerjan: I think you're talking about something largely different.
< 1265758177 0 :Sgeo_!unknown@unknown.invalid PRIVMSG #esoteric :Should I write a BF interpreter in Haskell? (Yes, I know there is one already, but this is for my own education)
< 1265758184 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Alphabet doesn't enter into this problem at all that I can tell.
< 1265758214 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: um in that case i don't know what you mean
< 1265758259 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :or maybe you mean that the program and input must be translated _separately_?
< 1265758271 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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)).
< 1265758271 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :remember, TMs take input on their tape, in their alphabet
< 1265758279 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :oerjan: Is L Turing-complete?
< 1265758312 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :you can write a computable reduction from any TM with input to an L program with input.
< 1265758330 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :but scratch "input" from your statement, and you can't
< 1265758354 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :but there are TC concepts with no input at all
< 1265758372 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :you have to include input in the whole, otherwise TC makes no sense
< 1265758387 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :e.g. a lambda calculus computation has no input
< 1265758399 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :it's just a reduction of a term
< 1265758434 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Then, is it a function? What is its domain?
< 1265758450 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :um what is a function?
< 1265758462 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :A mapping from one set to another?
< 1265758479 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :er ambiguous question
< 1265758491 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :*um what are you asking whether is a function
< 1265758494 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Sorry.
< 1265758501 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Is your lambda term a function?
< 1265758530 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :a lambda term is a string, at least that's one way of modeling them
< 1265758546 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: A "lambda term" is one way of *defining* a function.
< 1265758560 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :That is, defining what "function" means.
< 1265758582 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :pikhq: OK. What is the domain of the function defined by a lambda term?
< 1265758589 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :pikhq: i think that confuses things even more
< 1265758593 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: ignore pikhq
< 1265758598 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Okay, then.
< 1265758617 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: Set of functions to set of functions? :P
< 1265758620 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Anyways.
< 1265758625 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :a lambda function is a _symbolic_ term. that it can be interpreted as a function is irrelevant to the TC-ness of LC
< 1265758627 0 :pikhq!unknown@unknown.invalid PRIVMSG #esoteric :Carry on, Oerjan.
< 1265758674 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :a lambda term can be reduced using the alpha, beta, and if you want eta reductions
< 1265758701 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :then you can ask whether this reduction can ever reach a given term, such as \x y -> x
< 1265758716 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :(a common implementation of a boolean value)
< 1265758748 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :One sec.
< 1265758763 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :I just realized you never gave me a direct answer. Is L Turing-complete?
< 1265758773 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :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
< 1265758778 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: i think so
< 1265758864 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :For the record, I'm leaning towards: I don't think it is.
< 1265758918 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Now I'm all confused about lambda terms, and I don't know where to begin explaining why, though.
< 1265758969 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :(i've been using haskell notation for the lambda terms btw)
< 1265759015 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265759061 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :i didn't say a single lambda term was TC
< 1265759081 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :Well, you said "but there are TC concepts with no input at all" -- what should I make of that?
< 1265759106 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: there are
< 1265759113 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :you have a program that runs all turing machines in parallel
< 1265759117 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :and report when each one halts
< 1265759122 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :that's a UTM even without input
< 1265759126 0 :ais523!unknown@unknown.invalid PRIVMSG #esoteric :*and reports
< 1265759138 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :O_o
< 1265759195 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: i was just presenting LC as an example of a TC concept without input
< 1265759213 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :or rather, without input distinct from the program
< 1265759288 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265759288 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :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
< 1265759316 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: ah but L takes an input: a program + that program's input
< 1265759351 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :oerjan: Yes. But L *requires* certain inputs to do certain things. Lambda terms, TMs, etc don't.
< 1265759377 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :A TM can overwrite all of the input given to it with "hardcoded" stuff of its own choosing. L can't.
< 1265759395 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :I mean, L programs can't.
< 1265759398 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :the thing i am saying is that for TC-ness it is wrong to distinguish a part of input that is called the "program"
< 1265759400 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :There's only one, and it can't.
< 1265759493 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :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
< 1265759497 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: oh obviously RE-complete has a good definition. it's just that isn't a decent definition for turing-completeness
< 1265759550 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :'k, I'm officially completely lost.
< 1265759616 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :oklopol: Why not?
< 1265759682 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :oerjan: What does the "that" in "that's just because..." refer to?
< 1265759726 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: that TMs can overwrite things - this is irrelevant to what they can _compute_
< 1265759765 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :that's just mechanics.
< 1265759769 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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.
< 1265759798 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :well sure but a TM that ignores its input is trivial, computationally
< 1265759841 0 :oerjan!unknown@unknown.invalid PRIVMSG #esoteric :the computational content of a TM is its function from input tapes to final state, and possibly output tape
< 1265759869 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :cpressey: because some people want more complex starting patterns than finite strings
< 1265759880 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :i guess no other reason
< 1265759889 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :for recursion theoretical purposes
< 1265759919 0 :cpressey!unknown@unknown.invalid PRIVMSG #esoteric :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 :)
< 1265759928 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :IO stuff is obviously another issue, but we can just ignore that completely i guess
< 1265759940 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :or say it's part of the program
< 1265759942 0 :oklopol!unknown@unknown.invalid PRIVMSG #esoteric :or something