Re: OPPOSITE OF all coin sequences are computable to infinite length ?
From: |-|erc (h_at_r.c)
Date: 01/08/05
- Next message: |-|erc: "Re: Towards disproof of Omega"
- Previous message: J: "Re: abundance of irrationals"
- In reply to: Timothy Little: "Re: OPPOSITE OF all coin sequences are computable to infinite length ?"
- Next in thread: Timothy Little: "Re: OPPOSITE OF all coin sequences are computable to infinite length ?"
- Reply: Timothy Little: "Re: OPPOSITE OF all coin sequences are computable to infinite length ?"
- Messages sorted by: [ date ] [ thread ]
Date: Sat, 8 Jan 2005 12:14:11 +1000
"Timothy Little" <tim-via-n.i.net@little-possums.net> wrote
> |-|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".
Since
"There is no maximum to the number of integers"
means
"There are infinite number of integers"
can you rephrase your proposition into the above form?
>
>
> > 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.
P is a function that is emulatable by some UTM.
For the sequence to be possible it must be emulatable by some function Q.
Assume : Q(n) = P_n(n) + 1
Q(q) = P_q(q) + 1
Q(q) = Q(q) + 1 (if Q(q) halts, else 0)
the assumption of such a sequence is a contradiction.
>
> 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
yeah, it sells the text books.
Herc
- Next message: |-|erc: "Re: Towards disproof of Omega"
- Previous message: J: "Re: abundance of irrationals"
- In reply to: Timothy Little: "Re: OPPOSITE OF all coin sequences are computable to infinite length ?"
- Next in thread: Timothy Little: "Re: OPPOSITE OF all coin sequences are computable to infinite length ?"
- Reply: Timothy Little: "Re: OPPOSITE OF all coin sequences are computable to infinite length ?"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
