R.E sets, Three valued logic and diagonal argument.
in [Logic]
|
Prev: New maths formula, maths 2&3^(a->38^7839_88)-34 MATHS 3+4=4 sin(x)=oo
Next: since Physics has no numbers beyond 10^500, then that should be infinity for mathematics #621 Correcting Math
From: apoorv on 2 Jul 2010 06:55 If we take a non total Turing machine and run it over all possible inputs on its alphabet, (in a time sharing manner, so that it runs on input 1 for 1 minute, on input1 for 1 minute and on input 2 for 2 minutes and so on) then , at any given time, we have 3 catalogs: 1) Inputs that have been accepted 2) Inputs that have been rejected 3) Inputs about which we do not know. As the computation proceeds, members from catalog 3 move to catalog 1 or 2, but at no finite time is the catalog 3 empty. In other words, at all finite times, given an arbitrary input, it either is (to our knowledge) in the set accepted by the TM, or in the set rejected by the TM or we cannot say. Thus, given a number x and a R.E set A represented by some TM, at all finite times, we can either have that x belongs to A or is not in A or we cannot say. Thus, would it be that the appropriate logic to use is a three valued logic with the logical values T (true), F (false) and I (indeterminate)? We can also stipulate that ~P has the value I iff P has the value I; also T and I is I, T or I is T, F and I is F, F or I is I, I and/or I is I. Proof by contradiction is not available as P and ~P will return the value I if P has the value I. Consequently, no diagonal argument gets through if any value in the (square)array is I. Why is two valued logic accepted as the norm though it implicitly implies complete knowledge (which is not available at any finite time) as against 3 valued logic, which can explicitly incorporate insufficiency of knowledge in its framework? -apoorv
From: George Greene on 2 Jul 2010 10:44 On Jul 2, 6:55 am, apoorv <sudhir...(a)hotmail.com> wrote: > Why is two valued logic accepted as the norm though it implicitly > implies complete knowledge (which is not available at any finite time) The whole notion of time here is INappropriate. Things have the value they have AT ALL times, REGARDLESS of whether your machine has (as yet) gotten Or Not Gotten around to confirming/computing the value. The value was what it was BEFORE the machine noticed that. > as against 3 valued logic, which can explicitly incorporate > insufficiency of knowledge in its framework? No, it can't. Your treatment here cannot distinguish between "not known yet because the machine hasn't computed it yet" and "not known yet because IT WILL NEVER be known", e.g. because it is (necessarily) undefined. More to the point, there simply is no distinction between 3-valued and 2-valued logic. If you have 3 values then you can just represent them with 2 bits, i.e., with 2 copies of things that are 2-valued. So 2 values is all you need.
From: George Greene on 2 Jul 2010 10:46 On Jul 2, 6:55 am, apoorv <sudhir...(a)hotmail.com> wrote: > Thus, would it be that the appropriate logic to use is > a three valued logic with the logical values T (true), F (false) and I > (indeterminate)? Indeterminate or "undefined". If you are dealing with the class of partial recursive functions (e.g. tangent or f(x)=1/x) then this is natural, but it it's not just TRUTH-values that can be undefined; it's ANY value of ANY function. It probably turns out to be easier to let the TRUTH-values remain bivalent and let the OTHER values be undefined; you can reason about partial functions in 2-valued logic.
From: Frederick Williams on 2 Jul 2010 11:12 apoorv wrote: > > If we take [...] Kleene uses three-valued logic to discuss partial predicates. -- I can't go on, I'll go on.
From: apoorv on 9 Jul 2010 02:24
On Jul 2, 7:44 pm, George Greene <gree...(a)email.unc.edu> wrote: > On Jul 2, 6:55 am, apoorv <sudhir...(a)hotmail.com> wrote: > > > Why is two valued logic accepted as the norm though it implicitly > > implies complete knowledge (which is not available at any finite time) > > The whole notion of time here is INappropriate. > Things have the value they have AT ALL times, REGARDLESS > of whether your machine has (as yet) gotten Or Not Gotten around > to confirming/computing the value. The value was what it was BEFORE > the machine noticed that. We can translate at no finite time as there is no proof and at any finite time as after any n steps in the computation. If we take a set A defined by {x: phi x}, then whether or not a given a is in A may not be known a priori; a computation is needed to check whether phi(a) holds or not. For a R.E set A, there is some c for which there is no proof that c is in A and there is no proof that c is not in A. Now, we consider the diagonal argument. We let the subset Ai of N be represented by the binary sequence a_j, so that a_jk=1 if k is in Ai and 0 otherwise. Now, there is some R.E set Aj represented by a_j such that there is no proof that a_jj is 1 and there is no proof that a_jj is 0. If d is the diagonal sequence, then there is no proof that d_j is 1 and there is no proof that d_j is 0. Similarly, if D is the anti- diagonal sequence, there is no proof that D_j is 0 and there is no proof that D_j is 1. Let us consider a given number b. We can have no proof that b_j=d_j . Therefore, we can have no proof that b =d, i.e the given number is the diagonal. Similarly, we can have no proof that b=D. Thus, given a number b , we can have a proof that it is not the anti- diagonal, but we can have no proof that it is indeed the anti- diagonal. In other words, given any number, we can never prove that it is not on the list. Similarly, given a number n, we can have a proof that it is not the godel number (for PA) but we can never have a proof that it is the godel number (for PA). -apoorv |