[ont.events] UW Theory Seminar, Mr. Sachse-Akerlind on "Anomalous Algorithms and Provable Complexity Bounds."

mwang@watmath.UUCP (mwang) (05/27/83)

     _D_E_P_A_R_T_M_E_N_T _O_F _C_O_M_P_U_T_E_R _S_C_I_E_N_C_E
     _U_N_I_V_E_R_S_I_T_Y _O_F _W_A_T_E_R_L_O_O
     _S_E_M_I_N_A_R _A_C_T_I_V_I_T_I_E_S

     _T_H_E_O_R_Y _S_E_M_I_N_A_R
                                     - Wednesday, June 1, 1983.

     Mr.  D.  Sachse-Akerlind  of  the  Australian  National
     University  will  speak  on  ``Anomalous Algorithms and
     Provable Complexity Bounds.''

     TIME:                3.30 PM

     ROOM:              MC 5158

     ABSTRACT

     Computational complexity measures are considered within
     a formal axiomatic system S.  We show that for any par-
     tial recursive function f, what can be formally  proved
     (within  S)  about  the  complexity of computing f will
     vary greatly depending on the algorithm initially  used
     to  define f.  We illustrate this result using the TIME
     and TAPE measures on the Turing machines.

                        May 27, 1983