Re: OPPOSITE OF all coin sequences are computable to infinite length ?
From: Timothy Little (tim-via-n.i.net_at_little-possums.net)
Date: 01/07/05
- Next message: Charlie-Boo: "Re: Deep Thoughts # 17: Liar Paradox is a Formal Metamathematical Theorem"
- Previous message: poopdeville_at_gmail.com: "Re: x(f,a) -> y(f,a) XOR z(f,a)"
- In reply to: |-|erc: "Re: OPPOSITE OF all coin sequences are computable to infinite length ?"
- Next in thread: John Savard: "Re: OPPOSITE OF all coin sequences are computable to infinite length ?"
- Messages sorted by: [ date ] [ thread ]
Date: 7 Jan 2005 22:03:17 GMT
|-|erc wrote:
>> |-|erc wrote:
>> > "There is a maximum to the number of coins in any given oo coin
>> > sequence, that can be computed" [1]
> Can you state the correct negative form of proposition 1?
"There is no maximum to the number of coins in any given oo coin
sequence, that can be computed".
> but I've already told you they are the same, since they are both true.
You've told me, but you haven't proved it. You've only said that a
true statement "suggests" it.
> if you find a valid example of a sequence in one not the other let
> me know.
Let <T_n> be an enumeration of all Turing machines (equivalently,
programs). Let <L_n> be an enumeration of all finite tape states
(equivalently, inputs and outputs to the programs). Let
P_n:N -> N union {0} be a function defined by the output of the n'th
Turing machine started with the k'th input tape state. If it halts,
let P_n(k) be the index of the output tape state, otherwise let
P_n(k) = 0.
Define a sequence <a_n> by a_n = P_n(n) + 1.
Recall the two propositions:
> (A) "For any sequence <a_n>, there exists a program P, such that for
> any natural number N, P(n) = a_n for all n < N"
This one is false, with the sequence defined above as a counter
example. Suppose there exists such a program P. Then it has an index
into the enumeration, call it n_P. Choose N = n_P + 1 (since the
statement says it is true for all N), and choose n = n_P (since the
statement says it is true for all n < N). Then a_n = P(n) + 1, by
construction of <a_n>. However, the behaviour of program P when
presented with input n is given by P(n), so P(n) != a_n.
> (B) "For any sequence <a_n>, for any natural number N, there exists
> a program P, such that P(n) = a_n for all n < N"
This one is true. The sequence defined above is not a counterexample,
since for proposition (B), P is allowed to vary with the choice of N.
For proposition (A), it is not.
Swapping the order of the quantifiers makes all the difference.
- Tim
- Next message: Charlie-Boo: "Re: Deep Thoughts # 17: Liar Paradox is a Formal Metamathematical Theorem"
- Previous message: poopdeville_at_gmail.com: "Re: x(f,a) -> y(f,a) XOR z(f,a)"
- In reply to: |-|erc: "Re: OPPOSITE OF all coin sequences are computable to infinite length ?"
- Next in thread: John Savard: "Re: OPPOSITE OF all coin sequences are computable to infinite length ?"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
