Re: The Liar's Sentence and Nontermination

On Jun 3, 7:25 pm, stevendaryl3...@xxxxxxxxx (Daryl McCullough) wrote:
Marshall says...
On Jun 2, 4:05 pm, stevendaryl3...@xxxxxxxxx (Daryl McCullough) wrote:
Marshall says...

However, truth is not in general decidable by an algorithm.
That's what Turing's unsolvability of the halting problem
shows: For statements of the form "Program P does not halt
on input I", there is no foolproof algorithm for assigning
truth values. But we know what such sentences *mean*. So
meaning is not the same thing as agreeing on a computational
model.

That last sentence doesn't follow from the ones that come before.

In particular, if we are speaking of programs, what they mean is
exactly and completely dependent on which computational model
we are speaking of. What it *means* to say it halts is thus a
statement about the evaluation of the program within an
*agreed upon* computational model.
That we cannot evaluate the full behavior of programs in general
ahead of time does not entail that they have meaning that is
somehow detached or outside of their evaluation semantics.

But my point is that there is no terminating procedure to
evaluate the truth of a sentence of the form "Program
P never halts on input I".

Right.


Therefore, we can't say anything
about the meaningfulness of a sentence based on the fact
that our attempts to evaluate its truth never halts.

If our attempts to evaluate the truth of a sentence
***never*** halt, then we certainly can say something
about the meaningfulness of a sentence: since its
evaluation is nonterminating, it doesn't have a truth
value. Like the liar sentence.

However, I expect that you didn't really mean to
use the word "never". Unfortunately (assuming I'm
correct about that) I cannot tell what you might have
meant to say.


Sure. That is, as you say, a consequence of the
unsolvability of the halting problem, and we should
certainly *not* make that assumption. Frankly,
I don't think that the addition of the evaluator function
T into the argument does anything except obfuscate
the issues.

I thought *you* were the one who brought up computational
models for truth. What does it mean, if it doesn't mean
a computation that decides whether something is true or not?

No, that's what I mean: a computation that decided whether
something is true or not. However, as you pointed out
earlier, that statement is tautological. Computing equals
deciding.

However, we might use direct evaluation in one context
and meta-evaluation (aka abstract interpretation) in
another. It's important to distinguish them, and it seems
to me that your arguments sometimes don't do enough
of that.

Also it's important to note that meta-evaluation is
itself evaluation, just in a meta-computational-model.
It's not a different *kind* of thing.


Neither do I think that techniques such
as "will not return true" to try to capture both false
and not-halt behavior illuminate anything either, since
we already well know that termination isn't generally
capturable.

In fact, trying to do all of this in natural language is
the worst mistake of all, because it is biting off more
that anyone can chew.

What does natural language have to do with it?

The liar's sentence is usually presented in English,
not in any formal language. I've been saying that
that makes the whole situation less clear.


The point I was trying to make in the original post
is that the liar's sentence *doesn't* have anything
interesting to tell us that we can't already get a
better, clearer handle on from studying computational
models directly. This was not true in Epimenedes's
day, nor even in 1900, but it's certainly true today.

I agree that the Liar's Paradox is no longer a mystery,
but I don't agree that nontermination has anything to
do with it, or that computational models have anything
to do with it. Well, they might, if I knew what you meant
by "computational model".

Roughly, a set of values, possibly typed, and a set of
primitive operations, and the semantics for each of
the primitives. "Model" in the sense of "Concepts, Techniques
and Models of Computer Programming" by van Roy.
A Turing Machine is a computational model. Some
people use the term "programming paradigm."

(Not being a logician by training, I sometimes have
trouble speaking the native lingo here, for which
I apologize.)

[snip]

And I assert that the liar's sentence is better thought
of formally,

Yes, I agree. Tarski's theorem about the undefinability
of truth says all that you need to know about it.

You are talking about this?

http://en.wikipedia.org/wiki/Tarski%27s_Indefinablity_Theorem

It seems to me that that is pretty much what I was saying
in my last post; at the very least the two are entirely consistent.


because that makes it obvious that it's
just nontermination dressed up in a fancy outfit

It doesn't have anything to do with nontermination.
"Termination" is only relevant if you are running
a program (or more generally, carrying out a process).

If you are trying to "decide" something, in either the
layman's sense, or in the strict mathematical-logic
sense, you are carrying out a process. If you are
trying to assign meaning to something, then you
are carrying out a process. Deciding equals computing.

What exactly is your aversion to describing semantics
in computational terms? How do you conceptualize
the assignment of meaning to sentences in a way
that avoids any hint of carrying out a process?
Do you also object to the idea that, for example,
verifying a proof is a form of computation?


The Liar Sentence is not a process, it is a string
of characters.

Oh dear. Really? You're going that way?

Well, if it's a string of characters merely, then it
certainly raises no philosophical issues. After all,
my cat walking across my keyboard generates a
string of characters, and there's no conundrum in
that, unless it's how to get the cat off my desk
without getting scratched.

But I would say that it's more accurate to say that
the liar's sentence is more than just a string of
characters, in that it becomes interesting when
viewed as a sentence in English, and we perform,
in our heads, computations to attempt to assign
it meaning.


You are *interpreting* the Liar Paradox as a rewrite
rule of some sort. Yes, as a rewrite rule, it is non-terminating.
But why in the world do you want to do that? It's *not* a rewrite
rule. It's not a line of a program.

It's a sentence in a language. Whether or not it's a rewrite
rule per se, if we're going to do any *formal* analysis of
it, we have to do so in the context of a *formal* methodology
of whatever nature, whether that be a rewrite system,
a Turing machine, or something else.

But one thing is sure: whatever methodology we choose
will be a form of computation. Knowing that, it makes
more sense to my way of thinking to just leap directly
to computational models and study them, rather than
fuss around with English, which is just going to obfuscate
any issues of incompleteness or nontermination or
strictness analysis or abstract interpretation or whatever.


Marshall
.

Relevant Pages

  • Re: X = Z
    ... travel a path and return to its beginning, a goal of mathematics is ... that have otherwise generally canonical meaning. ... Fashion has nothing to do with truth. ... appear on the subject of 'primes' above and below mine, ...
    (sci.math)
  • Re: Universality as warrant for relative truth value
    ... term means to people and that might have the odor of truth value. ... I do see meaning as ... If knowledge is an ability, as I defined it, then "truthful ... Abilities are neither truthful nor ...
    (sci.philosophy.meta)
  • Re: Universality as warrant for relative truth value
    ... 99% of all scientists would agree. ... not to convey conventional truth. ... To ascertain the generally held meaning of words we turn to ... As I've indicated, I don't believe correspondence ...
    (sci.philosophy.meta)
  • Re: Definition of truth
    ... and that's only of the "true" truth. ... behaviors are well established and documented in Physics. ... if you wish to put specific meaning on certains ... Yeah, probably I should have, but didn't know at the time that English ...
    (rec.skiing.alpine)
  • Re: Godels theorem is invalid?
    ... > Then his definition of truth simply does not match the classical one. ... I am not saying that I agree with Tennant's arguments (which are based ... What exactly do you mean by the assertion ... > NOT ONE IOTA OF IMPACT on the TRUTH or the MEANING ...
    (sci.logic)
Quantcast