TOC Decidability

Question

Are the following problems decidable?

1.{⟨M⟩∣M is a TM and there exist an input whose length is less than 100, on which M halts}

I think we can simulate all the combinations of strings whose length is less than 100,and if the machine halts for any of them ,then it would be selected.?But i am not sure what will happen if there is no such input?Will it cause loop so is it RE but not REC?

2{⟨M⟩ : M is a TM which stops on every input in no more than 50 steps}

 Here also we can simulate all possible inputs of 50 length and then check if all are halting the machine?But i don't know what will happen if these words are not accepted by machine,Can it hang the machine?Is it also RE but NOT REC

Please correct if I am going wrong

Comments

i think both of them RE

Answer 1

1 is decidable. Consider the following logic, since the length of the tape is infinite, at first, after 99 cells we can insert a special symbol. This symbol servers as a indicator. Now, move the head back to starting of the state. Now, start checking every strings from length 1. String of length 10 occupies first 10 cells and rest of 90 cells will contain blank cells. So now string of length 100 will occupy first 100 cells. After checking all the strings of length of 100, next permutation of string would be the first string of length 101. While writing a string on the tape , we replace previously paced string characters or blank symbols with new string characters. While writing the characters, if we encounter the special symbol,then we can right way say "NO, this TM doesnot halt strings of length < 100". If there exists any string the TM is going to halt anyway. Thus we can say "YES" and "NO". Thus decidable. 

or since problem defined by statement 1 can be done by program. Any program can be implemented by a Turing machine. Thus we can reduce problem 1 to a program, since a this program is decidable, problem 1 is decidable.

2, It seems problem 2 is also decidable, http://cs.stackexchange.com/questions/3101/is-the-set-of-turing-machines-which-stop-in-at-most-50-steps-on-all-inputs-deci

Comments

@Nithish why you are not taking the case when machine will hang and loop forever then how will you decide?

I also think both problems are RE but not REC.