Solution to Alan Turing’s 1936 Halting Problem [ unsatisfiability (linking syntax to semantics) ]

peteolcott

2018-11-23 19:51:14 UTC

[snip a bunch of nonsense]
Not needed. xkcd already solved it: https://xkcd.com/1266/
EFQ

So I take is that you are clueless about the theory of computation.
It turns out the Mendelson's section 2.2 First-order languages
and their interpretations. Satisfiability and Truth. Models
Is the same sort of thing that I have been saying all along.
After I carefully study this material I will be able to explain
the same ideas that I have always been saying, yet using much
more conventional terminology.

My key insights relate most directly to the notion of satisfiability.
(1) Tarski Undefinability Theorem.
(2) Gödel's 1931 Incompleteness Theorem.

Can't be. If you read 2.2 you'll find that satisfiability is a semantic notion, but Gödel's 1931 incompleteness theorem is wholly syntactic.

Godel already linked syntax to semantics Introduction page 2
http://jacqkrol.x10.mx/assets/articles/godel-1931.pdf
The chain of symbolic manipulations in the calculus corresponds to
and represents the chain of deductions in the deductive system.
And as I have been saying all along semantics can be exhaustively
specified syntactically. Rudolf Carnap showed how to do this with his
"Meaning Postulates" back in 1952.
As soon as I acquire the meaning of the conventional notion of
satisfaction I will be able to show this.

In order to define Satisfiability directly within an object language
without the need for a separate metalanguage interpretation the object
language specifies relations between finite strings instead of merely
relations between expressions of language.
∀x Bachelor(x) → ~Married(x)

Your attitude towards brackets is quite cavalier.

You mean parenthesis: () or brackets:[] ?

∀x Bachelor(x) → ~Married(x)
and I objected to it. So re-read it and try to spot what is wrong with it.

2. Meaning Postulates
Our discussion refers to a semantical language-system L of the
following kind. L contains the customary connectives, individual
variables with quantifiers, and as descriptive signs individual
constants ('a,' 'b,' etc.) and primitive descriptive predicates
(among them 'B,' 'M,' 'R,' and 'Bl' for the properties Bachelor,
Married, Raven, and Black, respectively). The following statements
(3) 'Bla ∨ ~Bla'
(4) 'Bb ⊃ ~Mb'
He said that he used quantifiers and did not even actually use them at all.

Then why did you write
∀x Bachelor(x) → ~Married(x)
? I'm looking more than halfway down the third page of /Meaning postulates/ and I see
(x)(B(x) -> ~M(x))
(labelled P_1) except that Carnap uses the horseshoe where I use the arrow. Let's avoid troublesome words such as 'bracket' and 'parenthesis', and note that he punctuated his formula correctly.

You have to read all the text where he defines that B means
Bachelor and M mean Married.
My version more self-evidently clear without having to hunt around.

http://intrologic.stanford.edu/glossary/unsatisfiability_theorem.html
The Unsatisfiability Theorem states that Δ ⊨ φ if and only if Δ ∪
{¬φ} is unsatisfiable. In other words, if a set Δ of sentences
logically entails a sentence φ, then Δ together with the negation
of φ must be unsatisfiable, and vice versa. The theorem is useful
because it assure us that, if we want to determine whether or not
Δ ⊨ φ, all we need to do is to determine whether or not Δ ∪ {¬φ}
is unsatisfiable, which is often an easier task.

http://intrologic.stanford.edu/notes/chapter_03.html#section_03_04

3.4 Logical Entailment
We say that a sentence φ logically entails a sentence ψ (written φ ⊨ ψ)
if and only if every truth assignment that satisfies φ also satisfies ψ.
More generally, we say that a set of sentences Δ logically entails a
sentence ψ (written Δ ⊨ ψ) if and only if every truth assignment that
satisfies all of the sentences in Δ also satisfies ψ.

For example, the sentence p logically entails the sentence (p ∨ q).
Since a disjunction is true whenever one of its disjuncts is true,
then (p ∨ q) must be true whenever p is true. On the other hand,
the sentence p does not logically entail (p ∧ q). A conjunction is
true if and only if both of its conjuncts are true, and q may be false.
Of course, any set of sentences containing both p and q does logically
entail (p ∧ q).