Article 19029 of rec.puzzles: Path: nntp-server.caltech.edu!elroy.jpl.nasa.gov!ames!haven.umd.edu!darwin.sura.net!paladin.american.edu!news.univie.ac.at!hp4at!mcsun!uknet!siesoft!huw From: huw@siesoft.co.uk (Huw Roberts) Newsgroups: rec.puzzles Subject: Turing Machines and Computability Message-ID: <1992Oct29.174432.29481@siesoft.co.uk> Date: 29 Oct 92 17:44:32 GMT Sender: news@siesoft.co.uk (Usenet News) Organization: Siemens Nixdorf Information Systems Ltd. Lines: 17 X-Newsreader: Tin 1.1 PL4 Can someone answer this for me (I don't have a solution). 1. What is the greatest number of steps that a turing machine with N states and M symbols can take before it halts? (obviously it is possible to make a machine which never halts and it is also possible to design machines which take a very long time. What I'm asking is for someone to find a mechanism for creating THE MOST TIME CONSUMING machine for each combination of N and M) 2. Is 1. a computable function for all N and M? Waiting with eager anticipation Huw -- Huw Roberts (huw@siesoft.co.uk) Siemens Nixdorf Information Systems Ltd. +44 344 850982 Oldbury, Bracknell, Berks. RG12 4FZ England Article 19035 of rec.puzzles: Newsgroups: rec.puzzles Path: nntp-server.caltech.edu!elroy.jpl.nasa.gov!sdd.hp.com!caen!batcomputer!cornell!karr From: karr@cs.cornell.edu (David Karr) Subject: Re: Turing Machines and Computability Message-ID: <1992Oct29.210438.9729@cs.cornell.edu> Organization: Cornell Univ. CS Dept, Ithaca NY 14853 References: <1992Oct29.174432.29481@siesoft.co.uk> Date: Thu, 29 Oct 1992 21:04:38 GMT Lines: 40 In article <1992Oct29.174432.29481@siesoft.co.uk> huw@siesoft.co.uk (Huw Roberts) writes: >Can someone answer this for me (I don't have a solution). > >1. What is the greatest number of steps that a turing machine with N states >and M symbols can take before it halts? >(obviously it is possible to make a machine which never halts and it is >also possible to design machines which take a very long time. What I'm >asking is for someone to find a mechanism for creating THE MOST TIME CONSUMING >machine for each combination of N and M) I assume you are starting the machine on a blank tape. Then obviously the number of steps is a finite-valued function of N and M, f(N,M), since there are only finitely many machines for a given N and M and you are discarding those that don't halt. (Note if the input can be arbitrary, the machine that just runs to the end of the input and halts can run for as many steps as you like.) >2. Is 1. a computable function for all N and M? Suppose it were. Then to determine whether machine B halts, I count the number of states in B, call it N, and the number of symbols in B's alphabet, call it M. Then I compute T=f(N,M). Then I simulate B for T+1 steps or until it halts, whichever comes first. If the latter then of course B halts. If the former then B never halts, because if it did it would contradict the definition of f(N,M). So if f(N,M) is computable then the halting problem is decidable. We know the halting problem is NOT decidable, however (i.e. there is no procedure that given any machine B will tell us whether or not B ever halts), so f(N,M) is not computable. You might get further elucidation by posting to comp.theory. Your question is related to the "busy beaver" problem. -- David Karr (karr@cs.cornell.edu) Article 19037 of rec.puzzles: Newsgroups: rec.puzzles Path: nntp-server.caltech.edu!elroy.jpl.nasa.gov!swrinde!zaphod.mps.ohio-state.edu!cs.utexas.edu!hellgate.utah.edu!asylum.cs.utah.edu!tolman From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman) Subject: Re: Turing Machines and Computability Date: 29 Oct 92 15:36:39 MST Message-ID: <1992Oct29.153640.11917@hellgate.utah.edu> Organization: University of Utah, CompSci Dept References: <1992Oct29.174432.29481@siesoft.co.uk> Lines: 17 >Can someone answer this for me (I don't have a solution). > >1. What is the greatest number of steps that a turing machine with N states >and M symbols can take before it halts? >(obviously it is possible to make a machine which never halts and it is >also possible to design machines which take a very long time. What I'm >asking is for someone to find a mechanism for creating THE MOST TIME CONSUMING >machine for each combination of N and M) There is NO MECHANISM, because this is undecidable just as the halting problem for regular turing machines is undecidable.... at least for most believe it is undecidable. >2. Is 1. a computable function for all N and M? Nope.