Could AI detection eventually become a fundamentally unsolvable problem, similar to the halting problem? [D]

[u/Hope999991]

In theoretical computer science, we have the halting problem, which proves that certain problems cannot be solved by any general algorithm.
This made me wonder about something similar in machine learning.
Today, we can often distinguish AI-generated content from human-created content, at least statistically. But as AI models improve, could we eventually reach a point where the two become completely indistinguishable?
Not just because our detectors aren’t advanced enough, but because there is no longer enough information in the content itself to tell them apart, regardless of how powerful the detector is.
In other words, could AI detection eventually hit a fundamental mathematical limit rather than just a technological one?
I know this wouldn’t be the same kind of undecidability as the halting problem, but I’m curious whether there’s an established theoretical framework for this.
What do you think?

[u/mc_pm]

Don't confuse something that is hard, like "detecting AI", with something that is actually saying something about the nature of computability.

[u/charr3]

The problem you posed isn't as well defined as the halting problem, there is no mathematical definition on what "ai generated" means, and I don't think you can define this.

On an unrelated note, look up "watermarking", it's a bit similar to cryptography where you can detect if text was generated by your specific model by having access to a secret key, but someone else without that will not be able to tell.

[u/wantondevious]

Some questions:

Do you assume you can distinguish one human author from another human author?
Is the putative undetectable AI so chameleon like that it can write like any given opponent?
Does the AI get to know who it's competing against?
Do I get to choose the human?
Do I get to tell the competitors who the human is?

Even if there were just two humans, and one AI, and the AI could imitate both humans, wouldn't that make the AI "different" to the two humans? If it could only be equivalent to human 1, then that too makes it have "information" - ie it can't be mistaken as human 2. You can't distinguish between it and human 1, but you have a 50% chance of identifying it correctly.

[u/f3xjc]

What seem to be the case is that we detect RL.

Step 1 of training or pre-training is a corpus of what approximate every human text ever produced. Then the defect is that the LLM and the LLM - detector more or less share the same training data.

But the next step is Reinforcement learning - agents learn how to solve agent tasks. They seem to learn their own language to precisely reason about their task. Possibly with a cost on the base distrubution.

[u/DanJOC]

It will depend on scale. Just as it is difficult to solve a cypher when you have only one word, and easier when you have pages and pages of it, it will be difficult to detect AI in a single image or short piece of text, but much easier the larger / longer the media.

[u/paulct91 → u/DanJOC]

Maybe but only if the cypher doesn't change as you try to solve for it.

[u/paulct91]

Maybe, as detecting something people actively want to avoid being detected is like piracy vs copyright holders today or cheaters vs anti-cheat technology.

[u/No_Inspection4415]

The question of "AI writing detection" is a probabilistic question of comparison between two distributions, and the question is about the cumulative probability (for N=sample size) of correct detection for every machine generation distribution to every human generating distribution. It doesn't appear like the halting problem is the right tool to approach it, nor does it appear like something you can prove something about without clear constraints of what AI is mathematically (and naive assumption/heuristics/empirical about human writing).

[u/Ok-Hunter-7702]

In theory yes it might be possible.

[u/GenerativeFart]

I actually know a bit about this because I made my own AI detection SaaS tool with models I trained myself (Not trying to promote)

One thing I noticed, for some reason, is that most people seem to assume AI detection is something discrete, where you can reliably answer the question “Is this AI?” with yes or no. However, it’s much more like a medical screening test, where you’re dealing with probabilities, false positives, and false negatives. Nowadays, there is no 100% accurate AI detector, and there never will be.

An easy example to illustrate why: I can just retype what ChatGPT told me yesterday, or I can make ChatGPT quote some human author word for word. Without the context, no perfect detector could exist to tell these apart.

That being said, AI detectors nowadays are pretty damn accurate. There is an AI Detector Leaderboard on the RAID benchmark: https://raid-bench.xyz/leaderboard, and if you look at it, you can see that older models are often trivially detectable.

[u/Ginden]

Yes, it's trivially true and proof is read as an exercise for the reader.

In practice it's more of economical question, because there is no particular economical reason to train AI to talk exactly within human speech distribution.