Practical implementations of revolutionary new technology often follows theoretical breakthroughs. Thus Watt invented the steam engine after the laws of mechanics were formulated by Newton, and Crick and Watson discovered the structure of the DNA before genetic engineering could take off.
Somewhat contrastingly, bitcoin bursted into existence before solid theories of the governance of distributed systems existed. Yes, the usage of cryptography and of distributed computing was based on solid theoretical bases, and the role of incentives in economics was known, but until then, few if any studies were available about the sociological interactions generated in distributed computer systems.
Bitcoin was not an academic project but rather a very practical one, with a clear objective: proposing a system for electronic transactions non reliant on a trusted third party. Because it was so successful at what it aimed to achieve, it generated a lot of commentary and academic study.
These ex-post studies began creating a specific vocabulary. While today everybody can tell you that "bitcoin is based on a blockchain", the Bitcoin whitepaper remarkably does not use the word! Yes it uses the word "block" and the word "chain" but at no point it combines them into today's ubiquitous "blockchain".
Thus the concept of a "public permissionless blockchain" is not a theoretical concept that would have been introduced by an academic and then implemented in practice by Nakamoto. Quite the opposite, the practical implementation was first and the analysis which led to a specific glossary followed.
It follows that in order to clarify what a "public, permissionless blockchain" is, one should look at bitcoin and all the blockchains which tried to emulate it afterwards such as litecoin, ethereum and others.
Permissionless
What makes thes systems "permissionless" is summed up in the conclusion of the bitcoin paper (see picture above):
"The network is robust in its unstructured simplicity. Nodes work all at once with little coordination. They do not need to be identified, since messages are not routed to any particular place and only need to be delivered on a best effort basis. Nodes can leave and rejoin the network at will, accepting the proof-of-work chain as proof of what happened while they were gone."
Systems chaining blocks of digitally signed data using cryptographic hashes can technically claim to be "blockchain systems" but whether they are "permissionless" depends on one crucial step: the need for nodes to be identified, or lack thereof.
The "permissionless" concept is relatively easy to grasp: if nodes do not need to be identified and can leave and rejoin the network at will, it follows that any person or organisation can spawn as many nodes as it sees fit and join the network with all of them or just a part, without any other participants knowing that several nodes are controlled by the same person or entity. The network is resilient to Sybil attacks - thanks to the "proof of work" mechanism.
What a Sybil attack is, is explained among others in the picture below, sourced from the "Blockchian for the SDG" site.
Permissioned
The distinction between "permissionless" and "permissioned" is not an academic, theoretical one. We saw above that "permissionless" is in fact defined empirically by the fact that the system is governed "like Bitcoin / Litecoin / Ethereum ..."
It follows that one can argue, any system which is not governed like Bitcoin, is by definition "permissioned".
In particular, any system where the nodes need to be identified is arguably a permissioned system.
That might seem intellectually unsatisfying but think of the following: up to now, the only mechanism proved at scale to resist Sybil attacks in a permissionless environment is the "Proof of work". Any blockchain system not using proof of work is not resilient to Sybil attack ... unless it introduces a system of "permissions" to a certain degree.
Let's think this through to see whether it makes sense. I'll look at this from two angles: why "giving permission" is necessary to integrate with the law-based world and why, absent a PoW mechanism, "identifying nodes" is equivalent to implementing a "permission" system.
Compliance with the law requires "permission"
Bitcoin is the proverbial "honeybadger": it doesn't care about "the law" or anything else. This allows bitcoin to be permissionless.
But imagine you want to build a law abiding blockchain-based system. The central "object of law" is the "person" - whether a "natural person" or a "legal person". The practice of law boils down to judging whether a "person" has abided by the law or not.
If you want to be "compliant with the law", you need to be able to identify a "person" (again, either a "natural" or a "legal" one), in order for the law system to decide whether the acts of said person were lawful or not. If you build a blockchain-based system and something bad happens (anything - tax evasion, money laundering, pedopornography, etc.) you are on the hook. Unless either you (and all the other participants) are anonymous (like in bitcoin and its ilk) or everybody is identified and then you can point to law enforcement who the actual perpetrator might be.
Now let's say you identify people who want to participate in your system, and you do so in a proper sense (the unpleasant "KYC"). You do it because "it has to be done" and you want to be law-abiding and stuff, but you also want to be very open and let anyone in so you just store the KYC information "just in case" without doing anything with it.
And then "boom", one of the guys you KYC-ed and let in does something bad and law enforcement ("LE") comes knocking on your door (because you are identified as well and registered as "accountable" for the system").
You look at the data LE presents you with, linking "bad stuff" with a public key. You get out your KYC register and are able to tell LE that the owner of the public key who broke the law is "Mr X". He gets a fine and you are kindly asked to somehow "boot him out", i.e. take any measures you deem appropriate in order to prevent him from recidivating.
It can be argued that whatever you do, you cannot call your system "permissionless". But for the sake of the discussion, let's explore a bit further
Imagine you boot Mr. X out somehow (you designed your system so you can revoke his pair of keys). But 6 months or 1 year later Mr. X comes again and requests an account from you. And you KYC him again and store the data. But because you don't do anything with that data, not even compare it with existing records, you'll simply have another record, linking Mr. X to a new pair of keys. And of course, he does it again, and LE comes back knocking and they discover you gave a new set of keys to someone they've asked you to boot out ... pretty embarassing, to say the least.
So what do you need to do then? Well, at the very minimum, you need to have a process that takes the KYC data and does something with it which must result in a decision on whether that person gets permission to join the system (and receives a pair of keys) or not (typically if you "know that person" from a previous interaction and have already "rejected" her/him for whatever reason and in whatever way).
Permissioned blockchain system with an early check. Nothing prevents a very permissive policy for new users, but a check to spot "repeat offenders" remains necessary
Thus if you want your blockchain-based system to be compliant with the law, doing nothing more than "identifying the entrants" is not an option! You have to have a process that uses that identification data and leads to a decision to "accept" or "reject" the application, or the participation in the system's functioning. In other words, "it gives permission or not".
Can you still claim that your system is "permissionless"? Hardly so ..
Identification leads to a permissioned system
I'll start again by reminding the bitcoin whitepaper: "Nodes work all at once with little coordination. They do not need to be identified". Let's forget for a moment the above considerations about being law compliant. The question we are asking is: what would a blockchain-based system look like if users were identified; could such a system still be called "permissionless"?
I've explained that there is no academic nor commonly-accepted definition, so nothing prevents you from calling "permissionless" your system which identifies real-life persons and keeps a register linking "real life identities" with "key pairs". You can choose to do that for whatever purposes (say, marketing),
Yet for all practical purposes, that system is "permissioned".
Imagine for instance that you let the offender keep her/his keys and access to the transaction engine (so she can transact). You want to live up to your claim of being "permissionless", right? But you also want to avoid an offender from "doing it again", so you "censor" her/his activity at the level of the front-end, filtering and not displaying it.
This is very similar to how steem and hive treat abuse, using downvotes to lower reputation and then hiding the activity of accounts with low reputation.
Are steem and hive "permissioned" blockchains? I tend to say "no", because neither steem nor hive attempt to link a pair of keys (a "user") with a real life person. As long as the system stays pseudonymous, the same person can have a "bad account" with a low reputation and a reputable account. In that sense, the "permissioning" is done at the level of the "avatar" (of which there can be many), not of the person. However, both steem and hive adhere to the bitcoin ethos of not worrying too much about law compliance.
Back to our hypothetical law-abiding blockchain system which keeps a register associating real-life identities with key pairs BUT, because it wants to be "permissionless", only "punishes" offenders by "hiding" their transaction in the front end.
Blockchain system with a "late" check. You can call this "permissionless" if you wish ...
First observation: nothing of course prevents a third, unrelated person entering such a permissionless system and building a new decentralized front-end (permissionless innovation is the whole point, after all) which does not implement the filtering rule. So yes, your "official" front-end hides the operations of the "bad actor", but an independent front-end might choose to display them.
Second, if the "censoring" is done only ex-post, at the front-end level, and no "grant permission" process is implemented at the account creation time, a determined offender can of course resort to multiplying the number of her/his avatars, Sybil-like. Whether that is practical and worth the trouble (and hence likely to actually happen or not) will depend on the actual blockchain-system and its design goal, but suffice to say that this is an additional argument for implementing an upstream (rather than downstream) "filtering". Thus leading to "permission granting (or not)".
Conclusion
Law-abiding blockchain systems need to be able to identify the real-life person(s) transacting. The fact that Bitcoin, Ethereum and all the "permissionless" blockchains work with pseudonymous identities hampers their spread in the realm governed by laws. A blockchain system which strongly links the real-life users with their transactions can be called "permissionless" for marketing purposes, but it has to implement a decision tree which, for all practical purposes, is the logical equivalent of a "permissioning" process.