help with problems on computability needed!!

Hi all, I was wondering if anyone would be able to help me with the
following problems. I'm really bad at these... that's why I have to
retake this course on computational theory and complexity... I could
use any help I can get!

First question:
Consider a table whose rows are labelled with TMs, whose columns are
labelled with TM encodings, and where the entry at (Mi, <Mj>) contains
a 1 if Mi accepts <Mj> in at most |<Mj>|+t steps, and a 0 otherwise.
Use a diagonalization argument to show that for every t, there exists a
language L which is decidable in general, but not decidable with lag t.
We say that a language L is decidable with lag t if there exists a TM M
deciding L, which also satifies the requirement that on every input w,
M halts in at most |w| + t steps.

This second question is more tricky, I think:
Let M1,M2, . . . ,Mi, . . . be the list of all TMs in lexicographical
order.
For every positive integer k, define f(k) to be the index in the above
list of the k-th TM M such that L(M) = NULL. Formally,

f(k) = max{i : there exists J, which is a subset of {1 . . . i - 1}
such that (|J| = k - 1 and for all j belonging to {1 . . . i - 1},
L(Mj) = NULL iff j belongs to J)}

Notice that f is well defined for every k, since there are infinitely
many TMs M with L(M) = NULL. For example, if L(M2) = L(M5) = NULL and
L(M1),L(M3),L(M4) are not empty, then f(1) = 2 and f(2) = 5.
Prove that f is not computable.

I hope these aren't too difficult, although they are making me scratch
my head! Thanks for all your help, guys!!!

.

Relevant Pages

  • Re: Ruby Vs. Java
    ... have any of you played any kind MORPG? ... lag and I want little of it as possible. ... Programmers should write clear code (in a clear language) and never try ... have a project that gives you a reason to start learning a language and you will get farther with the language at least! ...
    (comp.lang.ruby)
  • Re: Custom dictionary is not available (not Spanish!)
    ... font, bold, italics, etc., so the first question is "Where did the content ... have applied a Style that includes a Language attribute. ... Dictionaries menu, it opens it, so I know Word can find it, it exists, and ... Custom Dictionaries in Word Help. ...
    (microsoft.public.mac.office.word)
  • Re: Need help
    ... If English is not your first ... your own language. ... My First question was not answered. ... in the work book how can I do that the function that were available is ...
    (microsoft.public.excel.misc)
  • Re: TCL cant do as much as Perl
    ... in Computational Theory it does not. ... I've never heard the question "which is a better language" asked outside of Theory of Computation college classes where the appropriate answer was "they're both provably identical, ... Darren New / San Diego, CA, USA Indications you're in trouble, #37: Your accountant charges you interest for not paying bills for which you already have the canceled checks back. ...
    (comp.lang.tcl)
  • Re: Is it possible to accomplish this using Homomorphisms?
    ... I'm relatively new to the area of Computational Theory, ... I have a problem where L is a Regular Language which is defined over the set ... Homomorphisms, and if so, what would the Homomorphisms be for each of the ... can simply intersect L with the regular ...
    (sci.math)