title: Prove that this language is undecidable
body: <p>Is the following language <em>L</em> undecidable?</p>
  
  <blockquote>
    <p><em>L</em> = {<em>M</em> | <em>M</em> is a Turing machine description and there exists an input <em>x</em> of length <em>k</em> such that <em>M</em> halts after at most <em>k</em> steps}</p>
  </blockquote>
  
  <p>I think it is but I couldn't prove it. I tried to think of a reduction from the halting problem.</p>