this site requires javascript to view.. it's a fucking plain text message.. anyway:
14:40 D. J. Bernstein As a boring platform for the portable parts of boring crypto software, I'd like to see a free C compiler that clearly defines, and permanently commits to, carefully designed semantics for everything that's labeled "undefined" or "unspecified" or "implementation-defined" in the C "standard". This compiler will provide a comprehensible foundation for people writing C code, for people auditing C code, and for people formally verifying C code.
For comparison, gcc and clang both feel entitled to arbitrarily change the behavior of "undefined" programs. Pretty much every real-world C program is "undefined" according to the C "standard", and new compiler "optimizations" often produce new security holes in the resulting object code, as illustrated by
and many other examples. Crypto code isn't magically immune to this--- one can easily see how today's crypto code audits will be compromised by tomorrow's compiler optimizations, even if the code is slightly too complicated for today's compilers to screw up. A boring C compiler will eliminate these nasty surprises; it will prioritize predictability.
I should note that this plan, throwing away gcc and clang in favor of a boring C compiler, isn't the only possible response to these types of security holes. Here are several other responses that I've seen:
* Attack the messenger. "This code that you've written is undefined, so you're not allowed to comment on compiler behavior!" The most recent time I saw this, another language lawyer then jumped in to argue that the code in question _wasn't_ undefined---as if this side discussion had any relevance to the real issue.
* Say that the C "standard" allows gcc and clang to do whatever they want to all of these "undefined" programs. Yes, we know that it's a stupid "standard"; that isn't the question. What do we do about the resulting security problems?
* Blame the security holes on the C programmers who wrote "undefined" programs. This _might_ be reasonable if there were a plausible plan to reduce the fraction of "undefined" programs from ~100% to ~0%, but there isn't. Even if there were, how would this massive code revision be better than keeping the code and switching to a boring C compiler?
* Claim that earthquakes in the behavior of "undefined" programs will teach C programmers to stop writing such programs. "That'll show 'em!" But the reality is that this hasn't worked and won't work.
* Claim that all we need is for some particular "undefined"-catching tool to be widely used. In fact, these tools are full of false positives and false negatives; at best they catch a few limited types of "undefined" behavior, not changing the big picture.
* Claim that a boring C compiler can't possibly support the desired system _performance_. Even if this were true (which I very much doubt), why would it be more important than system _correctness_?
Overall I think that these people simply don't understand what most C programmers want. A boring C compiler will very quickly gain users---not merely for security but also for predictability in general; people will appreciate, e.g., having variables automatically initialized to 0. Of course, the compiler has to support the usual C ABI, so that programs compiled with this compiler can be linked to libraries compiled with other compilers (including other languages), and vice versa, allowing an incremental upgrade process.
I'm told that the Plan 9 compiler tries to be somewhat predictable---
---but it still leaves many things unspecified, and I'm under the impression that it has its own ABI. There's a "Fail-Safe C" compiler that sounds like it defines much more, including safe semantics for buffer overflows---
that add more useful semantics to some parts of C _without_ changing the ABI, but the same compilers will happily screw up other parts of C. There's a "Friendly C" proposal that targets other parts of C more relevant to core crypto---
---but the big picture is still tons of misguided flexibility for the compiler writer.
---Dan
Name:
Anonymous2015-12-21 20:39
Too long but here are some things I noticed: ``"standard"'' ``"undefined"'' ``"optimizations"'' (LOL he can't even write. It is actually optimisations)
I have a solution, maybe, just maybe follow what the standard says for once and stop behaving like a stupid fuck who its okay because it just work on my machine. Asshat
A actual solution would be to use an implementation that tries to show up the errors as much as possible. And by implementation I do not mean only the compiler but also the standard library and the underlying architecture as well. Instead of covering your diarrhea in the sand, try to find the cause of it.
Throw the fucking thing out, and use literally anything else. There's no magic to C that any other low-level language can't accomplish, or even subsets of higher level languages.
Name:
fuck off lexie2015-12-22 1:11
>>2 the nice colorful pictures are easy to read for you lexie
>>6 What can we do to phase out and deprecate C? Most of us still use software that depends on it.
Name:
Anonymous2015-12-22 11:13
>>6 This is what Rust people say, and before you know it they've got you brainwashed with their SJW ideology, sucking dicks, infected with HIV, and rewriting the Linux kernel in Rust.
Name:
Anonymous2015-12-22 13:17
>>1 Ah, I see, D. J. Berenstain is an Ideas Man. In fact I think he might have transcended being an Ideas Man and became an Impetus Man, a being of pure wankery.
I mean, an Ideas Man would at least do something like take John Regehr's proposal and outline some Ideas on how to further eliminate undefined behavior (for example, you can range check all pointer arithmetics using fat pointers), of course leaving the boring stuff like ironing out the details (like how do you track pointer-ness through serialization via memcpy for example) and actual implementation to lesser men.
Not mr. Berenstein though, he wouldn't stoop even to that, he merely conveyed his Strong Opinion that the Job must be Done, mentioned the previous attempts at Getting the Job Done, and rode away into the sunset, his mission of improving human condition complete.
Name:
Anonymous2015-12-22 15:27
>>11 I am smarter than dan berngstaing. I have over 4 years experience in javascript which runs in the wbrowser. My profilolio includels: )did the CSS).
I have not publish as many academica papers as him but im still smarter because the things i have produced (my personal blog) are a lot of more imporcance than this stupid dude that thinks hes hot shit after writing an email app. I can write email app too using nodejs.
Why does anyone listen to this "djb" idiot. What a lame 90s-hacker pretentious 'handle'. doesn't he know it's 2016 already? He should get on github and use his real name and a nice photo like I do. I get employment through github dude.
Bceause I'm so smart (compared to him) I made a lo of cool things like new apps. What has he made? Some weird thing that mixes binary numbers about and it s named after an italian dancing move? tell me how exactly is that going to help young african girls get involved in computers...?
I'm smarter than dan beinhtstargi because I got $4000 on a kickstarter ato makea game making gamer: a browser bades games maker tool where you can select from 3 games to make by drag an drog. This empowers people. what hdoes his shit do? some math crap.
everyone lets ignore this 'djb' guy and hope he goes away.
The three currently known posters on /prog/: me, The Sussman, and dang bangstain
Name:
Anonymous2015-12-22 16:25
14 words
Name:
Anonymous2015-12-22 16:49
>>9 Source-to-source compilation of C into the preferred target language would be great, as well as the ability to link to C binaries. The latter is already necessary because most OSes only expose a C interface.
Name:
Anonymous2015-12-22 18:02
>>12 You sound really buttdevastated. Sorry for pooperpunishing you to such an anally anguishing extent!
I think it's the first time I've seen someone tried to whiteknight a male CS researcher though, and how! Wow.
I'm smarter than dan beinhtstargi because I got $4000 on a kickstarter ato makea game making gamer: a browser bades games maker tool where you can select from 3 games to make by drag an drog. This empowers people. what hdoes his shit do? some math crap.
Scratch that, you sound drunk as fuck. On an unrelated note, reminds of a story when two male nerds (acquaintances of acquaintances) were drinking with a female nerd, and at some point started hinting about menage a trois, to which she suggested that they might go and fuck each other if they are so horny, which to her great surprise they did.
Alcohol is known to sexually liberate people, bringing to surface deeply suppressed feelings like your homosexual fantasies about DJB. So no, now I'm not surprised at all.
Claim that all we need is for some particular "undefined"-catching tool to be widely used. In fact, these tools are full of false positives and false negatives; at best they catch a few limited types of "undefined" behavior, not changing the big picture.
These tools ought to be a standard component of every C compiler. One of the biggest issues with C is that you can't generally expect the compiler to warn you about very common errors (the more popular compilers certainly try to do this, but they aren't always an option, and even gcc and clang will silently accept really horrible things even with most of the usual warnings turned on).
Of course, you can't provide useful warnings for everything - that's an unavoidable fact of the way the language is designed - but not warning by default when the compiler knows the programmer has surely screwed up and that it is generating total crap is just not acceptable today.
>>18 It's halting-problem-impossible to catch undefined behavior with static analysis. It would need to be very heavy instrumentation for run-time analysis.
Name:
Anonymous2015-12-23 1:38
>>20 To catch all undefined behavior, yes. However it's quite possible to identify a decent amount of it with little or no runtime overhead.
Name:
Anonymous2015-12-23 1:44
Why not have ANDRU analysis and attempt formal proof of the program before compiling?
It's halting-problem-impossible to catch undefined behavior with static analysis
No, it isn't.
Name:
Cudder !cXCudderUE2015-12-23 11:21
tl;dr: most compiler writers are idiots who don't even realise one of the suggestions the standard gives about UB is...
NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).
...exactly what most programmers actually want when they use C.
Name:
Anonymous2015-12-23 13:13
>>20 everyone here knows what the halting problem is. you don't need to tell us about this AMAZING cool thing you just learned yesterday in godel escher bach.
yes it's undecidable, that doesn't imply a program can't detect it in a lot of cases. It is also possible to conservatively reject programs that can't be shown to be safe. This results in only accepting a nontrivial subset of safe programs.
Again with the "a lot of cases". Fuck that and fuck you. That doesn't fix the problem of C being shit. Either you eliminate UB or you don't.
Do you people never actually understood halting problem, for all your elitism and counter-elitism? The HP-based counterexample to static analysis problem looks like "try to prove Goldbach's conjecture, if it's true then dereference a NULL pointer, otherwise just return". Well then, if you want provably safe code you go and mark that code as invalid, problem solved.
All that "but muh halting problem" bullshit is a giant ripe red lutefisk that has nothing to do with any of the real problems with constructing a safe subset of C.
Name:
Anonymous2015-12-23 19:05
What the fuck does the halting problem have to do with most UB in C? 99% of it is trivial shit that no other language standard has trouble with. Fucking INT_MAX + 1 is UB ferfucksake.
Dec 21 20:12:23 <alice> https://groups.google.com/forum/m/#!msg/boring-crypto/48qa1kWignU/o8GGp2K1DAAJ Dec 21 20:12:26 <alice> This makes me cringe. Dec 21 20:13:58 <bob> alice: without reading, why? Dec 21 20:14:05 <urine> alice: TL;DR Dec 21 20:16:19 <eve> DJB is a serial reinventer...ignore him Dec 21 20:16:33 <alice> bob: The guy wants a compiler that has predictable "undefined behavior", "implementation-defined behavior" and "unspecified behavior". Dec 21 20:16:42 <pilne> so Dec 21 20:16:43 <mallory> yeah DJB is not the brightest as coders go Dec 21 20:16:50 <bob> alice: lmao. good luck to him I suppose. Dec 21 20:16:53 <pilne> tl:dr he has no ideas what he wants Dec 21 20:16:55 <eve> alice: it's not "the guy", it's DJB...the very definition of NIH WHACKJOB! Dec 21 20:16:57 <mallory> what an idiot Dec 21 20:17:16 <eve> I'm surprisedd he hasn't implemented one Dec 21 20:17:27 <alice> How?! Dec 21 20:17:44 <eve> he's djb. He reimplements *everything* Dec 21 20:17:46 <steve> why ... don't just pick another language? Or atleast use a stricter standard like POSIX. Dec 21 20:17:49 <mallory> I'm a lot smarter than djb Dec 21 20:18:14 <alice> The request for predictable unspecified behavior is legitimate, but implementated-defined is ALREADY defined, it's the whole purpose, so is the purpose of undefined behavior which shouldn't be used in a program and serves for portability purposes only. Dec 21 20:18:42 <dan> < eve> DJB is a serial reinventer...ignore him <- this is such a transparently wrong argument that i believe a convincing argument exists that it is low-level trolling Dec 21 20:19:12 <steve> whats wrong with wanting a stricter standard? ISO C is full of undefined this and undefined that. Dec 21 20:19:20 <urine> +1 Dec 21 20:20:25 <eve> dan: he reinveted sendmail and bind (to name just the two most egregious...); he *tried* to reinvent DNS (and failed because nobody uses dnscurve). He's a talented guy there's no doubt, but he *is* a serial reinventer
Name:
Anonymous2015-12-23 19:53
I do not want to be lumped with the "don't reinvent the wheel, use robust Java solutions", but isn't consistent implementation-defined behavior a stupid idea?
Name:
Anonymous2015-12-23 19:56
>>40 it doesn't sound stupid to me. Any reason why you say that?
I think the biggest force in effect here is that lesser programmers are having their ego threatened.
I'm talking about the kind of guys who are proud of themselves for memorizing the various C standards, knowing all the exact UB talking points you can pull out to force someone to admit you know C better than them.
They're scared and biting back because they know their 'talent' is being nullified.
Name:
Anonymous2015-12-23 20:21
>>42 I see a different thing: destroying the portability of C because they don't want to write x86 assembly.
Name:
Anonymous2015-12-23 20:52
>>43 Nobody but cudder should be forced to write x86 assembly in 2015.
Name:
Anonymous2015-12-23 21:00
>>36 You don't even understand the fucking conversation.
If you standardized what your compiler/environment does with UB, you have fixed it. If you move to a language that isn't as godawful and godforsaken as C, you have fixed it.
Trying to trap & report UB is fucking stupid, and the halting problem is part of and/or proof of that idiotic response to this thread.
Name:
Anonymous2015-12-23 22:59
Simply read UB as ``Not allowed''
Name:
Anonymous2015-12-24 0:27
Hey Doc, it hurts when I slam my head into the wall.
Name:
Anonymous2015-12-24 0:43
>>43 That's perfectly reasonable. Only an autistic turbonerd like Cudder would want to memorize and mentally manage the 500 stage pipeline on x86. Close off the difficult areas and let the optimizer go to work on it.
Name:
Anonymous2015-12-24 2:51
>>12 I'm a CEO of four large companies, and a professor at Harvard and a spaceman. I just got back from my last mission to space, and am also a racecar driver so I will have to go racing soon, but maybe I'll have some time before then. If some females don't call me up to do sex with them, because I'm also a big sex-haver and do it like many times a day. I graduated excelsior cum laude from Space University 25 years ago, and apparently they didn't teach me to read directions at Space University because I did not notice that the OP wants me to reply to the maillist and not post in this thread. So that's why I'm sharing all of this with you guys. I've developed software for the first computer ever, worked at IBM as a bad ass computer inventor, designed the x86 processor, and also developed software for spaceships, and also have lots of sex with females, and hopefully you will see me as qualified to do some serious PHP development here (C is obsolete and only sex non-havers use it).
If you standardized what your compiler/environment does with UB, you have fixed it.
Trying to trap & report UB is fucking stupid, and the halting problem is part of and/or proof of that idiotic response to this thread.
Let me see if I understand. So when your compiler tells you that you're using a not definitely initialized variable, you have fixed the UB problem. But when your code analyzer tells you that you're using a not definitely initialized variable, you are being fucking stupid and halting problem proves you wrong?
I'm beginning to suspect that you fuckers have no clue what UB actually is, I mean, which cases are marked as UB in C, so you're talking out of your asses about solutions to some entirely imaginary problematic cases.
Name:
Anonymous2015-12-24 14:14
How applicable is the Halting problem on non-Turing machines anyway? Oh, you thought your shitputer was Turing complete? Well what would happen if it runs out of memory? Nah, it's just a finite state machine with lots of states. A static analyzer doesn't have to check an infinite problem space like the Halting problem falls victim to.
Oh, you thought your shitputer was Turing complete?
Obviously as soon as you add the ability to interface with unlimited external storage (via internet for example) all you need is enough states to implement an UTM.
Name:
Anonymous2015-12-24 15:57
>>52 Thw tape is infinite, so the states in a TM is irrelevant. But expand your memory to the entire universe and it's still finite. The DFSM state count will grow with O(22n) where n is the tape size of the shitputer, but it is still finite.
>>1-55 People who want to throw out everything written in C and rewrite it in Rust are as bad as people who want to use JavaScript for everything. And I like JavaScript.
You mongos don't know the difference between "unlimited" and "infinite"? Are you in the middle school or something?
Name:
Anonymous2015-12-25 14:13
>>57 Doesn't matter. So long as the memory required is finite, a FSM can parse the language. L={anbn|n is unbounded} ∉ RL. L={anbn|n<10}, for example, is a regular language. The distinction between unlimited, arbitrary, unbounded, and infinite are irrelevant.
>>56 C will never be secure. They will continue finding buffer overflows, even in libc itself, for all eternity. If you want the `internet of things` to be anything else than the internet of ubiquitous botnets, you will have to accept some temporary setbacks in functionality. Security can not be added as an afterthought.
Name:
Anonymous2015-12-28 23:38
>>64 Why don't you just shut your /dev/random-connected face hole and kill yourself, you ignorant fuck?
The halting problem has nothing to do with Turing machines or finite/infinite or bounded/unbounded memory. You're just spewing terms that you've heard from the lowest level CS morons who barely understood what they meant.
I mean this sincerely. Put a bullet through your head, take a dive under a train, jump off a bridge, anything to rid the world of yourself.
Name:
Anonymous2015-12-30 7:13
>>68 Explain then how a finite system can possibly not be checked for halts?
I think that it is you who is a retard. Are you one of the retards who insist that hello-world can never be shown to halt? I think you may be!
Abstract. The undecidability of the halting problem is a well-known research result of theoretical computer science, dating back to Turing’s work in 1936. Nevertheless, it is commonly known that the halting problem on finite-state computer systems is decidable. Thus, any undecidability proof given for the halting problem must imply that it does not apply to finite-state computer systems. The aim of this paper is to deepen the understanding of why the undecidability proofs of the halting problem cannot be instantiated as finite-state programs. To bridge the gap between theory and practice, the arguments are based on simple mathematics rather than an extensive use of abstract formalisms.
See, should be simple enough for even a simpleton like you!
Name:
Anonymous2015-12-30 11:04
>>69 Are you the "jews invented infinity" retard or did you catch it from him?
>>70 Are you the "I've got nothing to say on the topic so I'm picking on the other person with random irrelevant bullshit pretenses" retard or did you catch it from him?
Name:
Anonymous2015-12-30 18:50
>>70 Do you have anything further to say about the halting problems applicability to finite systems? Several of us are waiting on your apology.
Name:
Anonymous2015-12-31 1:07
>>69 God fucking damnit, you're such a stupid nigger cunt. This is like CS 101 shit.
Pick some mathematical property of integers, where it is unknown if there are more any integers which meet that property that is greater than the existing largest one found.
Test each integer for that property, ++i.
Will it ever halt?
Now, eat a bullet.
Name:
Anonymous2015-12-31 1:17
can everyone just stop asking about the halting problem
this is literally reddit-tier
this is shit you should be asking on r/askscience or r/eli5
not here. /prog/ was always full of people who have long undertsand BASIC FACTS about programming
Name:
Anonymous2015-12-31 1:21
If this compiler doesn't drill holes through rock, I'm not interested.
Name:
Anonymous2015-12-31 3:39
>>74 If i is bounded, if it does not enumerate over all of N, if there are only a finite values to check, then that property can be exhaustively checked in finite time, and the sytem must halt in finite time.
Simply put: THE HALTING PROBLEM DOES NOT APPLY HERE. What do you not fucking understand? The halting problem is only concerned with infinite machines. Are you going to fight this fucking hard when I tell you that regexp can parse HTML if I guarantee that the recursion depth will never exceed the pumping number of the regexp?
>>75 No, we will never stop discussing it, and we will follow you into other threads until you stop either being a retarded fucking cunt who refuses to listen, you learn how to not be so god damn obvious in your posts that you stick out from everyone else and can be instantly identified, or you go the fuck back to /g/.
>>77 do you really think you're intelligent for explaining basic facts about computing to a retard?
if that's what makes you feel good go hang around on IRC or something, your postst are not wanted here.
Name:
Anonymous2015-12-31 3:57
>>74,75,78,79-idiot You are unbearable and insufferable and you are embarrassing yourself. Please, seriously, just fuck off. This is not fucking 4chan.
>>80 umad cunt? this is /prog/, it was born on 4chan
Name:
Anonymous2015-12-31 4:41
>>77 You're still in the realm of specific per-algorithm custom tests, not a single general solution. IE, you don't know what the fuck the halting problem even is.
Name:
Anonymous2015-12-31 4:49
>>82 There is no general solution to the halting problem (at least on infinite input sets), that is true. It is not that type of problem. No one disputes this. It has been claimed in this thread that the halting problem does not apply at all to finite programs over a finite input set. You are the only one disputing this. In this thread, you have been proven wrong, and it has been shown that your claims are irrelevant. ＼＼＼ ,,..-‐''''￣｀゛""''‐..、 /｀i ,-, r-､／,..-‐''''￣｀゛""''‐､ ｀ヽ､ /｀i ﾚ' /-, く｀i ン ､ ヽ i ヽ ＜_ Lｙ´/ i ﾊ !∠ ', ヽ 〉 ノー'´ ,-､ ｲ i ﾊ､_ﾚ' ﾚ!,ｨ'´｀ﾊ､_.! i ! / / ,..--＼ ヽ､ Ｌ!_ﾊ_!rrヽ, ´ﾋ__ノﾉ L_ﾊ__!./ ,'! _＞ ,.---'ヽ. / ﾊ'ﾊ_ﾘ " / ﾊ / ,'.| ｀ー-, ｀ー- ´＼ !. / !" r'"⌒ヽ / ,./ / | 'ｰ-^'ー' ､ ｀r'´レへ､ ヽ __,ﾉ ﾚ／､ゝ--"ﾊﾉ ＼ !､. ヽ＞r‐r=ﾆﾝ/ ￣ ! !ン ､ ,.ｲ /}><{ ハ / ｀､ / Ｙ 〒 L｀､____／ ｀ｰ／ i ： !
Name:
Anonymous2015-12-31 4:50
Also, this thread needs more cuteness. It has gotten far too angry. ,.-‐‐､ ,.-‐-､ _,.i （ﾉ::）i--‐‐‐'7 （ﾉ::） r''´ ゝ､ 'ｰ'ﾉ ヽ、 ｰ'ﾉ / ￣ ￣':, ／ ヽ, ,,r'´ ' ､ ,.ｨ''" ___＿,, -‐ ─‐ ''"´￣￣￣￣￣｀゛ー‐-二ｽ、 ,<-‐''"´/ , ' , ' / ,' / /X', ! ', ':, ｀ヽ;::｀ﾞ'':、 '､:::::::::::::,' / / ,' , -ﾅ‐-､ ,' i _i_ i ! !::::::::ﾉ ｀ ﾞ ''ｰ! i ! i ﾉ_｣__ﾊ ! !'/i ｀ﾊ, i i-‐'´ ＼ | ／ l l ! l｀ｧ'´ ,´ﾊ｀ヽ! ,ﾚ'=ﾅ'､i. ,i ! ─ ○ ─ i i ﾓ, ﾊ ! !ﾉ i i ﾉi !l /i ,' ,. ／ | ＼ / i ﾘﾔ'、 ﾊ ゝ' 、 '､ｿ ,ﾚ',. ! / ,:'⌒ヽ､_,.ノ ノ ﾚ' ハ ヽ!. ', "" ,. ‐‐-､ ""i､_) ﾚ' ,'´ _｣ i ! '､ ｿ ,ﾊヽ | ,' ,:'´:::｀L l ﾄ ､.. ,.. イ i ! ', i ,':::::,ｨ´｀:､L､i 'r､ ｀゛ｰ - r''ｽ, l ! / ! ） ﾚ'´!ﾍ7:::/ ヽ,ヽ_i::ヽ､ ___,.ﾉ:::∩,ﾍi_/´ iノﾚ' ,.':::::::i ',::::::::::::::::::::::::ﾉ i /:::::×l ',::::::::::::::::::::/ ｀i /:::::×::｣_ i::::::::::::::::::,' ! _,':::::,:'´ ｀ヽ, ｀i:::::::::::/ Y'''‐-､ _｣´:::::::/ y ', ﾉ､:::::::〈 ｲ ヽ ／:::::::::::,:' _/ ! |::::::/｀ i´ / `ヽ､:::::/ / ｀゛ｰ- ､__,' ｀i:::i l｀゛ｰ- 'i /:::V ,'､ ﾉ ｀V ﾄ､ ___ ﾉ i´:::::〈 ,' `ー- ､__/ l i ,' ノ:::::::::::｀i i ,ﾒ､ ', ', ,' ,.ｨｰ'´::::::::::::::::ﾉ ! /::::i ｿ i ｢⌒i ヽ､,::::::::::::::::::(_ｽ､_/´⌒〈::::ﾉ ':, ｀V´ﾝｰ-､ `ー､_＿,.ｲ:::::::｀ー-'｀ヾ､ ,ｧ‐'´｀ヽ､ﾉ'⌒ヽ､,｀i::::::::::::i !､__::::::::::::::::::::::） ,ｲ__,__,__ｨ_ﾒ､ｧ,__,_,_,)ﾒ--‐'´
Name:
Anonymous2015-12-31 5:26
>>83 Harken back to >>51. It is not a practical, tractable problem even with finite inputs.
Given that the analysis machine has infinite memory and time to track the full-state simulation of the target program + inputs, it could go full brute force and search for repeated states of a finitely bounded target machine.
None of that matters or makes any kind of sense with statically analyzing undefined behavior.
Your problem is that you're mentally retarded (or literally like 13) and unable to understand the difference between unbounded and infinite. It's obvious when you say stupid shit like "The halting problem is only concerned with infinite machines" -- yeah, sure, and Goldbachs conjecture is only concerned with infinite natural numbers. Wait, there's no such thing as an infinite natural number, is it? The only infinite thing here is your stupidity, isn't it?
Natural numbers are all finite by construction, Turing machines have no such restriction. The tape is unbounded, giving it an infinite amount of memory, meaning it can work forever. If it only had, say, 16G tape entries, it woulf have to either halt having completed or halt after exausting all 16B entries when meaningful compuation is no longer possible. It will not run forever.
I would just like to note that proofs of halting are pretty useless because even a halting procedure may take thousands of years to complete in which case it will be practically indistinguishable from a calculation which never halts.
The job of an algorithm designer is to make an algorithm which takes provably practical time to complete, not to prove whether it halts or not. The former is a useful property, the latter is useless even if proven.
Name:
Anonymous2015-12-31 19:41
>>91 An algorithm, by definition, must provably halt. If it does not, it is a program.
[...] don't make programs that fucking write themselves. Problem solved. Same goes for other programs: don't make programs that suddenly loop forever and your shitty self-referencing program won't be a contrived edge case for which Halt(p, input) doesn't work.
Name:
Anonymous2015-12-31 20:05
>>92 Obviously. But proving that it's an algorithm is useless in practice. Only proving that it's an algorithm which takes a bounded and reasonably low amount of resources to complete that counts. Would you use a Fibonacci algo which has been proven to terminate but takes 3 years to calculate the 1000th term?
Natural numbers are all finite by construction, Turing machines have no such restriction. The tape is unbounded, giving it an infinite amount of memory, meaning it can work forever.
And each instance of a TM either stops in a finite number of steps or doesn't stop at all. Its run time is not an "infinite natural number".
Asking "does this TM stop" (when started on an empty tape, eliminating input doesn't matter) is not different from asking "Can every natural number be represented as a sum of two primes". The latter statement obviously doesn't involve any "infinite natural numbers". And the former statement is obviously so very not different from the latter than you can go and straightforwardly encode one as another.
In each case we are not talking about any "actual infinity", we are only talking about unbounded finite numbers, is some finite number not representable as a sum of two primes? Does this TM stop after some finite number of steps?
The U.S. government and Lisp community spread C because it makes computing worse.
Nobody would even look at Lisp machines if we all used an iAPX 432 or similar computer.
The Lispers couldn't even compete with what people were using before. There is no way they could have competed with the capability-based computers that were being designed in the late 1970s. They believed the only way to popularize Lisp was to kill everything that is better.
>>108 Because of virtual memory and other paging games that can be done, practically all of them. All that needs to exist is an interface to memory, as all of this is at the conceptual layer. Something niggers like you repeatedly fail to grasp and always convolute with physical systems.
Name:
Anonymous2016-07-19 1:01
>>109 Even with virtual memory, you still need somewhere to put the data. If your system has say A bits of RAM, B bits of hard drive storage, C bits of removable disk storage, D bits of processor registers, your system has only 2^(A+B+C+D) possible states. Which means it's equivalent to a finite state machine, not a Turing machine.
>>110 There's no limit to the "somewhere". You can keep adding storage devices to a computer, and more computers to that computer via network. It's not bounded.
>>112 For a non-networked machine, there's a limit to how much storage is available until you physically modify it by adding more devices. And even with networking, the space available is still bounded.
Suppose every storage device in existence is already filled to capacity. The total data stored is a bounded quantity, however there still isn't room to add anything more. So the total storage capacity is still bounded.
Name:
Anonymous2016-07-19 7:21
>>113 That's not what bounded means, and you know it. Or you don't know it, and need to kill yourself.
Name:
Anonymous2016-07-19 7:53
>>114 Okay, smart guy, what does bounded mean, and how can a quantity be finite, yet unbounded?
Actually this is an impostor from an alternate reality. The real DJB's surname has always been Berenstain.
>>115 They'd teach you that in high school, after all required prerequisites. It's pointless to waste time on you before that.
Name:
Anonymous2016-07-19 15:35
>>115 I've taken college level calculus courses and they only barely touch on the concept of infinity (mostly in the context of limits/end behavior of functions). Regardless, the data storage available in the real world is bounded, because it is possible to add up all the data storage media in the world and you'd get a specific quantity. If you're going to claim computers today have unbounded memory, at what point in history did their memory cease to be bounded? In 1945, the total memory of all computers in the world was way less than one terabyte. Are you seriously going to claim that "less than one terabyte" is an unbounded quantity?
>>115 There is no quantity involved at all, shit for brains. All quantities are finite, and "bounds" don't even make sense for a fucking scalar. The point is that there's no limit inherent in a particular unbounded equation, algorithm or interface.
All you motherfuckers don't how what the fuck you're talking about, down to basic vocabulary.
Name:
Anonymous2016-07-19 20:45
>>121 Go build yourself an unbounded Turing machine then, wise guy.
Name:
Anonymous2016-07-19 20:52
>>122 Again, you have absolutely zero fucking clue about the words you're trying to use to sound smart. But for some reason, you just absolutely LOVE to see yourself use them, as you showcase your idiocy. How about you leave /prog/ at least until you finish elementary school?
>>123 Almost as much as I LOVE to showcase myself plunging my engorged meatpole into your wrinkly little man socket.
Name:
Anonymous2016-07-19 22:03
>>121 I'm not talking about "equations, algorithms, or interfaces". It's about hardware. Most languages and algorithms are Turing complete in that they don't involve explicit bounds. But for any real machine, there exist algorithms that will cause it to run out of memory.
Name:
Anonymous2016-07-19 22:17
>>122 A true Turing machine cannot be built, it's just a mathematical model that's incompatible with the laws of physics.
>>126 The limitations of algorithms have zero to do with the limitations of the machine they might run on. The machine's limitations might infringe on what the algo is doing, but that's an additional, external constraint, not one that has anything to do with the algorithm itself.
Quit conflating software and hardware!
Name:
Anonymous2016-07-20 16:11
>>129 That's what I'm saying. Turing completeness describes a means of expressing algorithms, but no real computer has equivalent power to a Turing machine. There are algorithms that can be expressed in a Turing-complete language, and be run on a Turing machine, but cannot be run on any real computer.
Name:
Anonymous2016-07-20 20:30
>>130 Bullshit. Big fucking steaming Cudder-sustenance bullshit.
Again, name one. Where the algorithm itself cannot be run on a non-infinite RAM computer, regardless of the instance of input data or actual memory quantity.
Name:
Anonymous2016-07-20 21:05
>>131 An infinite loop that increments the input by one each iteration.
Unlike modern optimizing compilers, whose goal is to make binaries that are as small and as fast as possible at the expense of compiling programs that may be semantically incorrect, kcc instead aims at mathematically rigorous dynamic checking of program compliance with the ISO C11 Standard.
Nice meme, kike. ``Non-standard'' programs are the only reason to use C.
Name:
Anonymous2016-07-22 23:00
There is no "standard" C program beyond Hello World, and even that I'm not sure about.