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