A bit too advanced…
I figured out the “answer” to my TeX question from yesterday—it’s undecidable! There is no way I can get my code to perform correctly and still finish up in a finite amount of time. The way to show this is similar to the proof that the halting problem is undecidable.
Quick sketch of the proof: What I want to do, in effect, is determine if there is a space at the end of the code created by the macro (so that if its expansion ends in a space and the next token after the macro is also a space, I can remove one of the spaces; otherwise I want to do nothing). Assume for the sake of later contradiction that I can create an \ifendsinspace{} function that takes an argument and returns \iftrue if the last token generated by the code in the argument is a space, and \iffalse otherwise (\iftrue and \iffalse are exactly what they sound like). Now, create the following macro:
\newcommand{\trouble}[1]{
% If the input, when run on itself, ends in a space,
\ifendsinspace{#1{#1}}
% write something that doesn't end in a space.
no-space-here%
\else% Otherwise,
% write something that ends in a space
space here: %
\fi% (this just ends the if statement)
}
Now, consider the output of \trouble{\trouble}:
- If it ends in a space, then
\ifendsinspaceis true, and thus it doesn’t end in a space. - If, however, it doesn’t end in a space, then
\ifendsinspaceis false, and it therefore ends in a space.
Either way, we have a contradiction, so we must reject our assumption and conclude that \ifendsinspace cannot be created. *hip thrust* BAM!
This explains why I was having so much trouble writing such a function! It’s pretty neat to find an undecidable problem in the real world; all other undecidable problems I’ve seen were contrived for classes I took at Mudd.
Correct me if I’m wrong, but intuitively, isn’t this just undecidable because computing the output of a function on all inputs is the halting problem?
I read somewhere that placement of figures is NP-Complete…who would think putting letters on paper is so hard?
Also, that #1{#1} thing makes me cry.
*exasperated look* Well, yeah, it sounds easy when you say it like that…
This caught me off-guard because this is the first time I’ve ever found that whitespace within a paragraph actually was handled wrong. It’s the first time I’ve noticed a difference between parameterless macros and those with parameters (there wouldn’t be a problem if I didn’t use a macro with arguments). Moreover, the fact that this problem might exist didn’t even occur to me until I accidentally stumbled upon it (at which point I assumed that it shouldn’t be hard to fix, since LaTeX typically handles this so seamlessly on its own). I didn’t see what this was at first because it broke all the rules I typically take for granted in LaTeX.
I would be very surprised if figure placement was NP-Complete, but I’ve already shown that I have poor intuition on this stuff. And if you think the #1{#1} is bad, wait ’till you see what I’ve been working on!
Better yet, isn’t this just Rice’s theorem saying “oh, you want to know something interesting about your fuction? Too bad!”?
But you really aren’t sunk unless TeX’s really shot you in the foot, are you?
foo(x,y,z)[-1] == " " should do it, yes? (Where [-1] is pythonese for “last element”).
I mean, that’s not computable, but as long as foo() is sane (which is up to you), then it’s still practical…