search of the:   for: 
code logs -> 2006 -> Thu, 07 Dec 2006< code.20061206.log - code.20061208.log >
--- Log opened Thu Dec 07 00:00:02 2006
00:23 Ev3 [~-@87.72.36.ns-26407] has joined #Code
00:31 Janus [~Cerulean@Nightstar-10302.columbus.res.rr.com] has joined #Code
01:36 MyCatOwnz [~mycatownz@Nightstar-379.dsl.in-addr.zen.co.uk] has quit [Quit: Textuality!]
02:29 Vornicus-Latens is now known as Vornicus
02:34 Janus [~Cerulean@Nightstar-10302.columbus.res.rr.com] has quit [Quit: Well, I'm grounded~ See ya later.]
04:50 ReivWork [~reaverta@IRCop.Nightstar.Net] has joined #Code
04:53
<@ToxicFrog>
Argh, I need to put fetchmail in my .bashrc or something.
04:55 ReivWork is now known as Reiver
06:00
< Reiver>
Theoretics question.
06:00
< Reiver>
I am trying to remember the name and/or concept of a theory that may or may not have to do with Turing, and Turing Complete/Turing Machines.
06:01
<@ToxicFrog>
Ok...
06:01
<@ToxicFrog>
I just wrote an exam on this, so I may be able to help you.
06:01
< Reiver>
Something about it is theoretically possible to have a computer able to compute anything, and many languages operate under that assumption, but in reality you have time/memory constraints that mean that they're not really capable of such?
06:02
<@ToxicFrog>
Umm.
06:02
<@ToxicFrog>
I don't know a formal name for anything along those lines; McM, have you any insights?
06:02
< Reiver>
It is entirely possible that I have the core premise slightly off.
06:03
< Vornicus>
Complexity theory deals with how long/how much memory it takes to compute something.
06:03
< Reiver>
My memory is flaking out on me. It's frustrating.
06:03
<@ToxicFrog>
(also, a Turing machine isn't "can compute anything". It's "can compute anything that can be computed with a Turing machine", which is not the same thing.)
06:03
< Reiver>
...Right
06:03
< Reiver>
What cannot be computed on a Turing Machine?
06:03
<@ToxicFrog>
(for example, can't solve the halting problem.)
06:03
< Reiver>
And/or what can.
06:03
< Reiver>
Halting problem?
06:03
<@ToxicFrog>
Given a program P, does it finish in finite time or run forever?
06:04
< Vornicus>
The halting problem: given an arbitrary turing program, you generally cannot tell without actually running it whether it will ever finish.
06:04
<@ToxicFrog>
More generally, there is no algorithm that will determine, for all programs in the set of turing programs, whether a given program will finish.
06:05
< Reiver>
There is a reason why, I am assuming.
06:05
< Vornicus>
Yes.
06:05 * Reiver has a guess, is wondering if it's that obvious though.
06:05
< Vornicus>
if there's an algorithm...
06:05
< Vornicus>
Then it can be written as a turing program...
06:06
<@ToxicFrog>
The proof is fairly simple.
06:06
< Vornicus>
...which will halt if the input program does not.
06:06
<@ToxicFrog>
Basically, write a program that runs itself through your halt-detector, and if the result is "never halts", halt.
06:06
<@ToxicFrog>
If the result is "halts", loop forever.
06:07
< Vornicus>
...so what if you run the turing program through itself?
06:07
<@ToxicFrog>
Your head explodes. I may have explained this poorly.
06:07 * Vornicus was explaining
06:07
< Vornicus>
but yours is more right than mine.
06:07
<@ToxicFrog>
Aah.
06:07
< Reiver>
That's easy.
06:07
< Reiver>
The program returns i. :p
06:07
< Vornicus>
but does it halt or not?
06:08
<@ToxicFrog>
Anyways. The point is, this is an undecidable problem and thus not solvable by a Turing machine.
06:08
< Reiver>
May I ask why you'd write a program that never halts if the core program does so?
06:09
< Vornicus>
To prove that it's impossible to create a halt detector.
06:09
<@ToxicFrog>
Aha. Perhaps you were thinking of the Church-Turing Hypothesis?
06:09
< Reiver>
TF: Maybe?
06:10
<@ToxicFrog>
Which basically says "any computable function can be implemented on a Turing machine"
06:10
<@ToxicFrog>
And is not, IIRC, formally provable, but looks plausible.
06:10
< Reiver>
Oh.
06:11
< Reiver>
I could've sworn there was something that went the other way.
06:11
<@ToxicFrog>
http://en.wikipedia.org/wiki/Church-Turing_thesis
06:12
< Reiver>
It was also related to "Turing-complete" languages or such; where things like C/C++ and most modern languages are not really "Turing-complete" because they would require infinite memory to do so, but they like to pretend they are and just crash if they run out.
06:12
<@ToxicFrog>
Err.
06:12
<@ToxicFrog>
C is Turing-complete.
06:13
<@ToxicFrog>
If you give it an infinite amount of memory, it can do anything a Turing machine can do.
06:13
<@ToxicFrog>
However, the machines it runs on do not have infinite memory.
06:13
< Reiver>
Right, but it doesn't have infinite memory so therefore it can't /actually/ do that. Yes?
06:13
<@ToxicFrog>
This is, however, a function of problem size, not of the nature of the language itself.
06:13
< Reiver>
I think it was discussed here before...
06:14 * Reiver frowns.
06:14
< Vornicus>
Turing machines are a purely mathematical concept
06:14
< Reiver>
Something about being able to only read one step ahead, an arbitary number of steps ahead, and then two other more powerful versions.
06:14
<@ToxicFrog>
That's parsing.
06:15
< Vornicus>
The universe as a whole cannot have a universal turing machine in it.
06:15
< Reiver>
Because there is not infinite resources to do it, yes?
06:15
< Vornicus>
indeed
06:16
<@ToxicFrog>
Which is related, in that languages can be classified based on what kind of machine you need to recognize them.
06:16
<@ToxicFrog>
Type-0 grammars require a Turing machine equivalent to recognize.
06:17
< Reiver>
Would you mind running that list of the grammars or whatever it was, for me?
06:18 * Reiver has a vauge hunch this may help a substantial deal. His brain is not co-operating, so...
06:18
<@ToxicFrog>
Type-3 is regular expressions and requires a deterministic finite automaton.
06:19
<@ToxicFrog>
Type-2 is context-free grammars and requires a pushdown automaton. Most programming languages are of this type, although PDAs are in practice not used for parsing.
06:19
<@ToxicFrog>
Type-1 is context-sensitive. I don't know much about these.
06:19
<@ToxicFrog>
Type-0 is unrestricted and requires a Turing machine.
06:22
<@ToxicFrog>
(note that these requirements are for /parsing/ the language; they have nothing to do with its expressive power or lack thereof)
06:23
< Reiver>
Aha.
06:23
< Reiver>
Right. Thanks.
06:23
< Reiver>
That wasn't what I was thinking of, but now I know I was poking at the wrong line of thinking~
06:27
< Reiver>
I don't know. I have a suspicion my memory is a poorly melded combination of the Type-x conversation, a little bit of the Church-Turing thesis, and a dim memory of a comp sci lecture about How Quantam Computers Will Fuck Everything Up.
06:27
<@ToxicFrog>
Possibly.
06:27
<@ToxicFrog>
Quantum computing is ZOMG BRAINFOAM for me, personally.
06:27
< Reiver>
(Or at least make NP-hard problems and recursive problems and basically anything that required loops solvable in one iteration. ...If one extremely insane iteration.)
06:27
< Vornicus>
...I was gonna use that word!
06:28
<@ToxicFrog>
As for the Turing-completeness of a language - this means, roughly, "can express any algorithm that can be expressed in a Turing machine"
06:28
<@ToxicFrog>
It has nothing to do with whether it will actually run in a situation involving finite resources.
06:28
< Reiver>
I had some vauge recollection that A Universal Turing Machine was impossible, but quantam computers, if done right and cutting a few corners, may have been able to cheat to do it anyway.
06:29
<@ToxicFrog>
Vornicus: 194X?
06:29
< Vornicus>
zomg brainfoam?
06:29
<@ToxicFrog>
I got "brainfoam" (and the more correct quote "there's FOAM in my BRAIN!") from the spritecomic 194X.
06:29
< Vornicus>
I got it from you.
06:30
<@ToxicFrog>
Aah. Sweet.
06:30 * Vornicus is randomly reminded of an ancient "don't do drugs" ad.
06:30
< Vornicus>
"Where did you learn this?" "I learned it by watching you!"
06:30 * Reiver wonders if his vauge recollection is actually right or not.
06:31
<@ToxicFrog>
I really don't know, quantum computing gives me the jibblies.
06:31
< Reiver>
I do remember something about Quantam computer theory at the time having something about being able to solve travelling-salesman problems in one pass.
06:32
<@ToxicFrog>
As for the "universal turing machine" - I'm a bit rusty on this, but IIRC this just means "program is stored in memory rather than in the machine architecture"
06:32
< Reiver>
And theoretically be able to do any such "Search through this and give us the valid results" type thing likewise. Infinite recursions, or something, by basically skipping the whole discrete-variable thing and collapsing harmonic waveforms, or... something...
06:32
<@ToxicFrog>
Thing is, an actual Turing machine implements a /single program/ which is hardcoded (insofar as something abstract can be!) into the machine itself.
06:33
< Vornicus>
QUantum computing throws all previous attempts at encryption out the window.
06:33
<@ToxicFrog>
The "universal Turing machine" is the Turing machine to which you can feed the spec for any non-Universal Turing machine and it will behave as that machine.
06:33
< Reiver>
Rather than, to find how many times X shows up in array Y, making a loop that goes if(Y == 1) count++; through the array, it /just spits out/ "3".
06:33
< Vornicus>
what's this? an SHA checksum? Eh, just throw it out the machine.
06:33
< Vornicus>
at the machine.
06:34
<@ToxicFrog>
Vornicus: crypto also breaks badly if P==NP, but personally I don't think that's the case.
06:34
< Reiver>
It breaks not all crypto.
06:34
< Reiver>
It breaks the open-key crypto used on credit card transactions over the internet though. >.>
06:35
<@ToxicFrog>
No, but it breaks asymmetric-key crypto horribly.
06:35
< Reiver>
As that's not been proven secure, and has been proven actually otherwise via paralell processing and sheer numbercrunching
06:35
<@ToxicFrog>
Which is, err, basically the only crypto used for important stuff.
06:36
< Reiver>
As, IIRC, the key thing on quantam computing is that it does every possible combination at once and merely returns the ones that worked (And thus created a harmony, or something?).
06:36
<@ToxicFrog>
The first part, yes.
06:36
< Reiver>
I believe it also plays merry hell with finding primes.
06:36
<@ToxicFrog>
I have no idea how it determines which one worked.
06:36
< Reiver>
Well
06:37
< Reiver>
Our lecturer at the time was fiddling a lot with it, as far as I can tell.
06:37
< Vornicus>
The answer, obviously, is brainfoam.
06:37
< Reiver>
He was dumbing things down for a 1st year comp sci course. >.>
06:37
< Reiver>
Oh!
06:37
< Reiver>
Apparently it's also possibly to get the theoretical maximum perfect level of compression with it, too.
06:37
<@ToxicFrog>
I know a guy in the UW quantum computing lab, actually, and he's tried to explain this to me.
06:37
<@ToxicFrog>
But all that comes out is "Ia! Ia! Cthulhu fthagn!"
06:38 * Reiver giggles.
06:38
< Vornicus>
See?
06:39
< Reiver>
"You stick it in, and it sort of does everything at once in all possible combinations. Those that actually work give a... it's a bit like harmonies in music, in that everything else is fuzzy and thus collapses, but the harmonies, being cleaner and more stable, stay behind. Only there's no actual stability in place, as the unstable don't actually /happen/ they were merely /theoretically possible/, but I'm getting too complicated..."
06:39
< Reiver>
^ vauge metaquote of a lecture I heard 4 years ago.
06:40 AnnoDomini [~fark.off@Nightstar-29697.neoplus.adsl.tpnet.pl] has joined #Code
06:40
< Reiver>
Or at least that was the vauge metaphor that stuck.
06:41 * Vornicus would /very/ not like to write that circuit.
06:41
< Reiver>
Mental image of white noise of every combination, and those combinations that worked just snap into focus, while all the others fade.
06:41
< Reiver>
Only because it's quantam the ones that didn't work didn't so much fade as not happen, but this is brainfoam again.
06:42
< Reiver>
Because they had to be tested for it to work, but they also never happened, and and and and. Yes. Quantam is insane. It's also merely extremely scary.
06:42
< Reiver>
:)
06:42
<@ToxicFrog>
There's FOAM in my BRAIN!
06:42
<@ToxicFrog>
FOAM!
06:43
< Reiver>
But!
06:43
< Reiver>
The 'harmonies' are what I got out of it.
06:44
< Reiver>
"It tries everything at once in a single pass, and the bits that work just pop up clear as day."
07:20 Reiver is now known as ReivOut
07:50 ReivOut is now known as Reiver
08:55 Vornicus is now known as Vornicus-Latens
09:01 EvilDarkLord [althalas@Nightstar-17046.a80-186-184-83.elisa-laajakaista.fi] has quit [Ping Timeout]
10:00 You're now known as TheWatcher[wr0k]
10:03 Ev3 [~-@87.72.36.ns-26407] has quit [Ping Timeout]
10:19 Reiver is now known as ReivZzz
11:20 EvilDarkLord [althalas@Nightstar-15301.a88-115-211-62.elisa-laajakaista.fi] has joined #code
11:53 EvilDarkLord [althalas@Nightstar-15301.a88-115-211-62.elisa-laajakaista.fi] has quit [Ping Timeout]
11:59 AnnoDomini [~fark.off@Nightstar-29697.neoplus.adsl.tpnet.pl] has quit [Ping Timeout]
12:03 EvilDarkLord [althalas@Nightstar-15301.a88-115-211-62.elisa-laajakaista.fi] has joined #code
12:05 AnnoDomini [~fark.off@Nightstar-29116.neoplus.adsl.tpnet.pl] has joined #Code
12:18 MyCatOwnz [~rb6822@Nightstar-18417.cs.bris.ac.uk] has joined #code
12:19 Thaqui is now known as ThaquiSleep
13:44 You're now known as TheWatcher[afk]
14:20 EvilDarkLord [althalas@Nightstar-15301.a88-115-211-62.elisa-laajakaista.fi] has quit [Ping Timeout]
14:24 You're now known as TheWatcher[wr0k]
14:31 EvilDarkLord [althalas@Nightstar-15301.a88-115-211-62.elisa-laajakaista.fi] has joined #code
15:29 You're now known as TheWatcher
15:57 MyCatOwnz [~rb6822@Nightstar-18417.cs.bris.ac.uk] has quit [Quit: Swim, swim, hungry!]
16:11 Ev3 [~-@87.72.36.ns-26407] has joined #Code
17:17 Ev3 [~-@87.72.36.ns-26407] has quit [Ping Timeout]
17:24 You're now known as TheWatcher[afk]
17:36 ReivZzz is now known as ReivWork
17:38 Vornicus [~vorn@Nightstar-18307.slkc.qwest.net] has joined #code
17:38 mode/#code [+o Vornicus] by ChanServ
18:42 You're now known as TheWatcher
20:03 Chalcedon [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has joined #code
20:03 mode/#code [+o Chalcedon] by ChanServ
20:43 ThaquiSleep [~Thaqui@Nightstar-18234.jetstream.xtra.co.nz] has quit [Ping Timeout]
20:59 ThaquiSleep [~Thaqui@Nightstar-12455.jetstream.xtra.co.nz] has joined #code
21:14 AnnoDomini is now known as Nalther
21:21 EvilDarkLord is now known as Thorak
21:36 ThaquiSleep is now known as Thaqui
22:18 You're now known as TheWatcher[T-2
22:18 You're now known as TheWatcher[T-2]
22:21 You're now known as TheWatcher[zZzZ]
22:41 Chalcedon is now known as ChalcyOut
22:50 Chalcy [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has joined #code
22:50 mode/#code [+o Chalcy] by ChanServ
22:51 ChalcyOut [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has quit [Ping Timeout]
23:13 Janus [~Cerulean@Nightstar-10302.columbus.res.rr.com] has joined #Code
23:26 Nalther is now known as AnnoDomini
23:26 Thorak is now known as EvilDarkLord
23:49
<@Vornicus>
...hey, look, Raymond Chen wrote a book.
--- Log closed Fri Dec 08 00:00:02 2006
code logs -> 2006 -> Thu, 07 Dec 2006< code.20061206.log - code.20061208.log >
 search of the:   for: