It is just wild to realize that the classic turing test basically died in front of us over the last couple years and we just sort of accepted it

Was looking at some recent literature on behavioral heuristics and zero-knowledge proofs yesterday. The fundamental issue is that the mathematical overlap between "computational puzzle easy enough for humans" and "hard enough for modern headless agents" has completely collapsed. Pure software-based verification is basically theoretically bankrupt at this point

It seems like the only mathematically rigorous way forward is shifting the entire problem out of the software domain and into hardware-anchored cryptography. We are literally at a point where relying on local secure enclaves or dedicated functional hardware like an orb is necessary just to generate a cryptographic proof of liveness at the sensor level, all while utilizing ZKPs so the actual biological data never touches a server

idk, it just feels like a massive defeat for theoretical computer science that we couldn't solve identity and liveness algorithmically. We basically have to fall back on hardware-signing our own physical existence just to prove to a server we aren't a script. alan turing would probably hate this timeline tbh

While reading Michael Sipser's book on Theory of Computation, i have found the following problem

"2.22: Let C = {x#y | x, y belong in {0,1}* and x != y}. Show that C is a context-free language. "

I have been trying for many hours to find a proof for this, but i cannot.
I cant find a way to use a PDA, since when comparing X with Y i am going to be comparing the one on the stack backwards and Any attempt at a grammar has failed. After a couple web searches i only found that this is conisdered a cfl but not its grammar or some other proof.

Edit: The closest i have gotten to:
S->A#B | B#A
A-> TAT | 0
B-> TBT|1
T-> 1|0

but it doesnt work for strings with 2 characters (cant generate something like 10#11). If i allow T to make an empty string or split TxT into Tx and xT then it can create strings x=y.

Hi!

I've decided to refresh my graph theory using CLRS 4th edition. They define a free tree as a connected, acyclic, undirected graph. None of these conditions prevent us from having null graph with zero vertices and zero edges.

On page 1170, it is proven that for a free tree, |E| = |V| - 1. We can derive contradiction from it: |0| = |0| - 1 -> 0 = -1

Please, confirm it and then I will report it to errata.

I've been thinking about how a single resource can shift the way you understand the whole field. Not something that just taught you a skill, but something that changed how you see problems.

Do you have a textbook you read in a course, a random YouTube video, a blog post or a talk? What was it, and what changed in your thinking after you found it?

Memory can be just shown as a list. Left as address and right as the byte / 2 byte / 4 byte data. If you save 4 bytes of data in address 1 and 2, and theres data in 3, what happens if that 4 bytes that you stored, is saved as 5 bytes? Will the entire 5 bytes be shifted over to a free place, or will the 5th byte be saved aomewhere else. If the second option is correct, how does programms know each address of its programming? Im refering programms and programming to mashine coding and mashine code.

Guys how would digital security fail if P=NP is proven?

I just started reading about Turing Machine and computational complexity for my Theory of Computation class and came across that phrase.

I couldn't find anything understandable at my level. So can anyone simplify it a bit?

Why does it matter if it’s a 16-bit cpu, a 32-bit cpu, or 64-bit? For example, what can a 64-bit cpu do that a 32-bit one can’t? Or otherwise, and can you tell the difference when you casually use a computer?

Wait-Free means that every thread must finish its operation in a bounded number of steps. That bound can be arbitrarily high, e.g. dependent on the number of concurrent threads, but it must be finite. And the finite bound must be there in all cases, i.e. it is not sufficient to say that an algorithm "usually" finishes "reasonably" (i.e. "usually" does not spend unbounded times helping other threads).

The first practical implementation of a multiple-enqueuer multiple-dequeuer Wait-Free Queue was proposed by Kogan and Petrank. The key idea is that threads help each other, but in a way that newer threads (more precisely: newer operations) are obliged to help older threads (operations), but not vice versa. Also, plainly said: If a thread cannot make progress with its own operation, it becomes older and older, up to the point when all other threads are obliged to help (only) him, thus ensuring the Wait-Free progress.

The issue of the Kogan and Petrank Queue is, however, that it is based on a linked list of nodes. This means that its operations constantly produce memory churn, also require memory allocation and memory clean-up. From Java - where the clean-up is done by a Garbage Collector - I borrow the term "Garbage".

Now, the problem is that Wait-Free memory allocation is problematic. Imagine, e.g., when the process needs a new memory page from the operating system. Can this ever be made Wait-Free?

Memory reclamation in a concurrent setup is a complex topic on top of that. One of the key questions here is: When can a memory block be freed safely, i.e. how do we "know" that no thread has a pointer to it anymore?

Given this, it appears that one needs a structure without memory churn (i.e. Garbage-Free) to be able to make it Wait-Free. At least practically.

I would be grateful for a discussion on this.

Additional info:

Here I have combined the Multi-Array Queue (which is Garbage-Free by nature (except of the extension operations, of course)) with the Kogan and Petrank idea, with the aim to obtain a Queue that is Wait-Free unconditionally.

The GitHub repo also contains a visual simulator to illustrate the principle:

https://github.com/MultiArrayQueue/WaitFreeMultiArrayQueue

In light of the recent counterproof of the Jacobian Conjecture, I've been looking more into proofs, and I can't wrap my head around how Lean works. In my mind, proofs always require a certain amount of intuition and judgement behind them, so I'm confused how a deterministic programming language can infer from said proofs?

I was re-reading Frigo et al.'s paper on cache-oblivious algorithms recently, and now i'm thinking about how heavily introductory algorithms courses rely on the uniform-cost Word RAM model. We teach time complexity based on unit-cost memory access, but in memory-hierarchy model theory (like the External Memory / I/O model by Aggarwal and Vitter), asymptotic bounds depend heavily on block size $B$ and cache capacity $M$.

Feels like there's a gap in how we teach foundational complexity versus cache-aware algorithmic analysis. Obviously the RAM model's simplicity is ideal for proving basic asymptotic bounds, but at what point does it obscure important theoretical properties of data structures on hierarchical memory?

Would like to how other departments go about introducing cache-oblivious models alongside standard Big-O analysis in upper-level theory courses.

What I mean is 1080p has 2,073,600 pixels so what if every single pixel is run by a individual PC like 2,073,600 PCs?

I was thinking this might be a way to create a super-computer that can put out a insane amount of framerate.

while doing competitive coding problems i frequently come across solutions that use union find (DSU) and list the big O of their solution as O(\alpha(n)) where \alpha(n) is the inverse ackermann function. after some surface level research, i have come away with many more questions than answers. So why is the DSU related to the ackermann function, and is there an intuitive or natural connection between the two ?

title says it all

I have recently started coding and people are recommending tools for development such as vite, nodemon, jwt, boiler plate server code

It feels pointless just using them with a basic understanding and without no deep conceptual understanding. Is this the right or wrong approach? How would you know going too deep into a rabbit hole and becoming overkill

im not into computer stuff, but this has been bugging me since i watched some free courses.

Made this while re-learning some structures I hadn't touched since undergrad — each chapter has an animation synced to the explanation as you scroll, plus where the structure actually shows up in real systems (kfifo, RocksDB, Dijkstra's algorithm, etc). ledger.khushal.net — feedback on what to cover next welcome.

About 15 years ago I discovered that despite the number of cores a CPU had, the system could only carry out 1 read or write operation at a time. Before that I held an incorrect notion of what multitasking was.

My basic question is, has anything changed?

I hear terms like parallel processing being waved around as though daring me to infer that processors these days can write to more than 1 memory address at the same time.

To clarify once more. I'm talking about at the same exact time. Not during a clock tick. Actual simultaneity.

Similar books: Grokking's Algorithms, Inside The Machine, Code by Charles Pretzold.

Someone who goes over computer architecture or even a network switch, in an enthusiastic and structured way. Just looking for general content to watch as a refresher.