Russel,
I just went to look at the paper "Hierarchies of generalized
Kolmogorov complexities and nonenumerable universal measures
computable in the limit"-- to find a quote showing that GTMs were a
generalization of Turing Machines rather then a restriction. I found
such a quote as soon as page 2:
"This constructive notion of describability is less restrictive then
the traditional notion of computability, mainly because we do not
insist on the existence of a halting program that computes an upper
bound of the convergence time [...]"
But, as soon as the abstract, I found:
"Among other things we show [...] that there is no universal
approximable distribution [...]"
So scratch that example! I now remember reading that when I first
encountered the paper, but obviously I did not pay much attention or I
would have recalled it sooner... I'll look over the proof again and
try to figure out whether it applies to even more general models (like
priors based on arithmetic describability or analytic describability).
--Abram
On Thu, Nov 27, 2008 at 5:22 PM, Russell Standish <lists.domain.name.hidden> wrote:
>
> On Thu, Nov 27, 2008 at 02:40:04PM -0500, Abram Demski wrote:
>>
>> Russel,
>>
>> Hmm, can't we simply turn any coding into a prefix-free-coding by
>> prefacing each code for a GTM with a number of 1s indicating the
>> length of the following description, and then a 0 signaling the
>> beginning of the actual description? I am not especially familiar with
>> the prefix issue, so please forgive me if I am wrong...
>
> Sure - but you also need to change the machine to recognise your code.
>
>>
>> Also, I do not understand why there would be reason to suspect that
>> the probability distribution, once properly defined, would turn out to
>> be equivalent to the S-L prior. GTMs can formally represent more
>> things than TMs, so why would those things not end up in the
>> probability distribution?
>>
>> --Abram Demski
>>
>
> Its been a while since I read Schmidhuber's papers, but I thought he
> was talking about machines that continuosly updated their output, but
> would eventually converge (ie for each bit i of the output, there was
> a time t_i after which that bit would not change).
>
> This seems to be a restriction on the notion of Turing machine to me,
> but not as restrictive as a prefix machine.
>
> --
>
> ----------------------------------------------------------------------------
> A/Prof Russell Standish Phone 0425 253119 (mobile)
> Mathematics
> UNSW SYDNEY 2052 hpcoder.domain.name.hidden
> Australia http://www.hpcoders.com.au
> ----------------------------------------------------------------------------
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list+unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Thu Nov 27 2008 - 17:47:23 PST