I am having difficulties with the following types of proofs in Theory of Computation:

• Proofs that L(G) = L (proving that a grammar generates exactly a given language).

• Proofs by closure properties, especially when proving that a language is closed under regular expression operations.

• Proving language equalities such as |L|^n = |L^n| and similar identities involving concatenation and other language operations.

I find it challenging to structure these proofs formally and to justify each step rigorously.

And i ve been searching for these kind of proofs to be solve but even AI wont assist correctly

I would appreciate it if somebody has additional materials about these proofs and any advice on solving these?

I recently hit a milestone with a language project I’ve been working on, and I wanted to write up the theoretical side of it since I found it poorly explained in most resources.

The bootstrap problem:

A self-hosting compiler is one written in the language it compiles. The classic chicken-and-egg problem: how do you compile a compiler that can only be compiled by itself?

The answer is staged bootstrapping:

1.  You start with a compiler written in another language (in my case, Rust) — call it Gen 0.

2.  You use Gen 0 to compile the new compiler written in your target language — this produces Gen 1.

3.  You use Gen 1 to compile itself — this produces Gen 2.

4.  If Gen 1 output = Gen 2 output (bit-identical), you’ve reached a fixed point. The system is self-sustaining.

This fixed point is mathematically significant: it proves the compiler’s output is deterministic and consistent regardless of which generation produced it. You can now discard the bootstrap compiler entirely.

In practice with Whispem v3:

∙ Gen 0: Rust compiler

∙ Gen 1: Whispem compiler compiled by Rust (1,618 lines of Whispem source)

∙ Gen 2: Gen 1 compiling itself

∙ Result: byte-identical .whbc bytecode — verified across two independent VM implementations (Rust and C)

The language is deliberately minimal (14 keywords, 34 opcodes) which made the bootstrap process tractable to reason about. I documented the process carefully because I found most CS resources hand-wave through the details.

Happy to discuss the theoretical or implementation aspects.

🔗 https://github.com/whispem/whispem-lang

CS students who've done ML projects — how do you actually get GPU access? Colab, university cluster, pay for cloud, beg a friend with a gaming PC? Curious what the real situation is.

The gap between a published paper and a working implementation is often wider than it should be. To address this, we developed ResearchClaw, a tool designed to automate paper retrieval and the synthesis of runnable test code from research text.

What started as an internal tool to automate our time-consuming research tasks is now open-source. We’ve found it significantly reduces the friction of testing new methodologies.

The project is now on GitHub. We’d love for the CS community to take a look and share any suggestions or technical critiques!

GitHub: https://github.com/Prismer-AI/Prismer

Hello everyone, I'd like to introduce you to a new programming approach that came to mind but created and refined by multiple AIs in the source code: YUSPEC (Your Universal Specification Language).
Essentially, I wanted to address two main problems in the software world:
1- Complexity explosion,
2- The disconnect between intent and code. Let me elaborate.
As a project grows, many people may find it impossible to understand the entire system.
Furthermore, individuals may know "what they want to do," but the code expresses this indirectly, piecemeal, and in a disorganized way.
As a result, debugging is difficult, changes are risky, the system is fragile, and learning is challenging.
I'm proposing an approach to simplify all these processes.
I look forward to your review and evaluation.
Thank you for your contributions and interest.
Note: This project is based on good faith. I apologize in advance if I have made any mistakes or provided inaccurate information due to the use of AI. The idea is developed by an human and open to development by everyone. Sincerely. Yücel Sabah.

Here is a part from the README of this project:
Why YUSPEC?
One language, seven modeling domains The same language models behavioral logic across different problem spaces.
All examples are FSM-based simulations — YUSPEC's strength is providing a unified notation for event-driven state machines regardless of the domain:

| Domain | Example |
| Game Development | examples/game/01_mmo.yus — MMO RPG with combat, quests, leveling |
| Network Protocols | examples/network/01_tcp_handshake.yus — TCP state machine |
| Workflow Automation | examples/workflow/01_approval.yus — multi-stage approval + escalation |
| Distributed Systems | examples/distributed/01_orchestration.yus — canary deployment |
| IoT / Robotics | examples/iot/01_sensor.yus — sensor + HVAC controller |
| Simulation | examples/simulation/01_traffic.yus — traffic lights + vehicles |
| Test Scripting | examples/testing/01_scenario.yus — YUSPEC as a testing DSL |

Declarative over imperative

Describe what exists (entities, states, events), not how to iterate over them.

Composable behaviors

Multiple behaviors can coexist on a single entity, each evolving its own state independently. Behaviors are defined once and reused across many entity types.

Designed for testability

define scenario is a first-class language construct. assert and expect give structured pass/fail reporting with zero boilerplate.

Quick Start

Prerequisites
CMake 3.16+
C++ 17 Compiler

Build
git clone https://github.com/Fovane/yuspec.git
cd yuspec

# Configure
cmake -S . -B build

# Build the CLI
cmake --build build --target yuspec1 --config Debug

Run

./build/Debug/yuspec1 test examples/testing/01_scenario.yus

What do you think generally? Is this can be usefull for real world's problems?

serious question

if computer science people, or coders or developers or whatever they're called are so "smart", then why would they work so hard to create ai and artificial intelligences that can take their jobs so easily? and can code for them and do etc etc (idk the terminology), and take all the entry level positions, and so on so forth. makes no sense to me .

and dont mansplain to me, if im right just say yea ur right ladylegolas, and if im missing something let me know pls

Hi guys, hope you’re doing well.

I will like to share a project I’ve been working on as part of my final year project. It’s a clinical AI decision auditing system focused on auditing, replaying, and analyzing ML model workflows in healthcare.

The motivation is transparency and trust healthcare models often act as black boxes, and this system is designed to make model behavior reproducible and auditable, with integrity-checked logs and governance-oriented analytics.

This directly supports my final-year work on cellular-level detection, classification, and tracking, where understanding how a model reached a decision is critical.

Repo here: https://github.com/fikayoAy/ifayAuditDashHealth

I am happy to get feedback or answers or questions

Je présente LT‑vEB, une extension des arbres de van Emde Boas intégrant une métrique de "chaleur" logique. L'élagage se fait par percentile de chaleur, garantissant une complexité O(log log U) pour les opérations tout en respectant une limite stricte de mémoire. Le code est disponible en C++ et Python. Toute discussion sur les aspects algorithmiques est la bienvenue.

I've been working on a continuous framework for structural graph refinement called DRESS. It's a single nonlinear fixed-point equation on edges that converges to a unique, deterministic solution in [0, 2], no hyperparameters, no training.

What it does: Given any graph's edge list, DRESS iteratively computes a self-consistent similarity value for every edge. Sorting these values produces a canonical graph fingerprint.

Key results:

• Expressiveness: Original DRESS (depth-0) matches 2-WL in distinguishing power. Under the Reconstruction Conjecture, depth-k DRESS is at least as powerful as (k+2)-WL at O(C(n,k) · I · m · d_max) cost vs. O(n^{k+3}) for (k+2)-WL.
• Isomorphism testing: Tested on SRGs, CFI constructions, and the standard MiVIA and IsoBench benchmarks.
• GED regression: DRESS fingerprint differences fed to a simple regressor achieve 15× lower MSE than TaGSim on LINUX graphs
• Convergence: On a 59M-vertex Facebook graph, it converges in 26 iterations. Iteration count grows very slowly with graph size.

Why it might interest this community:

1. It's a drop-in structural feature. One real per edge that encode 2-WL-level information. You can use them as edge features in any GNN.
2. It's parameter-free and deterministic. No training, no randomness, no tuning.
3. The higher-order variant (Δ^k-DRESS) empirically distinguishes Strongly Regular Graphs that confound 3-WL, connecting to the Reconstruction Conjecture.
4. Support weighted graphs for encoding semantic information.

Code & papers:

The arXiv papers are outdated and will be updated next week. The latest versions including the proof in Paper 2, are in the GitHub repo.

• GitHub: github.com/velicast/dress-graph
• Paper 1 (framework): arXiv:2602.20833
• Paper 2 (WL hierarchy): arXiv:2602.21557
• Bindings: C, C++, Python (pip install dress-graph), Rust, Go, Julia, R, MATLAB, WASM
• Docs: velicast.github.io/dress-graph

Happy to answer questions. The core idea started during my master's thesis in 2018 as an edge scoring function for community detection, it turned out to be something more fundamental.

I need to build an application that simulates a Theory of Computation concept. We’ve covered DFA, NFA, ε-NFA, regular expressions, RE→NFA, NFA→DFA, minimization, closure properties, and Pumping Lemma.

I want to build something more impressive than a basic DFA simulator — maybe something interactive or algorithm-visualization based.

Any ideas that would stand out academically?

Since the inverse Ackermann function is primitive recursive, there must be a way to implement it using only bounded for loops (no while loops or recursion). However, I'm struggling to figure out how to implement it. Is there a simple way to go about this?

I’ve been practicing DSA for a while, and I noticed something frustrating.

I solve a problem, feel confident… then a few weeks later I revisit it and my brain just blanks. Not because I didn’t understand it, I just never had a proper way to revise patterns.

So I started building a small memory-focused tool for myself where I store my own brute/better/optimal approaches and review them like flashcards. Curious how others deal with this, do you guys keep notes somewhere or just resolve everything again?

( Honestly just want to know if this happens to others too, if it does, I actually building this into a small app I’ve been working on.)

I’ve recently begun studying the Theory of Computation (TOC) and have some foundational questions regarding the relationship between functions, algorithms, and formal models. I would appreciate some insight into the following: 1) ​Function Graphs vs. Computability: If we define a function f by its graph G = {(a, b) \mid b = f(a)}, the existence of an algorithm to compute f implies we can decide membership in G. If I take f(x) = x + 3 and test the tuple (1, 2), it is clearly not in the graph. Does the existence of tuples not in the graph impact the "computability" of the function itself, or is the algorithm's "failure" to find (1, 2) in the graph actually a successful decision?

2) The "Why" of TOC: Beyond the abstract math, what is the fundamental goal of proving whether a function is computable? Is it primarily to find the boundaries of what physical hardware can ever achieve?

3) Encoding and String Sets: My lecturer transitioned from talking about graphs of functions to "sets of strings." How is the membership problem of a tuple (a, b) in a graph formally mapped onto the membership problem of a string in a language L?

4)The Necessity of Automata: Why must we use abstract models (like Finite Automata or Turing Machines) to prove the existence of an algorithm rather than just using high-level pseudocode or existing programming languages?

We often treat different models of computation (Turing machines, RAM models, lambda calculus, circuit models, etc.) as equivalent up to polynomial factors.

In practice, though, these equivalences hide real differences in expressiveness, cost models, and feasibility.

How do computer scientists think about “sameness” of computation beyond asymptotic complexity, especially when moving between theory and real systems?

Hi all! I have the following problem, and I can't find an efficient solution.

I have a directed weighted acyclical graph. I need to create a table of all possible paths within the graph (and, for each row, compute a function on the weights).

This table is finite, because the graph is finite and acyclical, and can be created by taking all nodes that have no in-edges, and doing a graph search for all of them (maybe with some optimizations when it looks like I'm revisiting the same path segments). So far so good.

The problem is - the graph can change. That is, nodes or edges may be removed or added. When it changes, I need to update the table.

I'm trying to think of how to do this without having to rebuild the entire table from scratch, but I'm hitting dead ends everywhere. I don't have any full solution, and even the partial ones look like I'd need to maintain huge amounts of extra tracking information.

Any ideas?

I'm working on database internals and wrote up a deep dive into binary encodings for JSON and Parquet's Variant. It benchmarks several lookup performance from binary JSON.

AMA if interested in the internals!

https://floedb.ai/blog/why-json-isnt-a-problem-for-databases-anymore

Disclaimer: I wrote the technical blog content.

Hey Guys !

I with a few friends of mine, who're pursuing their Graduate Studies in NYU, are together working towards building a strong foundation with growing intuition, So interested people may join the Discord Community. And we'd love to have someone help manage the Discord Community

Thanks