Ответ 1
Это "доказательство противоречия", редукция ad absurdum. (Латинские фразы всегда хороши в теоретических классах... если они имеют смысл, конечно.)
Эта программа H - это просто программа с двумя входами: строка, представляющая собой программу для некоторой машины, и ввод. В целях доказательства вы просто предполагаете, что программа H правильная: она просто остановится и примет, если M принимает с w. Вам не нужно думать о том, как это будет сделано; на самом деле, мы собираемся доказать, что это не может, что никакая такая программа H не может существовать,...
Поскольку
если бы такая программа существовала, мы могли бы немедленно построить другую программу H ', которую H не мог решить. Но, по предположению, такой программы нет: H может решить все. Таким образом, мы вынуждены заключить, что никакая программа, определенная так, как мы определили H, не возможна.
Кстати, метод доказательства reductio является более противоречивым, чем вы могли ожидать, учитывая, как часто его используют, особенно в области компьютерных наук. Вы не должны смущаться, чтобы найти это немного странным. Магический термин "неконструктивный", и если вы чувствуете себя очень амбициозным, спросите одного из ваших профессоров о критике Эретта Бишопа неконструктивной математики.