Very captivating question indeed, and we will see that your thinking IS correct.
First let's see what the second principle of thermodynamics says.
The entropy function is used in the 2nd law of thermodynamics. It stems from Carnot's theorem which states that processes taking places in steam machines have an efficiency lower or at best equal to the corresponding "reversible" machine (which by the way seems like an unstable concept over the 150 years of thermodynamics). Carnot did not coin the entropy function himself, but together with Clausius this is what they say:
As there is no perpetuum machine, then we can build a function S called entropy which constrains macroscopic thermodynamic measures into a certain equation, namely that S(V, T, P, etc.) = 0
Note that this equation is nothing but the equation of a hyper-surface in the space of thermodynamic measures.
Carathéodory is a German mathematician and like all mathematicians he wants to extract out of Carnot's and Clausius reasoning some axioms which would allow him to clarify what the second law really is about. Put bluntly he wants to purify thermodynamics to know exactly what entropy is.
After listing a certain number of axioms, he manages to formulate HIS second law, which says (more or less):
There ARE some adiabatic processes. Or more prosaically, if you want to return, sometimes work alone is not enough. You need a bit of heat.
Now that seems VERY different from the formulation of Clausius! But in fact it it not. All Carathéodory did was to change the orders of the words, a bit like mathematicians played with Euclide's 5th axiom for 2,000 years and produced many different wording for that axiom. And if you take a step back you should not be too surprised by Carathéodory's statement of the second law. In fact Carathéodory's leads to the exact same entropy function and hyper-surface equation S(V, T, P, etc.) = 0
Think hard on Carnot's theorem. As a mathematician, you should not be too satisfied of the way Carnot's admits perpetuum machines do not exist. In fact, as a mathematician you would rather see something like this:
There is an entropy function S which constrains macroscopic measures IF AND ONLY IF there is no perpetuum machines".
NOW you have a theorem. And what does it say? That as long as there is no isolated mechanical system which produces an infinite amount of energy and hence could lead you to any state you want, then you will find an entropy function. An isolated mechanical system is an adiabatic process. Hence Carathéodory's formulation: no adiabatic system can lead you anywhere. Sometimes you will need some heat.
So not only we are sure that Carathéodory's is correct, but also that his formulation is pretty simple.
Now where do you get the impression that the second law à la Carathéodory is similar to the halting problem?
Take a step back on Carathéodory's statement. All it says is that once you have an isolated mechanical system which you stop mingling with, you cannot reach any state you want.
Doesn't that sound PRECISELY like the halting problem? I.e. once you have written all axioms of your theory and laid down all possible transitions, there will be problems which you cannot solve. Sometimes, you will need to add more axioms.
In fact if you want to go really deep and encode Carathéodory's formulation, this will result in the same code as the halting problem with adiabatic processes instead of Turing machines, and states instead of problems.
What do you think?
NOTE: I edited my answer almost entirely so comments below won't be in line with what it contains now.