On 5/31/2020 4:32 PM, Bruce Kellett wrote:
On Mon, Jun 1, 2020 at 9:05 AM 'Brent Meeker' via Everything List
<everything-list@googlegroups.com
<mailto:everything-list@googlegroups.com>> wrote:
On 5/31/2020 3:49 PM, Bruce Kellett wrote:
On Mon, Jun 1, 2020 at 8:31 AM 'Brent Meeker' via Everything List
<everything-list@googlegroups.com
<mailto:everything-list@googlegroups.com>> wrote:
On 5/31/2020 3:23 PM, Bruce Kellett wrote:
On Mon, Jun 1, 2020 at 3:12 AM 'Brent Meeker' via Everything
List <everything-list@googlegroups.com
<mailto:everything-list@googlegroups.com>> wrote:
On 5/30/2020 10:44 PM, Bruce Kellett wrote:
On Sun, May 31, 2020 at 2:26 AM Bruno Marchal
<marc...@ulb.ac.be <mailto:marc...@ulb.ac.be>> wrote:
Let us write f_n for the function from N to N
computed by nth expression.
Now, the function g defined by g(n) = f_n(n) + 1 is
computable, and is defined on all N. So it is a
computable function from N to N. It is computable
because it each f_n is computable, “+ 1” is
computable, and, vy our hypothesis it get all and
only all computable functions from N to N.
But then, g has have itself an expression in that
universal language, of course. There there is a
number k such that g = f_k. OK?
But then we get that g_k, applied to k has to give
f_k(k), as g = f_k, and f_k(k) + 1, by definition
of g.
That is a fairly elementary blunder. g_k applied to k,
g_k(k) = f_n(k)+1, by definition of g_k. You do not get
to change the function from f_n to f_k in the
expression. It is only the argument that changes: in
other words, f_n(n) becomes f_n(k). So you are talking
nonsense.
No, I think that's OK. It's a straight substitution
n->k. The trick is that g(n) is not some well defined
specific function because n has infinite range. So none
of this works in a finite world. But it's not
surprising that there is incompleteness in an infinite
theory.
Yes, I had misunderstood what g(n) was supposed to be -- it
is simply a representation of the diagonal elements of the
array, plus 1. But Bruno's attempt to use the diagonal
argument here fails, because he has to show that f_n(n)+1
is not contained in the infinite list. He has failed to do this.
All computable functions are in the list ex hypothesi.
That is what the diagonal argument is all about: you hypothesize
that all bit strings (for example) are in your infinite list.
Then you flip the diagonal bit of each string and form a new
string from all the diagonal elements. And lo, that new string is
not in the initial list. Therefore your hypothesis that all bit
strings are in the list is disproven.
Bruno has attempted toride to glory on this argument, and has
failed miserably!
That's a general problem with reductio arguments. When you get to
end you don't know which premise was wrong. Bruno, isn't changing
the hypothetical list though, so he's saying the premise that you
can order the total functions is wrong. You can order the
functions (say lexigraphically) but you can't know which are total.
ISTM the result, that there's an incompleteness theorem for the
set of all functions, is quite intuitive. But Bruno seems to be
saying this is all finitist because he doesn't assum and axiom of
infinity. Yet the "diagonalization" doesn't work in a finite world.
Take all bit strings of length N (finite) and apply the diagonal
argument. The string resulting from putting all the flipped diagonal
bits together is not in the original list, contradicting the
assumption that the list is complete.
If N is finite then there are only 2^N possible bit strings and the list
will include all of them. So when you flip a bit in each one you get
the same list, just reordered.
Brent
Of course, the list of all strings of length N contains more than N
elements, so the diagonal argument does not apply. The set of all
strings of infinite length is certainly infinite, so one might work
the diagonal argument there -- if one doesn't worry too much about
cardinality issues......
I think Bruno should rephrase his argument -- it might be sensible,
but as presented it was clearly invalid.
Bruce
--
You received this message because you are subscribed to the Google
Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send
an email to everything-list+unsubscr...@googlegroups.com
<mailto:everything-list+unsubscr...@googlegroups.com>.
To view this discussion on the web visit
https://groups.google.com/d/msgid/everything-list/CAFxXSLRM0SwFN3ujhJ7Av0MAV5aR98Gma4uA6NWg-5D8DP%2B7RA%40mail.gmail.com
<https://groups.google.com/d/msgid/everything-list/CAFxXSLRM0SwFN3ujhJ7Av0MAV5aR98Gma4uA6NWg-5D8DP%2B7RA%40mail.gmail.com?utm_medium=email&utm_source=footer>.
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/everything-list/929dd9a8-886d-b387-6eb4-1f7d511fb328%40verizon.net.
