f



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!!!

0
ahtwong (2)
6/16/2005 3:12:34 AM
comp.theory 5139 articles. 1 followers. marty.musatov (1143) is leader. Post Follow

1 Replies
763 Views

Similar Articles

[PageSpeed] 30

Hey, that's quite a mouthful. But you're registered to a course, right?
So you are *entitled* for help from the most qualified person - your
prof.
There are too many students who are shy of approaching their
professors,
who can actually turn out to be quite willing to help. Try it!
There is hardly another way to overcome the difficulties so common with
the theory courses.

0
sixholes (1)
6/17/2005 10:13:21 PM
Reply:

Similar Artilces:

need to compute this problem having problems with how to start this problem help need urgently
Let   U[0; 2theta] be a uniform random variable from the interval [0; 2theta] and let A  Exp(1) be exponentially distributed with mean 1. Assume  and A independent. Compute the mean mX(t) =E[X(t)] and autocorrelation RX(s; t) = E[X(s)X(t)] of the phase-shifted sinusoid.X(t) = A*  cos(t +theta ): State also if X(t) is Wide Sense Stationary (WSS). plot 10 realisations of X(t) plotR(s-t,0)as a function of s-t "pramod kumar" <pramod.kilu@gmail.com> wrote in message <jpapso$44b$1@newscl01ah.mathworks.com>... > Let   U[0; 2theta] be a uniform random variable ...

help me in this computer theory problem
Problem 2 (5 points) Write an algorithm that inputs an integer array A[1::n] and an odd integer number k, and determines whether k can be represented as the sum of two elements of the array. If k is the sum of two elements of A[1::n], your algorithm should return true; else, it should return false. Its running time should be O(n  lg n). Please help me in this problem Savior wrote: > Problem 2 (5 points) > Write an algorithm that inputs an integer array A[1::n] and an odd > integer number k, and determines whether k can be represented as the > sum of two elements of the arra...

Need help with computer problem
Here's my problem: Sometimes webpages open fine and other times they won't open. At the bottom of the screen it will say "Done" but it will only be a blank white window. When I am able to get a webpage open, there are times when I can't open a link on that page; it will only open a blank window. I can't open links sent to me via email. To try to end run around that problem, I copy the URL for the link and try to paste it into the address space but the pull down menu won't give me the option to paste. Sometimes when I try to open a link in my email it even locks up...

Strange problem with my computer: need help !!
Hi ! I have a Athlon 1.2G, 256Mg Ram on Windows ME. I used a compressed gas duster to clean all internal parts of my computer (fans, motherboard, cd-rom, etc..). Since that event, I've got problem to boot on my computer. When the computer is cold, it boot and freeze 10 sec. after. The monitor's shut down, the disk drive light get always on but the drive don't work, everything on the keyboard or on the mouse is "close"... and I can't reset from the front switch (I must close the power supply). I must do that "game" up to 8 times before it runs correctl...

Help needed on this 857W config. Repost to be clearer what the problems are and the help needed
Hi, Please see below config for my 857W. The basic topology is that I have one cisco857W and various servers and internal wired and wireless clients on the 192.168.0.0 255.255.255.0 network. There are a number of services running on the local lan, DNS and DHCP is also provided by a local server on the same subnet as the router. The 857W router sits on address 192.168.0.254 and needs to act as the local gateway for both wired and wireless clients. With this config booted on the router, the wireless clients can connect and authenticate and get allocated the correct DHCP information and ...

copy of some problems from Sipser Theory of Computation needed
this is for a class I am taking. I ordered my copy of this text from bn.com but, unfortunately, my order has been delayed. Would it be possible for anyone with a scanner or a quick typing hand to send me a copy of the chapter 0 problems: 0.10, 0.11, 0.12 . I e-mailed some people in my class but thought I'd cast the net a little wider :) I am unable to get to campus in the meantime and just copy it from someone else. argghhh. I know it is a lot to ask but if anyone is feeling particularily charitable I'd appreciate it! oh, and just in case I was ambigous I meant this text http://www.c...

Need help with help need
Friends and wormbots: I am looking for some intrepid souls to try out and comment on a perl script I wrote. (What, perl in SAS-L and it's not David Cassell ?) The script takes the SAS help files apart and does some analysis (orphans, linkrot and duplicates) and inserts back links. What do back links do ? It ensures every page in the help system has a link to every page that links to it. (Actually only the the subset of the help system represented by the modules you choose to play with [there are over 140 help modules]) 1,000 lines of perl that sprouted out of a two line seed (or should...

Help: Need help identifying the cause of this problem....
Hi all, The symptoms: When connected to the internet my desktop runs at 100% cpu usage and 100% network usage. There are no idications of which process is actually using 100% CPU. Whatever is wrong with my desktop is now wrong with my laptop - they both run winxp and are connected to the same router. If I disconnect the router from the cable modem both computers continue to run at 100%/100% - disconnect the network cables - or disable the connection - and the problem goes away. Right now I am writing this on my wife's mac - it is also connected to router but works just fine. There is no ...

yahoo.com.au mail problems problems problems
Hello, in the last month I encountered big problems to read mail from yahoo.com.au server. There is no chance to connect to e-mail /www based server. Having logged to www.yahoo.com.au mail window doesn't open waiting for an image from au.adserver.yahoo.com server is that server dead, making reading mail completely impossible ? Ping says, that server is unreachable. What can I do to make things better as in previous months ? Ple ...

Need help with a problem
Hello, I�ve the following problem: Given: y = f(x) + normcdf(g(x))+normcdf(h(x)) where y is given and x is the variable I want to get. f,g and h are functions of x and normcdf(x) is the integral of the N(0,1)-distribution. It would be very nice if sb could help me finding x. Thx Jan In article <ef2b993.-1@webx.raydaftYaTP>, "Jan Wiltschut" <Jan.Wiltschut@gmx.de> wrote: > Hello, I�ve the following problem: > > Given: > > y = f(x) + normcdf(g(x))+normcdf(h(x)) where y is given and x is the > variable I want to get. f,g and h are functions of x and...

Need Computer Help?
PC Dude computer Help and Discussion forums offer professional help for all your computer problems. Check us out at http://pcdude.proboards86.com ...

Need Computer Help?
PC Dude computer Help and Discussion forums offer professional help for all your computer problems. Check us out at http://pcdude.proboards86.com Just wanted to thank again those who have taken a look at my forum. Also wanted to invite again those who haven't yet taken a look or joined. Check us out at http://pcdude.proboards86.com. Thank you! Gary335 wrote: > PC Dude computer Help and Discussion forums offer professional help for > all your computer problems. Check us out at > http://pcdude.proboards86.com Just wanted to thank again those who have taken a look at my forum. A...

Need Computer Help?
PC Dude computer Help and Discussion forums offer professional help for all your computer problems. Check us out at http://pcdude.proboards86.com ...

Need help with problem
Hi, a problem with this following code is really bugging me. tform = fopen(country, "r"); fseek(tform, 9L, SEEK_SET); fgets(player2, 38, tform); printf("Player Name (save): %s", player); printf("Player Name (form): %s", player2); fseek(tform, 10L, SEEK_CUR); fgets(country2, 38, tform); printf("Country Name (save); %s", country); printf("Country Name (form): %s", country2); fseek(tform, 18L, SEEK_CUR); fscanf(tform, "%i \n", &app_budget); ...

Need help for the same problem ?
>> x(1:7) = randi([4,50],1,7); d(1:7) = randi([3,5],1,7); for i = 1 : 7 sum = 0; w = 1; sum = sum + w*(x(i) - d(i)); end f(1) = sum; for i = 1 : 7 sum = 0; sum = sum + w*(x(i) - 4); end f(2) = sum; f = f(1) + f(2); >> a = Particle_Swarm_Optimization (10,2,[4 50;3 5],f,randi(100,50),2,2,2,0.4,0.9,3); Completed 0 % ...Error using feval Argument must contain a string or function_handle. Error in Particle_Swarm_Optimization (line 103) availability(p,itr)=feval(Food_availability,parameter); ...

Need Computer Help?
PC Dude computer Help and Discussion forums offer professional help for all your computer problems. Check us out at http://pcdude.proboards86.com Gary335 napisal(a): > PC Dude computer Help and Discussion forums offer professional help for > all your computer problems. Check us out at > http://pcdude.proboards86.com bleh ... Regards -- A=2EB - http://www.dzialkanadmorzem.pl/ http://www.realestate1.eu campingpl=E4tze in Polen urlaub in polen wetter polen Ostsee Polen dzialkanadmor...@onet.eu wrote: > Gary335 napisal(a): > > PC Dude computer Help...

Problem == Need Help
Seems I have a little problem ............ and I need one of you guru's to give me a hand. For years I have been selling my CD of C= stuff I archived from the old BBs for a few coins to cover shipping, never wanting to use it as a source of income, just to offer what I had to all you guys. Well sombody who recieved a CD , has put the whole damn thing ONLINE .... WITHOUT my permission !! I tell people when they get the CD they can share it with friends and make copies of it, but this jerk has put the whole thing online ( including my copyrighted programs ) I need some help tracking ...

Need Computer Help?
PC Dude computer Help and Discussion forums offer professional help for all your computer problems. Check us out at http://pcdude.proboards86.com Just wanted to thank those that have visited and/or joined. If you haven't yet visted, please do so! PC Dude offers help for users of all experience levels. Check us out at http://pcdude.proboards86.com. Gary335 wrote: > PC Dude computer Help and Discussion forums offer professional help for > all your computer problems. Check us out at > http://pcdude.proboards86.com ...

Need Computer Help?
PC Dude computer Help and Discussion forums offer professional help for all your computer problems. Check us out at http://pcdude.proboards86.com ...

Help needed with problem
Can someone help me out with this problem. Any help is appreciated. Thanks. Let doubleswap(x) be the string formed by replacing each a in x by the substring bb and each b by the substring aa. For example, doubleswap(abcab)=bbaacbbaa. Furthermore, let doubleswap(L) be the language formed of strings doubleswap(x) for x an element of L. Prove that if L is regular, then so is doubleswap(L). Where L is a subset (or equal) to {a, b, c}^*. If L is regular, the L can be expressed as L(y) for some regular expression y. We define y' to be the same as y except that we replace each a in y by a pa...

Need Computer Help?
PC Dude computer Help and Discussion forums offer professional help for all your computer problems. Check us out at http://pcdude.proboards86.com ...

Problem, need help.
I have found this nice menu form my website www.folkspot.be But it has a usability problem. When i click "crew" for example, the submenu "crew" opens and i have to click the submenu to get to the page. As you notice, this is a click to many. As you can see this is the case in several items. Some do have subitems and work fine. I'm to much of a newbee in javascript to figure this out. Can someone please help me fix this problem? thanks. -- Bigbuddha www.bigbuddha.be www.folkspot.be Open the SLIDING_MENU.JS file and look for the function "write_menu()"...

Need Help with this problem
I am in this programming class and need help on this problem: - Defines a Ruby class, Vehicle, with attributes weight, length width and height. The Vehicle class should have a class variable counts the number of vehicle objects created. - Define three subclasses, landvehicle, watervehicle, and airvehicle so they inherit the attributes of the vehicle class and so that each has some attributes of its own, numberofwheels for landvehicles, keeldepth for watervehicles, and maxairspeed or airvehicles - creates 1 landvhicle objects, 2 watervehicle objects and 3 airvehicle objects, use [ constructors...

need help in the same problem
HI I am student in engneering faculty an work on project need to use cmos camera with matlab 7 and by using tv capture card(tv tuner) to show life video . so if you have any information about this problem please help me thank you for your consideration Have a nise dreames ...

Web resources about - help with problems on computability needed!! - comp.theory

Numbering (computability theory) - Wikipedia, the free encyclopedia
In computability theory a numbering is the assignment of natural numbers to a set of objects such as functions, rational numbers , graphs , or ...

Open Directory - Computers: Computer Science: Theoretical: Automata Theory: Turing Machines
about dmoz - dmoz blog - suggest URL - update listing - become an editor - report abuse/spam - help the entire directory only in Automata_Th ...

Logic - Wikipedia, the free encyclopedia
Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy , mathematics , semantics , and computer ...

Conference on Logic, Computability and Randomness
The booklet with the abstracts of invited and contributed talks is available here . See the poster of the conference in jpg or png . The conference ...

Significant Activities (US Army)
Acronym Finder: SIGACTS stands for Significant Activities (US Army). This definition appears very rarely

AMERICAblog
skip to main skip to sidebar About us - Elections - Gay GOP Primary Schedule - Elections - Romney Economic Crisis - Jobs - TSA - Limbaugh - Fun ...

Facebook Game Development - Facebook Game App Developer - Create A Facebook Game App
Facebook Game Development - Facebook Game App Developer - Create A Facebook Game App

BOSTON SKEPTICS » book club
June 23 marks the 100th birthday of one of the most important mathematicians of the 20th century, a man who if not singlehandedly winning World ...

Tech World Preps to Honor "Father of Computer Science" Alan Turing, as Centenary Nears
Listening to the way people in the world of technology talk about Alan Turing, it's difficult to believe that the English computer scientist ...

Recognizing Alan Turing
... Turing was one of the intellectual giants of the 20th century and made major contributions to cryptanalysis and started the theory of computability. ...

Resources last updated: 2/15/2016 9:35:24 PM