OK, help me settle a debate.

Is ASN.1 Turing complete?

(Accidentally Turing Complete counts. Proofs of concept are welcome.)

@soatok maximum gayness in all things.

I don’t think it is. There’s no branching or flow control that I know of. Maybe there’s some trick in the module import feature that gets you to recursion accidentally. I’m very much not a theorist, though.

What’s the Yes argument?

@tmaher X.680 5.7 discusses recursion

@soatok oh I see https://www.itu.int/rec/dologin_pub.asp?lang=e&id=T-REC-X.680-202102-I!!PDF-E&type=items

In the data structures themselves. Yea I would be very interested in an example of it being Turing complete

@astrid @tmaher It used to have Macro support.

@soatok I had managed to not think about ASN.1 for ages and now I both want to know and also do not under any circumstances want to know.

@daedalus @soatok this is the correct response

@soatok

ASN.1 is more like the necronomicon. gazing at it too long or attempting to write an ASN.1 parser will drive you to be incapable of passing a turing test.

@soatok I have spent too much time on thinking through this to win a stupid argument on the internet:
Well technically what I wanted to know is not TC but merely if it is possible to translate ML-KEM's keygen algorithm into ASN.1.

From what I can tell, it is definitely not a regular language, due to the pumping lemma. However, it is extremely hard to get it to compute pretty much anything, so my vote goes to not TC.

@sophieschmieg @soatok i don't know ASN.1 but have you tried to use the pumping lemma for CFGs? if it isn't context-free or regular, chances are it's pretty damn close to TC.

@sophieschmieg What if we permit macros?

@soatok "Do you mean ASN.1/DER or ASN.1/BER?"

<Questioner catapults into the abyss below the bridge>

[Apologies for the obscure reference]

@soatok The average ASN.1 parser is turning complete by accident (thanks, C).

@soatok @astrid @tmaher every piece of info you drop makes asn.1 a exponentially worse idea

@charlotte @soatok @astrid @tmaher ASN.1 has this weird quantum topological property where it’s simultaneously the worst thing you’ve ever seen and also once you’ve studied it you realize that the only thing worse than ASN.1 is ASN.1.

@novet @soatok the problem is that the pumping lemma works just because there are size prefixed strings. That makes the language not regular, but is pretty useless when trying to do anything interesting with it.

@wordshaper @charlotte @soatok @astrid @tmaher ASN.1 has everything you might want from a data serialization standard except simplicity

@wordshaper @charlotte @soatok @astrid @tmaher ah, yes "it's worse all the way down".

@wordshaper @charlotte @soatok @astrid @tmaher 💯

@fanf @wordshaper @soatok @astrid @tmaher does it at least have a data model that is better than “this is a number. it has no range or precision. a valid implementation might read this as a float or just as 0. also one of the 3 specs disagrees with itself on what a number even is grammatically”

@wordshaper @charlotte @soatok @astrid @tmaher does this also imply that a strict improvement over using ASN.1 would be to use ASN.1?

@ryanprior @wordshaper @soatok @astrid @tmaher every time you look at it it gets worse, so no

@wordshaper @charlotte @soatok @astrid @tmaher

ASN.1.

"recurses! foiled again!"

@soatok having worked only casually with ASN.1, my bet is on “yes, accidentally, like Magic: the Gathering”

@0x09 @soatok ... MtG is turing complete?

@lina @0x09 https://beza1e1.tuxen.de/articles/accidentally_turing_complete.html

@charlotte @ryanprior @wordshaper @soatok @astrid @tmaher yeah it's like how you can't undo entropy just by reversing direction

@ferrix @charlotte @ryanprior @soatok @astrid @tmaher the arrow of ASN.1 points only and forever in one direction. In case you were ever curious where the mad god Azathoth danced you can even follow it. (And you thought the A in ASN.1 stood for Abstract. We should be so lucky (but, alas, aren’t))

Management takes no responsibility for the results of following ASN.1 to its logical and inevitable conclusion.

@ferrix @ryanprior @wordshaper @soatok @astrid @tmaher it’s like those old stories of your grandparents where their commute to school was uphill both ways

@charlotte @ferrix @ryanprior @soatok @astrid @tmaher well, y’know, geography was a bit grumpier back in the day.

@wordshaper @ferrix @ryanprior @soatok @astrid @tmaher it was before euclidian geometry was invented

Since the poll is closed:

The consensus is "No". Which is also what I believe. Happy to be proven wrong, of course.

@soatok
I think ASN.1 is a classic example of mission creep and how the international standards process can fail big-time. The basic encoding rules for ASN.1 are simple and elegant. Everything else is an unusable mess.
(My company implemented an X.400 mail client on the BBC Micro, so I feel I have some standing in this debate.)

@KimSJ I don't think anything the ITU has ever been involved in did not involve complete and utter mission creep.

I am honestly curious if there was ever a something that was X.500 series (what LDAP is a cut down simplified version of) complete.

@soatok ...that does not appear to be the consensus answer from the poll

@cliffle Alan Turing appreciation is the gay option

Alan Turing fanfiction is the gayer option

Neither precludes "Yes" or "No"

@soatok so I guess the question becomes:

Is Alan Turing fan fiction... Turing-complete?