2 ms·
> A unary predicate whose argument ranges over TM may have such a subset as its extension. Yes, but now we can talk about a specific logic/language, and now it
by pron 10y ago
> A unary predicate whose argument ranges over TM may have such a subset as its extension.
Yes, but now we can talk about a specific logic/language, and now it matters exactly how the NDTM is expressed syntactically. E.g. in TLA (and LTL, or CTL for that matter) `[](x ∈ {1,2,3})` means "the variable x in the program is always in 1..3", or (semantically) "the set of all TMs where x is always in 1..3". x is a name given to a variable in an infinite set of variables defining the abstract machine's state (i.e. a state in TLA is defined to be an assignment to the infinite set to all possible variables), and the existence of the machine (or a Kripke structure, if you will) is implied. If you only supply a proposition on variable x, it means that all other (infinite set of) variables can take any value.
You can read about TLA/TLA+ in one of the links I provided to get the specifics (it's extremely easy to pick up, BTW). In any event, a proposition in TLA can be thought of as a predicate over a(n implicit) TM. You may also find this short note by Lamport about the history of TLA/+ (and in particular the unification of temporal-logic propositions and programs) interesting[1].
> Two syntactically different predicates may have the same extension.
True, I didn't say the syntactic representation is unique. Also, in TLA it's no longer just a predicate but any proposition.
> There oughtn't even be the possibility of conflating them.
I am not conflating them, and I'm not saying a proof is formally a proposition. I'm saying that in intuitionistic logic, a proof (especially of an existential quantification) may be also interpreted as a more precise/limited proposition. But this is just a vague notion, and it could be completely wrong (even if I were able to communicate it clearly), so I see no point in debating this.
[1]: http://research.microsoft.com/en-us/um/people/lamport/pubs/commentary-web.pdf http://research.microsoft.com/en-us/um/people/lamport/pubs/c...