0
$\begingroup$

As stated here https://books.google.cz/books?id=dwpeNRgjK68C&pg=PA57&lpg=PA57&dq=uniform+halting+problem&source=bl&ots=qsbv_672W9&sig=NDcebhxrwcYdF-P15dor565l8Jc&hl=en&sa=X&ved=0ahUKEwj5mpG-zNTJAhUH6A4KHSB_DOI4ChDoAQgpMAI#v=onepage&q&f=false
Uniform halting problem is variation of Halting problem and asks the question if TM will halt on every input.
I'm little bit confused about the reduction and I'd like some insights whether I understood it correctly or not. I'd like to approach this somewhat informally. This is how I understand it:

  • Let's suppose we got TM - M which solves the HP for input w
  • Then we have TM - M' which should solve the UHP
  • M' is constructed like this: takes it's input - y and erases it from the tape and then writes w on it
  • Next it simulates M on the tape (which now contains w)

So M should halt on w, if M halts then M' will halt on any input (because it erases it anyway and it halts on w and w is indeed a valid input) if M will not halt, then M' will not halt on any input. Since we know M cannot know for sure if it will halt on w the UHP is undecidable as is HP.

Couple of things I'm not sure about.

  • y is the input I should decide whether it will halt on and x is input for M which M halts on (supposing M solves HP) ?
  • Wouldn't it be easier to just say if I can't halt on one input I for sure can't halt on every/all inputs? In other words if HP is not decidable how can UHP be anything else but undecidable??
$\endgroup$
  • 1
    $\begingroup$ Your description of the reduction is confusing (or confused?), but in any case the reduction does not seem possible. The Uniform Halting problem is harder than the Halting Problem. Perhaps you've got the direction of the reduction backwards? $\endgroup$ – Andrej Bauer Dec 14 '15 at 22:44
  • $\begingroup$ I may got it confused a bit. Anyway I already got what I wanted to know from elsewhere thus the question is not relevant anymore. I appreaciate the answer though. $\endgroup$ – Daniel Stodůlka Dec 15 '15 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.