Your point that reference counting can result in memory leaks is absolutely correct and a worthwhile point. However, it's also worth pointing out that tracing garbage collectors like those used by Java are also allowed to leak memory and never free it. In the most extreme scenario you have the epsilon garbage collector, which leaks everything:
Implementing a garbage collector that is guaranteed to free memory when it's actually no longer needed is equivalent to solving the halting problem (via Rice's theorem), and so any garbage collection algorithm is going to have to leak some memory, it's simply unavoidable.
I feel like in a subtle way you're mixing up data races with race conditions, especially given the example you site about incrementing an atomic variable.
TSAN does not check for race conditions in general, and doesn't claim to do so at all as the documentation doesn't include the term race condition anywhere. TSAN is strictly for checking data races and deadlocks.
Consequently this claim is false:
>The issue is that even if it statically proved the absence of data races in the C++ sense, that still wouldn't imply that your algorithm is race-free.
Race-free code means absence of data races, it does not mean absence of the more general race condition. If you search Google Scholar for race free programming you'll find no one uses the term race-free to refer to complete absence of race conditions but rather to the absence of data races.
There's "data race" in "C++ ISO standard" sense, and then there's "data race" in the general CS literature (as well as all the other terms). Two threads writing a value to the same memory location (even atomically) is usually a data race in the CS/algorithm sense (due to the lack of synchronization), but not the C++ sense. I'm not really interested in pedantic terminology here, just trying get a higher level point across about what you can & can't assume with a clean TSAN (and how not to clean your TSAN errors). Feel free to mentally rewrite my comment with whatever preferred terminology you feel would get my points across.
This isn't pedantry, if you're going to talk about how specific tools work then you need to use the actual terminology that the tools themselves use or else you will confuse yourself and anyone you talk to about them. If we were discussing general concepts about thread safety then sure we can be loose about our words, but if we're talking about a specific tool used for a specific programming language then we should make sure we are using the correct terminology, if only to signal that we have the proper domain knowledge to speak about the subject.
>Feel free to mentally rewrite my comment with whatever preferred terminology you feel would get my points across.
If I rewrite your comment to use data race, then your comment is plainly incorrect since the supporting example you give is not a data race but a race condition.
If I rewrite your comment to use race condition, then your comment is also incorrect since TSAN doesn't detect race conditions in general and doesn't claim to, it detects data races.
So what exactly am I supposed to do in order to make sense of your post?
The idea that you'd talk about the pros and cons of a tool like TSAN without knowing the difference between a race condition and a data race is kind of absurd. That you'd claim my clarification of these terms for the sake of better understanding your point is a form of pedantry is sheer hubris.
Hold on, before attacking me. Say we have this Java program, and assume the semantics of the common JRE/JVM everyone uses. Do you believe it has a data race or not? Because the variable is accessed atomically, whether whether you mark it as volatile or not:
class Main {
private static String s = "uninitialized";
public static void main(String[] args) {
Thread t = new Thread() {
public void run() { s = args[0]; }
};
t.start();
System.out.println(s);
}
}
And I sure as heck have not heard anyone claim such data races are impossible in Java. (Have you?)
>When a program contains two conflicting accesses (§17.4.1) that are not ordered by a happens-before relationship, it is said to contain a data race.
Yes, your program contains a data race, by the definition used in the JLS. The set of outcomes you may observe from a data race are specified. I'm not sure if this choice was intentional or not, but there is a guarantee that you will either print the argument or "uninitialized" and no other behavior, because String relies on final field semantics. This is would not be true in c/c++ where the equivalent code is undefined behavior and you could see any result.
In Java you can have a data race and use it productively for certain niche cases, like String.hashcode - I've also contributed some to the Guava concurrency library. This is not true in c/c++ where data races (by their definition) are undefined behavior. If you want to do the tricks you can in racy Java without UB, you have to declare your variables atomic and use relaxed memory order and possibly fences.
What you wrote is indeed a data race, it'll race s, but you mention the semantics of the JRE and I wonder if you actually know what those are because that's crucial here.
You see Java has a specific memory ordering model (many languages just give you a big shrug, including C before it adopted the C++ 11 model but Java spells out what happens) and that model is very sophisticated so it has an answer to what happens here.
Because we raced s, we lose Sequential Consistency. This means in general (this example is so trivial it won't matter) humans struggle to understand what's going on in their program, which makes debugging and other software engineering impractical. But, unlike C++ loss of Sequential Consistency isn't fatal in Java, instead we're promised that when s is observed in the main thread it will either be that initial "uninitialized" string or it will have the args[0] value, ie the name of the program because these are the only two values it could have and Java does not specify which of them observed in this case.
You could think of this as "atomic access" and that's likely the actual implementation in this case, but the Java specification only promises what I wrote.
In C++ this is game over, the language standard specifically says it is Undefined Behaviour to have any data race and so the behaviour of your program is outside the standard - anything at all might happen.
[Edited: I neglected originally to observe that s is set to "uninitialized", and instead I assumed it begins as null]
> But, unlike C++ loss of Sequential Consistency isn't fatal in Java
I have no idea what you mean here. Loss of sequential consistency is in no way fatal in C++. There are several access modes that are specifically designed to avoid sequential consistency.
Regarding the rest of your comment:
You're making exactly my point though. These are guaranteed atomic accesses -- and like you said, we are guaranteed to see either the old or new value, and nothing else -- and yet they are still data races. Anyone who agrees this is a data race despite the atomicity must necessarily understand that atomics don't imply lack of data races -- not in general CS terminology.
The only way it's correct to say they are mutually exclusive is when you define "data race" as they did in the C++ standard, to imply a non-atomic access. Which you're welcome to do, but it's an incredibly pedantic thing to do because, for probably >95% of the users of C++ (and probably even of TSAN itself), when they read "data race", they assume it to mean the concept they understand from CS. They don't know that the ISO standard defines it in its own peculiar way. My point here was to convey something to normal people rather than C++ committee language lawyers, hence the use of the general term.
> Loss of sequential consistency is in no way fatal in C++. There are several access modes that are specifically designed to avoid sequential consistency.
Sure, if you work really hard you can write a C++ program which doesn't meet the 6.9.2.2 intro.races definition of a data race but does nevertheless lose sequential consistency and so it has in some sense well-defined meaning in C++ but humans can't usefully reason about it. You'll almost certainly trip and write UB when attempting this, but assuming you're inhumanly careful or the program is otherwise very simple so that you don't do that it's an exception.
My guess is that your program will be miscompiled by all extant C++ compilers and you'll be unhappy with the results, and further that if you can get committee focus on this at all they will prioritize making your program Undefined in C++ rather than "fixing" compilers.
Just don't do this. The reason for the exclusions in 6.9.2.2 is that what we want people to do is write correct SC code but using primitives which themselves can't guarantee that, so the person writing the code must do so correctly. The reason is not that somehow C++ programmers are magicians and the loss of SC won't negatively impact the correctness of code they attempt to write, quite the contrary.
>The only way it's correct to say they are mutually exclusive is when you define "data race" as they did in the C++ standard, to imply a non-atomic access.
A data-race does not imply a non-atomic operation, it implies an unsynchronized operation. Different languages have different requirements for what constitutes a synchronized operation, for example in Python all reads and writes are synchronized, in Java synchronization is generally accomplished through the use of a monitor or a volatile operation, and in C++ synchronization is generally accomplished through the use of std::atomic operations.
The fact that in C++ atomic operations result in synchronization, while in Java atomic operations are not sufficient for synchronization is not some kind of language lawyering or pedantry, it's because Java makes stronger guarantees about the consequences of a data race versus C++ where a data race can result in any arbitrary behavior whatsoever. As such it should not come as a surprise that the cost of those stronger guarantees is that Java has stronger requirements for data race free programs.
But of course this is mostly a deflection, since the discussion was about the use of TSAN, which is a data race detector for C and C++, not for Java. Hence to the extent that TSAN detects data races, it detects them with respect to C and C++'s memory model, not Java's memory model or Python's memory model, or any other memory model.
The objection I originally laid out was your example of a race condition, an example which can happen even in the absence of parallelism (ie. a single-core CPU) and even in the absence of multithreaded code altogether (your example can happen in a single threaded application with the use of coroutines). TSAN makes no claim with regards to detecting race conditions in general, it only seeks to detect data races and data races as they pertain the C and C++ memory models.
I am not "deflecting" anything, I am going to the heart of the matter.
Let me lay this out very explicitly. This comment will likely be my final one on the matter as this back-and-forth is getting quite tiresome, and I'm not enjoying it, especially with the swipes directed at me.
For the sake of this discussion, assume the command-line arguments behave the same in both languages. (i.e. ignore the C++ argv[0] vs. Java args[0] distinction and whatnot.)
Somehow, you simultaneously believe (a) that Java program contains data races, while believing (b) the C++ program does not.
This is a self-contradictory position. The programs are well-defined, direct translations of each other. They are equivalent in everything but syntax. If one contains a data race, so must the other. If one does not, then neither can the other.
This implies that TSAN does not detect "data races" as it is usually understood in the CS field -- it does not detect anything in the C++ program. What TSAN detects is only a particular, distinct situation that the C++ standard also happens to call a "data race". So if you're talking to a C++ language lawyer, you can say TSAN detects all data races within its window/buffer limits. But if you're talking to someone who doesn't sleep with the C++ standard under their pillow, they're not going to realize C++ is using a language-specific definition, and they're going to assume it flags programs like the equivalent of the Java program above, which has a data race but whose equivalent TSAN would absolutely not flag.
Yes, C++ and Java have different conditions for what a data race is.
That your position hinges on thinking all languages share the same memory model suggests a much deeper failure to understand some of the basic principles of writing correct parallel software and while numerous people have tried to correct you on this, you still seem adament on doubling down on your position so I don't think there is much point in continuing this.
> That your position hinges on thinking all languages share the same memory model suggests a much deeper failure to understand some of the basic principles of writing correct parallel software and while numerous people have tried to correct you on this, you still seem adament on doubling down on your position so I don't think there is much point in continuing this.
I never suggested "all languages share the same memory model". You're severely mischaracterizing what I've said and putting words in my mouth.
What I said was (a) data races are generals properties of programs that people can and do discuss in language-agnostic contexts, and (b) it makes no sense to say two well-defined, equivalent programs differ in whether they have data races. Reducing these statements down to "all programs share the same memory model" as if they're somehow equivalent makes for an incredibly unfaithful caricature of everything I've said. Yes, I can see there's no point in continuing.
> data races are generals properties of programs that people can and do discuss in language-agnostic contexts
"Data race" is a specific property defined by a memory model, which is normally part of a language spec; it's not usually understood as an abstract property defined in terms of outcome, at least not usefully. If you talk about data races as abstract and language-spec-agnostic properties, then yes, you're assuming a memory model that's shared across all programs and their languages.
> "Data race" is a specific property defined by a memory model, which is normally part of a language spec; it's not usually understood as an abstract property defined in terms of outcome, at least not usefully.
Really? To me [1] sure doesn't look useless:
> We use the standard definition of a data race: two memory accesses to the same address can be scheduled on different threads to happen concurrently, and at least one of the accesses is a write [16].
You're welcome to look at the [16] it cites, and observe that it is from 1991, entirely in pseudocode, with no mention of a "memory model". It so happens to use the phrase "access anomaly", but evidently that is used synonymously here, per [1].
> If you talk about data races as abstract and language-spec-agnostic properties, then yes, you're assuming a memory model that's shared across all programs and their languages.
No, nobody is assuming such a thing. Different memory models can still exhibit similar properties when analyzing file accesses. Just like how different network models can exhibit similar properties (like queue size bounds, latency, etc.) when discussing network communication. Just because two things are different that doesn't mean they can't exhibit common features you can talk about in a generic fashion.
Java defines what is or isn't a "data race" in one way, as part of its spec. C++ defines that same term "data race" in another way, as part of its spec. Your linked papers use a definition of "data race" which they define themselves based on a claimed 'standard definition' which is different than both the Java and C++ definitions of the same term. The point here is that the definition of "data race" is not universal or objective. When you want to evaluate whether or not some bit of code exhibits a "data race" then without qualifying what you mean when you say "data race" that property is gonna be evaluated in the context of the language, not some higher-level abstract assumption. You can talk about whatever set of common properties of a "data race" that are invariant to language or whatever and that you want to talk about, that's fine, but you need to make that expectation explicit if you want to have a productive conversation with anyone else, because "data race" by itself is context-dependent.
> This implies that TSAN does not detect "data races" as it is usually understood in the CS field -- it does not detect anything in the C++ program. What TSAN detects is only a particular, distinct situation that the C++ standard also happens to call a "data race"
TSAN defines its own specific definition of "data race" which is invariant to the languages that it evaluates. In particular the C++ definition of "data race" is more lenient than the TSAN definition of "data race"; C++ doesn't consider two atomic accesses of the same memory (at least one being a write) under memory_order_relaxed to be a data race, but TSAN does.
TSAN _could_ detect the C++ program as having a data race, for sure. And if it could evaluate Java programs, it _could_ also detect the Java program as having a data race, too.
> C++ doesn't consider two atomic accesses of the same memory (at least one being a write) under memory_order_relaxed to be a data race, but TSAN does.
I'm confused what you're saying here. If you take the program I linked, which uses relaxed ordering, and add -fsanitize=thread, TSAN doesn't flag anything. That seems inconsistent with what you're saying?
P.S. note that even using memory_order_seq_cst wouldn't change anything in that particular program.
First of all, TSAN can identify the presence of a data race, but it can't prove the absence of any data races. If -fsanitize=thread doesn't flag anything, that's insufficient evidence to say that there aren't any data races in the code, at least as TSAN defines data race, which is stricter than how C++ defines data race.
You've now received many comments from many different commenters that all kind of say the same thing, which is basically that your understanding of a "data race" is not really accurate. Those comments have included pretty detailed information as to exactly how and when and why your definition isn't totally correct. If I were you I'd take the L and maybe read up a bit.
> First of all, TSAN can identify the presence of a data race, but it can't prove the absence of any data races. If -fsanitize=thread doesn't flag anything, that's insufficient evidence to say that there aren't any data races in the code
I stated as much in my own first comment, with more details on when/why this does/doesn't occur.
> at least as TSAN defines data race, which is stricter than how C++ defines data race. [...] If I were you I'd take the L and maybe read up a bit.
Before assuming I haven't: I have. And the reading does not agree [1] [2] with your idea that TSAN sometimes considers relaxed atomic writes to be data races. Hence my replies. Remember, you wrote:
>> C++ doesn't consider two atomic accesses of the same memory (at least one being a write) under memory_order_relaxed to be a data race, but TSAN does.
I have not seen a single word anywhere -- not in the docs, not in example code, and (I think) not even from anyone here other than you -- suggesting that TSAN considers memory_order_relaxed writes to constitute a data race. It certainly does not flag them in the most trivial test I could think of, which I had already linked here [3].
If this is just my ignorance or misunderstanding, then instead of telling me to go do my own reading, please enlighten me and provide one link or example that demonstrates that TSAN considers atomic writes to the same memory to be a data race? I would be very glad to learn this, as I wasn't aware of this before, and am not seeing anything suggesting such.
> Those comments have included pretty detailed information as to exactly how and when and why your definition isn't totally correct.
I have linked to papers going back decades showing that "data race" has a general definition that don't entirely match up with what people have said. I myself have also explained in great detail how the general definition differs from the C++ one. I don't know what else to possibly provide here, but I'm done.
I haven't participated in this thread yet, but I would like to drill down on your TSan example. It seems to me that the window of timing for TSan to catch it is _super_ tight, as the overhead of creating a thread is very large relative to the other operations.
For something like TSan, which allows programs to execute normally with additional instrumentation, this timing matters, and so it's not a great example. An equivalent program being simulated in something like Loom would be much more convincing.
I'm a little confused, as you agree with your parent commenter that TSan not raising a flag is not conclusive. But you also appear to be using TSan not flagging the program as some kind of evidence in the same comment.
Thanks for following along and trying to clarify this, I really appreciate it.
The answer to your questions is that timing is not the issue in my example. You can notice this easily if you strip std::atomic<> from the type. TSAN can and does catch it just fine. The atomicity itself is what tells TSAN to not consider this a data race.
What probably threw you off was that I (sloppily) used "timing" as a way to say "proximity in the history buffer". [1] It's not wall clock time that matters, it's the number of memory accesses that fit in TSAN's history buffer. (This should also explain your confusion w.r.t. "tight" timing.)
Hence, the conclusivity depends entirely on the reason it wasn't flagged. (This is why I explained the failure modes quite precisely in my very first comment: not all of them have randomness involved.) If it wasn't flagged because the history buffer wasn't large enough, then obviously it's not conclusive. But if it wasn't flagged because TSAN noticed it and deliberately exempted it, then obviously it doesn't consider it a data race.
> The answer to your questions is that timing is not the issue in my example. You can notice this easily if you strip std::atomic<> from the type. TSAN can and does catch it just fine.
If you strip the std::atomic from your example, then you obviously lose read/write atomicity on the value, which should be trivial for something like TSAN to detect and flag.
> The atomicity itself is what tells TSAN to not consider this a data race ... the conclusivity depends entirely on the reason it wasn't flagged. (This is why I explained the failure modes quite precisely in my very first comment: not all of them have randomness involved.)
"The conclusivity" can only ever be "inconclusive" or "has a data race", it can never be "does not have a data race", because that's just not how TSAN (or any similar tools) work. See [1]. In your original C++ program there is no happens-before relationship between the thread you spawn and the main thread, so there is a data race by the TSAN definition, even though the read and the write are atomic, and even if a given execution of that code by TSAN doesn't yield an error. It's not about timing, at least not exactly -- it's about the guarantees of the scheduler and its execution of threads, which is non-deterministic without explicit synchronization in the application (or something along those lines)..!
You've linked to papers that define "data race" in a specific way. That doesn't mean that when anyone says "data race" in any other context they are using any of those papers' definitions, for reasons that have been exhaustively explained.
Actually I don't think your c++ program contains a data race, because the writes that populated the argument string happened before the atomic read. If you copied the string on the other thread before writing the pointer or you used a non atomic variable, I bet tsan would catch it.
> Actually I don't think your c++ program contains a data race, because the writes that populated the argument string happened before the atomic read
But the write to the static variable from the second thread is entirely unordered with respect to the read, despite the atomicity. If lack of ordering is your criterion for data races, doesn't that imply there is a data race between that write and that read?
No, because it's atomic. If that was a data race, and data races are UB, there would be no point in having relaxed atomics.
It's not my criterion, it's defined in the language standard. You can't have a data race on an atomic except for std::atomic_init. The reads on the string contents themselves are ordered because the args string is initialized before the thread is launched and the other one is static. If the launched thread allocated a new string and then populated the atomic, that would be a data race, unless stronger memory order was used by both the writer and the reader.
Never mind, I don't think we're disagreeing on what the C++ standard definition of data race is. I think I thought you were saying something different in your comment.
Also the programs are not direct translations of each other - a direct translation to Java would use varhandle and opaque (equivalent to relaxed), and then would not contain a data race.
You can't precisely convert it to c++, because there's no c++ construct that precisely matches Java behavior - namely atomic with relaxed memory order but permitting aliasing and load/store optimizations. The spiritually closest thing would just be a regular variable, which would be a data race that tsan would catch.
You can go the other way, porting that c++ to Java using varhandle and opaque memory order.
The Java specification which can be found here [1] makes clear that with respect to its memory model the following is true:
1. Per 17.4.5 your example can lead to a data race.
"When a program contains two conflicting accesses (§17.4.1) that are not ordered by a happens-before relationship, it is said to contain a data race."
2. Per 17.7 the variable s is accessed atomically.
"Writes to and reads of references are always atomic, regardless of whether they are implemented as 32-bit or 64-bit values."
However, atomic reads and writes are not sufficient to protect against data races. What atomic reads and writes will protect against is word tearing (outlined in 17.6 where two threads simultaneously write to overlapping parts of the same object with the result being bits from both writes mixed together in memory). However, a data race involving atomic objects can still result in future reads from that object to result in inconsistent values, and this can last indefinitely into the future. This does not mean that reading from a reference will produce a garbage value, but it does mean that two different threads reading from the same reference may end up reading two entirely different objects. So, you can have thread A in an infinite loop repeatedly reading the value "uninitialized" and thread B in another infinite loop repeatedly reading the value args[0]. This can happen because both threads have their own local copy of the reference which will never be updated to reflect a consistent shared state.
As per 17.4.3, a data-race free program will not have this kind of behavior where two threads are in a perpetually inconsistent state, as the spec says "If a program has no data races, then all executions of the program will appear to be sequentially consistent."
So while atomicity protects against certain types of data corruption, it does not protect against data races.
> Two threads writing a value to the same memory location (even atomically) is usually a data race in the CS/algorithm sense (due to the lack of synchronization), but not the C++ sense
You seem to conflate the concepts of "data race" and "race condition", which are not the same thing.
Two threads writing to the same memory location without synchronization (without using atomic operations, without going thru a synchronization point like a mutex, etc.) is a data race, and almost certainly also a race condition. If access to that memory location is synchronized, whether thru atomics or otherwise, then there's no data race, but there can still be a race condition.
This isn't a pedantic distinction, it's actually pretty important.
> Two threads writing a value to the same memory location (even atomically) is usually a data race in the CS/algorithm sense (due to the lack of synchronization), but not the C++ sense
Not only are you incorrect, it’s even worse than you might think. Unsynchronized access to data in c++ is not only a data race, it’s explicitly undefined behavior and the compiler can choose to do whatever in response of an observed data race (which you are promising it isn’t possible by using the language).
You are also misinformed about the efficacy of TSAN. Even in TSAN you have to run it in a loop - if TSAN never observes the specific execution order in a race it’ll remain silent. This isn’t a theoretical problem but a very real one you must deeply understand if you rely on these tools. I recall a bug in libc++ with condition_variable and reproducing it required running the repro case in a tight loop like a hundred times to get even one report. And when you fixed it, how long would you run to have confidence it was actually fixed?
And yes, race conditions are an even broader class of problems that no tool other than formal verification or DST can help with. Hypothesis testing can help mildly but really you want at least DST to probabilistically search the space to find the race conditions (and DST’s main weakness aside from the challenge of searching a combinatorial explosion of states is that it still relies on you to provide test coverage and expectations in the first place that the race condition might violate)
TSAN observes the lack of an explicit order and warns about that, so it is better in some sense than just running normally in a loop and hoping to see the occurrence of a specific mis-ordering. But that part of it is a data race detector, so it cannot do anything for race conditions, and as soon as something is annotated as atomic, it cannot do anything to detect misuse. It can be better for lock evaluation, as it can check they are always acquired in the same order without needing to actually observe a conflicting deadlock occurring. But I agree you need more formal tooling to actually show the problem is eliminated and not just improbable
Geez. I'm well aware it's UB. That was just sloppy wording. Should've said "not necessarily", okay. I only wrote "not in the C++ sense" because I had said "even atomically", not because I'm clueless.
HackerNews isn't not exactly like reddit, sure, but it's not much better. People are much better behaved, but still spread a great deal of misinformation.
One way to gauge this property of a community is whether people who are known experts in a respective field participate in it, and unfortunately there are very few of them on HackerNews (this was not always the case). I've had some opportunities to meet with people who are experts, usually at conferences/industry events, and while many of them tend to be active on Twitter... they all say the same things about this site, namely that it's simply full of bad information and the amount of effort needed to dispel that information is significantly higher than the amount of effort needed to spread it.
Next time someone posts an article about a topic you are intimately familiar with, like top 1% subject matter expert in... review the comment section for it and you'll find just heaps of misconceptions, superficial knowledge, and my favorite are the contrarians who take these very strong opinions on a subject they have some passing knowledge about but talk about their contrarian opinion with such a high degree of confidence.
One issue is you may not actually be a subject matter expert on a topic that comes up a lot on HackerNews, so you won't recognize that this happens... but while people here are a lot more polite and the moderation policies do encourage good behavior... moderation policies don't do a lot to stop the spread of bad information from poorly informed people.
There was a lot of pseudo science being published and voted up in the comments with Ivermectin/HCQ/etc and Covid, when those people weren't experts and before the Ivermectin paper got serious scrutiny.
The other aspect is that people on here think they're that if they are an expert in one thing, they instantly become an expert in another thing.
This is of course true is some cases and less true in others.
I consider myself an expert in one tiny niche field (computer generated code), and when that field comes up (on HN and elsewhere) over the last 30 years the general mood (from people who don't do it) is that it's poor quality code.
Pre-AI this was demonstrably untrue, but meh, I don't need to convince you, so I accept your point of view, and continue doing my thing. Our company revenue is important to me, not the opinion of done guy on the internet.
(AI has freshened the conversation, and it is currently giving mixed results, which is to be expected since it is non-deterministic. But I've been doing deterministic generation for 35 years.)
So yeah. Lots of comments from people who don't fo something, and I'm really not interested in taking the time to "prove" them wrong.
But equally I think the general level of discussion in areas where I'm not an expert (but experienced) is high. And around a lot of topics experience can be highly different.
For example companies, employees and employers come in all sorts of ways. Some folk have been burned and see (all) management through a certain light. Whereas of course, some are good, some are bad.
Yes, most people still use voting as a measure of "I agree with this", rather than the quality of the discussion, but that's just people, and I'm not gonna die on that hill.
And yeah, I'm not above joining in on a topic I don't technically use or know much about. I'll happily say that the main use for crypto (as a currency) is for illegal activity. Or that crypto in general is a ponzi scheme. Maybe I'm wrong, maybe it really is the future. But for now, it walks like a duck.
So I both agree, and disagree, with you. But I'm still happy to hang out here and get into (hopefully) illuminating discussions.
I don't think that's much of an issue. If you need deferred initialization then stick to a pointer and then once the pointer is initialized shadow it with a reference.
>A solution to the Halting problem can be repurposed as a general-purpose theorem prover. The author is correct. You simply write a program that searches all possible valid proofs till it finds the one you are looking for (or maybe doesn't and runs forever).
The author is not correct and it's a common misconception. Simple question for you... let's say I give you a magical black box that can solve the halting problem. Now please use it to prove or disprove the continuum hypothesis (within ZFC).
Hopefully you'll come back to me and say the black box shows that the continuum hypothesis can not be proved or disproved (in ZFC). Okay we agree so far, but note that we have established that having a solution to the halting problem can not actually be repurposed as a general purpose theorem prover, since no such proof exists in the first place.
Okay you might counter by saying that a solution to the halting problem can be repurposed as a general purpose theorem prover for propositions that either have a proof or don't have a proof, ignore those pesky propositions that are neither provable or unprovable...
But then the solution to the halting problem doesn't get you anything... if you're dealing with a proposition that either has a proof or a proof of its negation, you don't need a solution to the halting problem to find it, you are guaranteed to find it eventually by definition.
The claim that a black box that solves the halting problem can be used as a general purpose theorem prover is simply untrue and confuses certain concepts together. At best you can claim it gives you a restricted theorem classifier.
You're mixing things up. By a "general theorem prover", we typically mean "a program which can decide for every sentence in FOL whether it's valid" (I say FOL, because the situation is even worse for HOL), i.e. a decider for the set of valid FOL sentences. The sentence ZFC -> CH (where ZFC and CH are expanded as needed) is not valid because CH doesn't follow from the ZFC axioms. Neither is ZFC -> not(CH) valid. We know both of these results from proofs specific to this problem, but a general purpose theorem prover would give us both of these results for free. If we had such a tool, mathematics would essentially be "solved" (maybe apart from deciding what questions to ask). But since FOL is undecidable, it can't exist.
What you are asking for is a machine that for each pair of formulas A, B (correctly) decides that either A -> B or A -> not(B), but this is impossible for model-theoretic reasons (not all theories are complete) and that has nothing to do with decidability.
Tainnor has basically already said what I would have (independence phenomena is an orthogonal concern, general purpose theorem prover does not mean "can prove X or not-X for any first-order sentence X").
> if you're dealing with a proposition that either has a proof or a proof of its negation, you don't need a solution to the halting problem to find it, you are guaranteed to find it eventually by definition.
You don't know what situation you are in ahead of time, this is the point (my proposed algorithm terminates on all inputs, including independent statements). If you had a black box machine that could tell you whether a statement was independent or not then that would be just as useful, yes. But that's also an undecidable problem. Yet a halting oracle can be used to compute it!
The author is correct, you are simply misusing or misunderstanding standard terminology =)
Terminology isn't the most important detail here and there's no real point dwelling on it, what's important are the actual fundamental concepts at play.
An oracle for the halting problem can not be used to prove or disprove the Continuum Hypothesis within ZFC. No amount of bickering over terminology can change that fact. You can claim that such an oracle can be used to show that the Continuum Hypothesis is independent of ZFC and that's true and something I explicitly pointed out in my reply to you, but that's not a general theorem prover at that point, that's a theorem classifier for a specific formal theory (namely ZFC).
ZFC is not the end-all be-all of first order logic and it's certainly not even a particularly good choice of formal model for dealing with Turing Machines. Your halting oracle will not be able to do the same kind of theorem classification for other formal theories, namely those that do not have a recursively enumerable set of axioms. The most obvious example of such theories are second order theories, but even if you restrict yourself to first order theories, you have examples of such theories like True Arithmetic where your halting oracle won't be able to classify propositions since even though it's a first order theory proofs can't be enumerated in the same way that proofs can be enumerated in ZFC (or other first order theories with recursively enumerable axioms):
In general if the basis of your argument depends on nitpicking terminology, then that's a good sign you might not actually understand the fundamental concepts at play and are instead just regurgitating terms that you've heard from other people which is what I suspect you're doing here.
And even works for some non-recursive theories like the first-order theory of true arithmetic.
The basic idea is that you can determine whether a sentence X is in the theory or not by searching every natural number for counter-examples, and then using your halting oracle to check whether that search terminates or not.
No it won't. You must first fix a specific theory to apply your solver to. It won't work for every arbitrary choice of theory even with recursively enumerable axioms.
First of all, I should have written "recursively enumerable theory" or "theory with decidable axioms". But I think it's clear that I'm referring to things like ZFC, first-order PA or any other similar system.
With that out of the way, it's pretty easy to write a general theorem prover for such theories if you can solve the halting problem.
First define a TM G that takes as input 1. the description of another TM A that decides whether a particular sentence is an axiom of some theory T and 2. a sentence P. We enumerate all syntactically valid proofs with P as the conclusion and check whether all axioms are valid according to A and all inferences are sound. If we find a valid proof, we stop. (G can obviously be built.)
Then define H such that it takes the same inputs as G, and then (using the halting oracle) determines whether G would halt given A and P. If yes, return true, otherwise false.
Then H would be a decider for the language consisting of all pairs T |= P, where T is some recursively enumerable theory.
Yes it will? This works for any first-order theory with a recursive set of axioms. You are simply searching for proofs of implications from the axioms and using the halting oracle to tell if the search terminates or not. By the compactness theorem this is guaranteed to work.
Of course you have to input the axioms, how would a theorem prover work otherwise?
In this case I meant compactness - if a statement follows from your (possibly infinite set of) axioms then it follows from a finite subset of them. But you can skin the cat in many ways, yeah (proof theory vs model theory way of looking at it I guess).
Look, I have a masters in mathematical logic (but bailed from my PhD, to my discredit). I know what I'm talking about. You are the one who started all this bickering about what counts as a theorem prover - personally I don't really care what you call it!
As for the stuff about CH, yes, there's nothing we disagree about there. And on non-recursive theories and logics without a sound/complete/effective proof theory, sure, a halting oracle isn't enough.
No one is asking you to spell out the edge cases, but when you claim that a halting oracle can be used as a general-purpose theorem prover and I point out the edge cases where that won't work, it's pretty egregious to then say that I'm mixing things up, I am misusing standard terminology, etc...
If you claimed every prime number is odd, and I point out that 2 is an even prime number, you don't get to turn around, pull out your credentials, claim I'm mixing things up and bickering around because I am pointing out an exception to your generalization.
The fact is a halting oracle cannot be used as a general-purpose theorem prover. At best it can be used as a way to classify theorems in specific first order theories with recursively enumerable axioms and I even admitted that much in my original response to you.
That some first order theories do not have recursively enumerable axioms and for these theories even an oracle for the halting problem is insufficient to either prove, refute, or classify as independent particular propositions is actually a fascinating topic in and of itself which could have led to a much more engaging conversation than the one you decided to go with by talking about your failed academic career and claiming I'm misinformed, but alas that ship has sailed and at this point and with that I don't think there is much further to discuss here.
Random ad-hominems don't do much for me, friend, I'm autistic (you'll have to kill my dog or something). Hit me with more logic - despite your odd character attacks I have enjoyed this exchange. Thinking about Turing degrees and nonstandard logics again has been refreshing.
I think I wounded your pride? That wasn't really my intention. I hope you recover soon.
Sure, but neither bcrypt or chess fall into the category of being unprovable, so having a halting detector doesn't help for those situations. The author is mixing up problems that are "hard" in the sense that we know in principle how to solve it but need a lot of resources, versus "hard" in the sense that we genuinely don't know how to solve the problem, even if we had access to infinite resources.
Mixing these two up is very misleading and detracts from what is otherwise a well written article.
Hard to say exactly how it will affect the market, but IIRC when deepseek was first released Nvidia stock took a big hit as people realized that you could develop high performing LLMs without access to Nvidia hardware.
I thought the reaction was more so that you can train SOTA models without an extremely large quantity of hyper-expensive GPU clusters?
But I would say that the reaction was probably vastly overblown as what Deepseek really showed was there are much more efficient ways of doing things (which can also be applied with even larger clusters).
If this checkpoint is trained using non-Nvidia GPUs that would definitely be a much bigger situation but it doesn't seem like there has been any associated announcements.
Plans take time to adjust; I imagine a big part of the impact was companies realizing that they need to buy/rent much less expensive GPU compute to realize the plans they've already committed to for the next couple years. Being able to spend less to get the same results is an immediate win; expanding the plan to make use of suddenly available surplus money/compute takes some time.
And then part of the impact was just "woah, if some noname team from China can casually leapfrog major western players on a tiny budget and kill one of their moats in the same move, what other surprises like this are possible?". The event definitely invalidated a lot of assumptions investors had about what is or isn't possible near-term; the stock market reacted to suddenly increased uncertainty.
Except that, all Deepseek models so far have been trained on Nvidia hardware. For Deepseek v3, they literally mention that they used 2,048 NVIDIA H800 GPUs right in the abstract: https://arxiv.org/html/2505.09343v1
I know of enterprises in APAC now spending millions of dollars on Huawei GPUs, while they might not be as efficient, they are seen as geopolitically more stable (especially given the region).
DeepSeek helped "prove" to a lot of execs that "Good" is "Good enough" and that there are viable alternatives with less perceived risk of supply chain disruption - even if facts differ may from this narrative.
https://openjdk.org/jeps/318
Implementing a garbage collector that is guaranteed to free memory when it's actually no longer needed is equivalent to solving the halting problem (via Rice's theorem), and so any garbage collection algorithm is going to have to leak some memory, it's simply unavoidable.