05:49:30 -!- lament has quit ("leaving").
07:10:05 -!- calamari_ has joined.
07:19:48 -!- calamari_ has left (?).
07:59:59 -!- clog has quit (ended).
08:00:00 -!- clog has joined.
11:02:50 -!- dbc has quit ("you have no chance to survive make your time.").
20:53:58 -!- lament has joined.
21:54:11 -!- phb has joined.
21:54:26 -!- maihem has joined.
21:54:30 -!- sleon|tuX has joined.
21:54:51 -!- Lars_G has joined.
21:55:10 <Lars_G> ANd now everyone goes quiet, long live Murphy
21:55:15 <lament> when you consider the C language, you don't actually consider the possibility of the program dying at any time because of OOM
21:55:15 <phb> ofcaurse :P
21:55:31 <phb> cause noone want to discuss this anyway, it's just a way to pass time in #c :P
21:55:35 <lament> when you analyze programs written in C you don't do that either
21:55:48 <maihem> lament, actually a program for a turing machine *can't* handle oom. It must simply stop until more tape can be found
21:56:11 <maihem> lament, when writing in C, I try to ask if memory is available
21:56:26 <Lars_G> So it's basically an interrupt with a handler that takes a long time
21:56:30 <lament> well, it won't help you because the program might die at any time
21:56:40 <lament> any time you need more stack for example
21:56:41 * phb is so out of the loop on turing machines :(
21:56:43 <maihem> a turing machine does not have a function. "is there more tape or should I fail"
21:56:57 <lament> neither does c, if you consider the stack
21:57:15 -!- woggle has joined.
21:57:26 <Lars_G> but a good turing machine should have detectors on the tape roll not to burn the driver motors uselessly
21:57:40 <lament> we're not talking about physical turing machines
21:57:56 <Lars_G> Ok then there are no detectors. :)
21:58:05 <lament> what driver motors? Turing machine is a programming language, for all intents and purposes
21:58:18 <lament> well, turing machines are programs in a certain language, anyway
21:58:34 <Lars_G> The problem is then wethever the turing machine aknowledges the lack of tape.. in theory it should not, so it would engage in a very strange form of overflow
21:58:37 -!- phb has changed nick to phb-wifi.
21:58:45 <Lars_G> either overwritting the last position or something else
21:58:46 <lament> nothing stops you from writing an implementation of a turing machine with unlimited memory
21:59:00 <maihem> lament, C guarantees 32 KB of auto storage, I wonder what it guarantees on nested function calls.
21:59:14 <lament> you just transfer the problem of getting more memory into the lower abstraction level
21:59:43 <lament> (lower than your interpreter)
22:00:07 <lament> you can write an interpreter for turing machines as a turing machine
22:00:10 <Lars_G> as a matter of fact I am not %100 up to day with Turnign machines (saw them long ago thou I admire Alan M. Turing) but the thing doesn't even has an index to current position, does it? it just has forward, back, read, write and react on data
22:00:15 <lament> by definition, it won't ever have memory problems
22:00:46 <Lars_G> So the machine itself is oblivious to any form of OOM, possible or not
22:00:56 <maihem> by definition, it also wont ever exist :/
22:01:00 <Lars_G> and thus has no way to react to such an ocurrence, the reaction is undefined
22:01:19 <lament> maihem: turing machines aren't the only programming language which doesn't care about memory constraints
22:01:27 <lament> maihem: many others don't, either
22:01:37 <lament> and implementations for them exist.
22:01:45 <lament> so if you have such an implementation
22:01:49 <lament> and you run out of memory
22:02:01 <maihem> I know, they suffer the same problem, or they terminate prematurely
22:02:02 <lament> that it's a problem of the underlying implementation, not a problem of your turing machine
22:02:31 <lament> (underlying implementation - implementation of language in which your implementation of the TM is written)
22:02:39 <lament> therefore, your implementation of TM is still valid
22:02:43 <lament> even though it breaks :)
22:03:02 <maihem> an implementation of a turing machine that does not have enough tape will not complete a program that will complete on a real turing machine. Such an implementation is an inadequate reification
22:03:45 <lament> besides, nothing stops you from writing an implementation that _will_ stop and wait for more memory every time it runs out of it.
22:03:52 <lament> Getting more memory will be the user's problem.
22:04:24 <lament> that's what many programs (not TM ones) do anyway
22:04:53 <maihem> the question becomes a problem of, how much memory can be made from the constituents of our universe - and will it exist for long enough for the program to finish with it ;)
22:05:08 <lament> no, that's irrelevant for the implementation
22:05:15 <lament> it's only relevant for an actual running program
22:05:36 <lament> implementations are allowed to delegate their problems to something else
22:05:44 <lament> for example, C delegates memory problems to the OS
22:05:55 <sleon|tuX> lament: there is also restricted tm
22:06:19 <Lars_G> Hmmm afaik memory problems ARE the OS's competence
22:06:31 <lament> i don't see how C delegating memory problems to the OS is different from TM delegating them to the OS.
22:06:36 <maihem> if an implementation cannot run any program that will run on a turing machine. it is not a correct implementation of a turing machine. if the user provably *cannot* obtain arbitrary quantities of tape, then the implementation is inadequate. The implementation here includes the user unfortunately :/
22:07:25 <sleon|tuX> lament: fibunatchi number 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
22:07:52 * Lars_G enters a crissis and slaps sleon|tuX around with a picture of Bill Gates
22:08:09 <Lars_G> Do not mention Fibonacci on my presence, it has left scars from college
22:09:03 <maihem> if you can prove that a user cannot get the tape, then the implementation (software + user) can be proved to not run all programs written for a turing machine
22:09:20 <lament> yes, but my implementation is just software, not software + user.
22:09:42 <lament> if you can prove the user can't get enough tape, then you have to get another user. But the implementation (software) is still correct.
22:11:01 <maihem> This discussion is rapidly heading towards, if the nuke drops, the program doesn't complete when it should. I can see that on the horizon :)
22:11:27 <lament> that's _not_ a problem of the implementation
22:11:41 <maihem> but does the destruction of the computer consitute completion? or is it bottom?
22:11:42 <lament> your usage of the word "implementation" is simply incorrect
22:12:14 <maihem> I consider implementation to be equivalent to reification. Do you think that is incorrect?
22:12:47 <maihem> would do you see as the difference?
22:12:49 <lament> a program that gets source code as input and performs the actions specified by that source code is an implementation (an interpreter)
22:13:02 <lament> the existence of a computer to run that program is completely irrelevant.
22:13:54 <maihem> So was I really talking about a reification of an implementation?
22:14:28 <lament> and yes, reification of turing machines is impossible as long as the universe is finite.
22:15:08 <maihem> IMHO a turing machine is concrete. hence the name "machine" rather than "function"
22:16:12 <lament> it's called a machine becasue modern CS terminology didn't exist back when Turing invented it.
22:16:37 <lament> nowadays they'd be called "Turing programs"
22:17:50 <maihem> function is not modern CS terminology. it dates back to before Turing. I think it was Church that examined computability with the function application.
22:18:14 <maihem> I haven't read my ntes in a while :)
22:18:32 <lament> maihem: turing machines aren't functions
22:19:04 <maihem> If they have infinite tapes they are. IMHO.
22:19:18 <lament> if something has an infinite tape, it's a function?
22:19:57 <maihem> A turing machine has an infinite tape. a turing machine is a function that can be applied to a program
22:21:13 <lament> maihem: turing machines are'nt applied to any programs. Turing machines _are_ programs
22:21:25 <maihem> the program is the argument to which the turing machine function is applied, lambda p.(turingMachine p) program
22:22:09 <maihem> apply a turing machine to a program and you get an answer (or non-completion if the program is written thusly)
22:22:54 <maihem> apply an (approximate?) implementation of a turing machine to a program, and if may not complete when the turing machine would have
22:23:09 <lament> i'm afraid you don't understand the terminology
22:23:25 <lament> if turing machines are "applied" to anything, then only to tapes
22:23:27 <maihem> you mean my lambda application above?
22:23:50 <maihem> yes, the tape is the program
22:24:00 <lament> no, the tape is not the program.
22:24:23 <lament> the "program" is the brain of the TM itself.
22:24:28 <maihem> data which is a program. the turing machine takes that data (program) and computes the result.
22:25:18 <lament> Do you call the input of your C programs "program"?
22:26:16 <maihem> yes. If I were analysing the correctness of my reification of a formal specification
22:26:23 <lament> anyway! turing machines do take input and produce output (unless they fail to terminate)
22:27:03 <lament> i don't see this as a sufficiently strong argument to be calling turing machines "functions"
22:27:04 <maihem> yes, but an implementation of a turing machine is an implementation of a different function to the true turing machine
22:27:22 <maihem> so I believe you cannot have a turing machine
22:27:53 <lament> you're confusing implementation with reification again.
22:28:07 <lament> that you _can_ have an implementation of a turing machine was proved by none other than Mr. Turing himself.
22:28:20 <lament> the famous Universal Turing Machine, in fact.
22:29:13 <maihem> I don't believe it was proved at all. Hence the difficulty in proving that one can compute the result of the same processes that occur in your brain.
22:29:31 <maihem> That's why the AI question is still out
22:30:03 <lament> http://mathworld.wolfram.com/UniversalTuringMachine.html
22:30:42 -!- phb-wifi has changed nick to ph|Zzzz.
22:30:42 <lament> you're confusing universal turing machine with the church-turing hypothesis
22:30:49 <lament> the latter wasn't proven.
22:30:56 <lament> mostly because it was disproven.
22:31:04 <lament> but we're not talking about that.
22:32:50 <maihem> I'm thinking that one must have infinite tape to be a turing machine
22:33:31 <lament> by definition, turing machines have infinite tape.
22:33:59 -!- sleon|tuX has quit ("Leaving").
22:34:08 <deltab> if they didn't, there would be some things they couldn't compute
22:35:49 <maihem> so.. where am I going wrong?
22:36:03 <lament> in confusing implementation with reification
22:36:22 <lament> and in thinking that "machine" implies a real machine with a real tape, apparently.
22:36:38 <lament> http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=machine&action=Search
22:38:18 <maihem> So while a reification of a function when applied to data (ie a program) must compute the same result as that function. while an implementation only need do that when applied to a subset of that data
22:38:46 <maihem> sorry, a subset of the domain of that function
22:39:32 <maihem> so an implementation of a turing machine could actually just always print "Hello, World"?
22:39:38 <lament> an implementation is a program, that provably implements the language.
22:39:59 <maihem> I think that is circular
22:40:11 <lament> the key word here is _program_
22:40:31 <lament> "application" doesn't ever come into the picture
22:40:56 <lament> maybe you need another universe to be able to successfully apply your implementation.
22:41:06 <lament> that's irrelevant to the implementation.
22:41:07 <maihem> I suppose a program is applied also to the time that it is executed, and to external events
22:41:37 <lament> not unless all that is in the language specification.
22:41:43 <maihem> So an implementation only needs to implement a function as closely as possible under the constrains of nuclear war, etc... including only having 4 Meg RAM
22:42:04 <lament> an implementation is *NOT A PHYSICAL OBJECT*
22:42:15 <lament> programs don't have a RAM
22:42:24 <lament> programs can't be destroyed in a nuclear war
22:43:58 <lament> programs are just a bunch of symbols conforming to a given algebra
22:44:11 <lament> just as turing machines are.
22:44:38 <maihem> so an implementation is something that when a computer is applied to it, can be applied to a time and unknown event sequence to profuce a function that can be applied to a program in the lanuage that it implements and can produce the same result as that language given some appropriate time and event sequence?
22:45:00 <maihem> that makes sense. I see your point
22:45:07 -!- Lars_G has left (?).
22:45:45 <maihem> the events can include the addition of RAM by the user if necessary
22:46:09 <lament> i don't know what a "computer" is
22:46:57 <maihem> you have an implementation that is a program and not a thing, but that doesn't require a computer in order to compute the result of running that program on a program?
22:47:07 <lament> programs don't require computers.
22:47:46 <lament> programs specify the semantics of a certain virtual machine.
22:47:47 <maihem> I think pen and paper with a strict set of rules to follow a program is a computer. I don't mean to suggest it should be made of doped silicon
22:48:08 <maihem> babbage designed one of steel
22:48:25 <maihem> so... I think the term computer is generic enough
22:48:26 <lament> do you need a computer to calculate 2 + 2?
22:48:33 <lament> no, you don't need a computer, you need _arithmetics_
22:48:56 <lament> given an arithmetics, 2 + 2 _is_ 4, you don't need to calculate it
22:48:56 <maihem> yes. I compute 2 + 2 so I am a computer (if not efficient at arithmentic computations)
22:49:02 <Taaus> No! We need axioms! :D
22:49:33 <lament> arithmetics includes axioms :)
22:49:41 <lament> and rules for their application
22:49:46 <lament> just as programming languages do...
22:50:16 <lament> maihem: SEE!! Taaus agrees with me!
22:50:44 <Taaus> He's right. That is a rather unique event.
22:51:47 <lament> thankfully, it's being recorded even as we speak
22:51:56 <lament> i will present the logs on my trial
22:53:40 <maihem> do arithmetics produce physical output over time? If not then your implementation is indeed just a function, and is thus a reification of some formal specification. sorry, I'm dragging this on needlessly aren't I :)
22:54:01 <lament> no, you're just confusing yourself further :)
22:54:12 <maihem> I find that happens a lot :)
22:54:28 <lament> anyway, i didn't understand what you said :(
22:54:32 <Taaus> I've never had arithmetics interact physically with anything... Apart from the time I accidentally divided by zero, and my paper burst into flames...
22:55:05 <lament> Taaus: you were lucky you weren't dividing zero by zero - anything could have happened!
22:56:15 <maihem> I think computers should represent numbers in log_2 form. so there is noo zero. Also far fewer integers, but you can't have everything.
22:57:08 <maihem> I know, log_2 (log_2 (1))
23:02:21 * Taaus goes back to reading about the joys of fold/unfold
23:16:03 -!- clog has joined.
23:16:03 -!- clog_ has joined.
23:20:12 -!- clog has quit (Read error: 110 (Connection timed out)).
23:20:12 -!- clog_ has changed nick to clog.
23:31:39 -!- maihem has quit ("Client exiting").