| Kaz Kylheku <563-365-8930@kylheku.com>: Apr 18 10:57PM ["Followup-To:" header set to comp.lang.c.] > (4) With no function call returns from X(). > then the function call from Y() to X() is infinitely recursive unless > X() stops it. I have two remarks. Remark 1: This argument is irrefutable, because it is vacuously true. Y has no power to stop the recursion because of (3). Therefore, the only that there might be no recursion is if X stops it. Thus, whenever (3) holds, the conclusion says, effectively, "the function call is infinitely recursive, or else it is not infinitely recursive", which is vacuously true. THe only way we can disprove an argument is if we show that its conclusion is false when the premises are true. If we hold the premises true, (3) must be true since it is one of them, and in that situation, the conclusion is vacuously true. Remark 2: There is no way for the premises to be true, and for there not to be runaway recursion. Therefore the "unless X stops it" remark in the conclusion is superfluous: it refers to an impossible situation. Proof: If all the premises are true, then (3) is true. Thus only X can stop the recursion. Hypothesis: suppose X does stop the recursion. X is a function, which means it can only make a decision based on its parameters and nothing else. Whenever it is called with the same parameters, it performs the same computational steps. (2) that X is called with the same parameters by Y. Therefore if X stops the recursion, X does that on the first call from Y. Y is not called again, and so there is no second call from Y to X. But this contradicts (1), which asserts that there are two calls to X. Therefore, we must retract our hypothesis: X does not stop the recursion. That leads to a contradiction. -- TXR Programming Language: http://nongnu.org/txr Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal |
| jacobnavia <jacob@jacob.remcomp.fr>: Apr 18 08:48PM +0200 Le 18/04/2021 à 18:39, Juha Nieminen a écrit : > The funny thing is that you seem to be completely oblivious to the fact > that you are trying to recommend a fix to a flaw in the language, while > still defending the language. Obviously C strings are a flaw in the language. C is not the perfect language. C++ isn't flawless either. Python has the excellent idea that white space (tabulations) have a semantic meaning, imagine that... Rust has its "unsafe" keyword that voids any advantages the language may have, lisp has too much parenthesis for anybody's taste. Should I go on? Rants like this are completely sterile |
| Keith Thompson <Keith.S.Thompson+u@gmail.com>: Apr 18 12:46PM -0700 > you have to know better. > This is nothing new, as I wrote the entire FILE* infrastructure works > this way. Except that you *can* assign objects of type FILE (if you don't mind undefined behavior). The FILE type is opaque in the sense that the standard doesn't say what it looks like, but it has to be an object type. -- Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com Working, but not speaking, for Philips Healthcare void Void(void) { Void(); } /* The recursive call of the void */ |
| Manfred <noname@add.invalid>: Apr 18 10:53PM +0200 On 4/18/2021 9:46 PM, Keith Thompson wrote: > undefined behavior). The FILE type is opaque in the sense that the > standard doesn't say what it looks like, but it has to be an object > type. The relevant part was: > typedef struct string_t STRING; I am talking about opaque types, which are incomplete and as such you can't use objects of their type. As far as the standard is concerned FILE is an opaque type whose definition might not be seen (and in fact is _not_ intended to be seen, let alone used) by user code. I think it is clear that the fact that in some implementations the definition of FILE might percolate into user TUs is orthogonal to this discussion. $ cat opaque.c typedef struct string_t STRING; STRING* string_concat(STRING* s1, STRING* s2); void string_free(STRING* s); void foo(STRING* s1, STRING* s2) { STRING* s3 = string_concat(s1, s2); string_free(s3); } void bar(STRING* s1, STRING* s2) { *s2 = *s1; // can't do that } $ cc -std=c11 -Wall -pedantic -c opaque.c opaque.c: In function 'bar': opaque.c:17:9: error: invalid use of incomplete typedef 'STRING' {aka 'struct string_t'} 17 | *s2 = *s1; | ^ opaque.c:17:7: error: invalid use of incomplete typedef 'STRING' {aka 'struct string_t'} 17 | *s2 = *s1; | ^ |
| olcott <NoOne@NoWhere.com>: Apr 18 04:04PM -0500 On 4/17/2021 12:56 AM, Juha Nieminen wrote: > dynamic arrays of such string objects, in C++ he could just create a > std::vector<std::string> and be done with it. All the tools he needed > for that project available easily and safely. I always took the same sort of approach. If you stick with the most important subset of C++ the standard template library and the ability to define self-contained objects, then C++ can greatly reduce the complexity of programming tasks. Because of the tediousness of memory allocation errors I only used fixed length arrays in C, and I only use std::vector in C++. In several decades as a professional programmer I have never allocated memory in C or C++. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| Bonita Montero <Bonita.Montero@gmail.com>: Apr 18 11:31PM +0200 > Where does that misconception come from? That isn't a misconception. |
| jacobnavia <jacob@jacob.remcomp.fr>: Apr 18 08:44PM +0200 See the tiobe index: https://www.tiobe.com/tiobe-index/ This is to calm down people like Mr Nieminen. |
| Manfred <noname@add.invalid>: Apr 18 10:59PM +0200 On 4/18/2021 8:44 PM, jacobnavia wrote: > See the tiobe index: > https://www.tiobe.com/tiobe-index/ > This is to calm down people like Mr Nieminen. Java is this close to falling behind Python. I'm not surprised. Wild performance of assembly, it appears! |
| wij <wyniijj@gmail.com>: Apr 18 11:41AM -0700 On Monday, 19 April 2021 at 02:24:22 UTC+8, olcott wrote: > Copyright 2021 Pete Olcott > "Great spirits have always encountered violent opposition from mediocre > minds." Einstein Then, you restrict Y() to the type of function that X() can detect. |
| olcott <NoOne@NoWhere.com>: Apr 18 01:54PM -0500 On 4/18/2021 1:41 PM, wij wrote: >> "Great spirits have always encountered violent opposition from mediocre >> minds." Einstein > Then, you restrict Y() to the type of function that X() can detect. Basically the above criteria allows a C function X() that simulates the x86 machine language of function Y() to correctly decide that Y() is calling X() in infinite recursion. It turns out that this same scenario is what has been used to "prove" that the halting problem cannot be solved. If X is the Linz H and Y is a slightly simplified version of the Linz H^, then H does correctly decides not halting on H^ void H^(u32 P) { u32 Input_Would_Halt = Halts(P, P); if (Input_Would_Halt) HERE: goto HERE; } int main() { u32 Input_Would_Halt = H((u32)H^, (u32)H^); Output("Input_Would_Halt = ", Input_Would_Halt); } http://www.liarparadox.org/Peter_Linz_HP(Pages_318-319).pdf -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| wij <wyniijj@gmail.com>: Apr 18 12:44PM -0700 On Monday, 19 April 2021 at 02:54:46 UTC+8, olcott wrote: > calling X() in infinite recursion. > It turns out that this same scenario is what has been used to "prove" > that the halting problem cannot be solved. Y() can be written in various way to simulate X() that X() has no way to predict. Or X() can predict the future. E.g. Y() can split the algorithm of X() into several parts and simulate it. How can X() know about this. |
| olcott <NoOne@NoWhere.com>: Apr 18 02:53PM -0500 On 4/18/2021 2:44 PM, wij wrote: >> that the halting problem cannot be solved. > Y() can be written in various way to simulate X() that X() has no way to > predict. Or X() can predict the future. You have that backwards, here it is in more detail: #define u32 uint32_t void X(u32 P, u32 I) { Simulate(P, I); } void Y(u32 P) { X(P, P); } int main() { Y((u32)Y); } X() has an x86 emulator and the compiled C of Y() is x86. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| wij <wyniijj@gmail.com>: Apr 18 01:05PM -0700 On Monday, 19 April 2021 at 03:53:37 UTC+8, olcott wrote: > Copyright 2021 Pete Olcott > "Great spirits have always encountered violent opposition from mediocre > minds." Einstein I hope you can also solve the mentioned example: E.g. Y() can split the algorithm of X() into several parts and simulate it. How can X() know about this. |
| olcott <NoOne@NoWhere.com>: Apr 18 03:07PM -0500 On 4/18/2021 3:05 PM, wij wrote: > I hope you can also solve the mentioned example: > E.g. Y() can split the algorithm of X() into several parts and simulate it. > How can X() know about this. Y() is not at all any sort of simulator, you have this part backwards. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| wij <wyniijj@gmail.com>: Apr 18 01:16PM -0700 On Monday, 19 April 2021 at 04:07:30 UTC+8, olcott wrote: > Copyright 2021 Pete Olcott > "Great spirits have always encountered violent opposition from mediocre > minds." Einstein Therefore X() can only solve 'known instances', right? |
| olcott <NoOne@NoWhere.com>: Apr 18 03:37PM -0500 On 4/18/2021 3:16 PM, wij wrote: >> "Great spirits have always encountered violent opposition from mediocre >> minds." Einstein > Therefore X() can only solve 'known instances', right? X() can detect a when it is called in infinite recursion by Y() which is an x86 function generated by a C compiler. This is sufficient to refute the conventional halting problem undecidability proofs. void Y(u32 P) { int Input_Would_Halt = X(P, P); if (Input_Would_Halt) HERE: goto HERE; } int main() { X((u32)Y, (u32)Y); } -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment