05:49:30 -!- lament has quit ("leaving"). 07:10:05 -!- calamari_ has joined. 07:10:15 hi 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:16 ^_^ 21:54:26 -!- maihem has joined. 21:54:30 :D 21:54:30 -!- sleon|tuX has joined. 21:54:32 OOM? 21:54:39 Out of memory 21:54:50 wel 21:54:51 -!- Lars_G has joined. 21:54:52 *well 21:55:03 nice 21:55:10 ANd now everyone goes quiet, long live Murphy 21:55:15 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 ofcaurse :P 21:55:31 cause noone want to discuss this anyway, it's just a way to pass time in #c :P 21:55:35 when you analyze programs written in C you don't do that either 21:55:48 lament, actually a program for a turing machine *can't* handle oom. It must simply stop until more tape can be found 21:56:07 maihem: why? 21:56:11 lament, when writing in C, I try to ask if memory is available 21:56:26 So it's basically an interrupt with a handler that takes a long time 21:56:30 well, it won't help you because the program might die at any time 21:56:40 any time you need more stack for example 21:56:41 * phb is so out of the loop on turing machines :( 21:56:43 a turing machine does not have a function. "is there more tape or should I fail" 21:56:57 neither does c, if you consider the stack 21:57:15 -!- woggle has joined. 21:57:26 but a good turing machine should have detectors on the tape roll not to burn the driver motors uselessly 21:57:33 ugh 21:57:40 we're not talking about physical turing machines 21:57:56 Ok then there are no detectors. :) 21:58:05 what driver motors? Turing machine is a programming language, for all intents and purposes 21:58:18 well, turing machines are programs in a certain language, anyway 21:58:33 anyway 21:58:34 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 either overwritting the last position or something else 21:58:46 nothing stops you from writing an implementation of a turing machine with unlimited memory 21:59:00 lament, C guarantees 32 KB of auto storage, I wonder what it guarantees on nested function calls. 21:59:02 if anything 21:59:04 lament: is it possible? 21:59:14 you just transfer the problem of getting more memory into the lower abstraction level 21:59:43 (lower than your interpreter) 21:59:53 for example 22:00:07 you can write an interpreter for turing machines as a turing machine 22:00:10 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 by definition, it won't ever have memory problems 22:00:25 Lars_G: correct. 22:00:46 So the machine itself is oblivious to any form of OOM, possible or not 22:00:56 by definition, it also wont ever exist :/ 22:01:00 and thus has no way to react to such an ocurrence, the reaction is undefined 22:01:02 maihem: incorrect 22:01:19 maihem: turing machines aren't the only programming language which doesn't care about memory constraints 22:01:27 maihem: many others don't, either 22:01:37 and implementations for them exist. 22:01:45 so if you have such an implementation 22:01:49 and you run out of memory 22:02:01 I know, they suffer the same problem, or they terminate prematurely 22:02:02 that it's a problem of the underlying implementation, not a problem of your turing machine 22:02:07 s/that/then 22:02:31 (underlying implementation - implementation of language in which your implementation of the TM is written) 22:02:39 therefore, your implementation of TM is still valid 22:02:43 even though it breaks :) 22:03:02 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 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 Getting more memory will be the user's problem. 22:03:57 heh 22:04:24 that's what many programs (not TM ones) do anyway 22:04:53 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 no, that's irrelevant for the implementation 22:05:15 it's only relevant for an actual running program 22:05:36 implementations are allowed to delegate their problems to something else 22:05:44 for example, C delegates memory problems to the OS 22:05:55 lament: there is also restricted tm 22:06:03 lament: the have a limited band 22:06:19 Hmmm afaik memory problems ARE the OS's competence 22:06:31 i don't see how C delegating memory problems to the OS is different from TM delegating them to the OS. 22:06:36 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:06:59 hm 22:07:05 maihem: akkerman? 22:07:11 provably you say.... 22:07:25 lament: fibunatchi number 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 22:07:44 sorry for my english 22:07:52 * Lars_G enters a crissis and slaps sleon|tuX around with a picture of Bill Gates 22:07:52 sleon|tuX: what? 22:08:09 Do not mention Fibonacci on my presence, it has left scars from college 22:08:14 maihem: hm! 22:08:30 Lars_G: oh no! 22:08:35 maihem: nah, wrong 22:09:03 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 yes, but my implementation is just software, not software + user. 22:09:42 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 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:18 what? 22:11:20 um 22:11:27 that's _not_ a problem of the implementation 22:11:41 but does the destruction of the computer consitute completion? or is it bottom? 22:11:42 your usage of the word "implementation" is simply incorrect 22:12:14 I consider implementation to be equivalent to reification. Do you think that is incorrect? 22:12:18 yes. 22:12:47 would do you see as the difference? 22:12:49 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 the existence of a computer to run that program is completely irrelevant. 22:13:54 So was I really talking about a reification of an implementation? 22:14:10 reification. 22:14:28 and yes, reification of turing machines is impossible as long as the universe is finite. 22:15:06 which really sucks :( 22:15:08 IMHO a turing machine is concrete. hence the name "machine" rather than "function" 22:16:12 it's called a machine becasue modern CS terminology didn't exist back when Turing invented it. 22:16:37 nowadays they'd be called "Turing programs" 22:17:50 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:00 IIRC 22:18:14 I haven't read my ntes in a while :) 22:18:20 s/ntes/notes/ 22:18:32 maihem: turing machines aren't functions 22:19:04 If they have infinite tapes they are. IMHO. 22:19:09 what!? 22:19:18 if something has an infinite tape, it's a function? 22:19:57 A turing machine has an infinite tape. a turing machine is a function that can be applied to a program 22:20:22 to "a program"? 22:20:39 Huh... 22:21:13 maihem: turing machines are'nt applied to any programs. Turing machines _are_ programs 22:21:25 the program is the argument to which the turing machine function is applied, lambda p.(turingMachine p) program 22:22:09 apply a turing machine to a program and you get an answer (or non-completion if the program is written thusly) 22:22:50 what? 22:22:54 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 i'm afraid you don't understand the terminology 22:23:25 if turing machines are "applied" to anything, then only to tapes 22:23:27 you mean my lambda application above? 22:23:50 yes, the tape is the program 22:24:00 no, the tape is not the program. 22:24:04 the tape is data. 22:24:23 the "program" is the brain of the TM itself. 22:24:28 data which is a program. the turing machine takes that data (program) and computes the result. 22:25:18 Do you call the input of your C programs "program"? 22:26:16 yes. If I were analysing the correctness of my reification of a formal specification 22:26:23 anyway! turing machines do take input and produce output (unless they fail to terminate) 22:26:34 as do functions 22:26:45 as do all programs 22:27:03 i don't see this as a sufficiently strong argument to be calling turing machines "functions" 22:27:04 yes, but an implementation of a turing machine is an implementation of a different function to the true turing machine 22:27:22 so I believe you cannot have a turing machine 22:27:53 you're confusing implementation with reification again. 22:28:07 that you _can_ have an implementation of a turing machine was proved by none other than Mr. Turing himself. 22:28:20 the famous Universal Turing Machine, in fact. 22:29:13 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 That's why the AI question is still out 22:29:53 ahem 22:30:03 http://mathworld.wolfram.com/UniversalTuringMachine.html 22:30:42 -!- phb-wifi has changed nick to ph|Zzzz. 22:30:42 you're confusing universal turing machine with the church-turing hypothesis 22:30:49 the latter wasn't proven. 22:30:56 mostly because it was disproven. 22:31:04 but we're not talking about that. 22:32:30 Ah, I see. 22:32:50 I'm thinking that one must have infinite tape to be a turing machine 22:32:55 Is that wrong? 22:32:58 no. 22:33:31 by definition, turing machines have infinite tape. 22:33:59 -!- sleon|tuX has quit ("Leaving"). 22:34:08 if they didn't, there would be some things they couldn't compute 22:35:49 so.. where am I going wrong? 22:36:03 in confusing implementation with reification 22:36:22 and in thinking that "machine" implies a real machine with a real tape, apparently. 22:36:38 http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=machine&action=Search 22:38:18 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:39 no 22:38:46 sorry, a subset of the domain of that function 22:38:48 no 22:39:32 so an implementation of a turing machine could actually just always print "Hello, World"? 22:39:38 an implementation is a program, that provably implements the language. 22:39:59 I think that is circular 22:40:03 no. 22:40:11 the key word here is _program_ 22:40:15 it isn't a process 22:40:31 "application" doesn't ever come into the picture 22:40:56 maybe you need another universe to be able to successfully apply your implementation. 22:41:06 that's irrelevant to the implementation. 22:41:07 I suppose a program is applied also to the time that it is executed, and to external events 22:41:37 not unless all that is in the language specification. 22:41:43 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 an implementation is *NOT A PHYSICAL OBJECT* 22:42:08 it's a _PROGRAM_ 22:42:15 programs don't have a RAM 22:42:24 programs can't be destroyed in a nuclear war 22:43:58 programs are just a bunch of symbols conforming to a given algebra 22:44:08 *bunches 22:44:11 just as turing machines are. 22:44:38 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 that makes sense. I see your point 22:45:07 -!- Lars_G has left (?). 22:45:45 the events can include the addition of RAM by the user if necessary 22:45:54 no 22:45:55 no 22:46:09 i don't know what a "computer" is 22:46:57 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 programs don't require computers. 22:47:46 programs specify the semantics of a certain virtual machine. 22:47:47 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 babbage designed one of steel 22:48:25 so... I think the term computer is generic enough 22:48:26 do you need a computer to calculate 2 + 2? 22:48:33 no, you don't need a computer, you need _arithmetics_ 22:48:56 given an arithmetics, 2 + 2 _is_ 4, you don't need to calculate it 22:48:56 yes. I compute 2 + 2 so I am a computer (if not efficient at arithmentic computations) 22:49:02 No! We need axioms! :D 22:49:33 arithmetics includes axioms :) 22:49:41 and rules for their application 22:49:46 just as programming languages do... 22:49:56 :) 22:50:16 maihem: SEE!! Taaus agrees with me! 22:50:44 He's right. That is a rather unique event. 22:51:47 thankfully, it's being recorded even as we speak 22:51:56 i will present the logs on my trial 22:51:57 heh 22:53:40 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 no, you're just confusing yourself further :) 22:54:12 I find that happens a lot :) 22:54:28 anyway, i didn't understand what you said :( 22:54:32 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:54:57 lol 22:55:05 Taaus: you were lucky you weren't dividing zero by zero - anything could have happened! 22:55:22 Too true. 22:56:15 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 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"). 23:54:54 and thus they left. 23:55:26 Verily.