MHB Few confusions about halting problem is unsolvable proof-:

[shivajikobardan]

https://lh6.googleusercontent.com/xFVXel6_szTL_WVir-dz4SpFIGkHqMY9428mA3HRY2Nl06Ez9Wt9N3RZ8U0Jmsshwnl7ekEQX31ccWBXBNW5XUhRwVQafqZOPHpmy3fY4L94b4UmqGR-N7IIO8Ep1wpWg4BmDebD
How can same machine take same machine as input(is it same machine taking encoding of itself as input—if that’s the case, what does that means some examples to understand this)? (in Universal Turing Machine, i know it was possible). What does that even mean here?

I feel like adding a turing machine flipper is like cheating and should not be allowed as well.

https://lh4.googleusercontent.com/Q52OnluXaJhBGPUQEcMzbJlS5ooxohC_Pn_D_fUq_BUCmRyfuE1d4XRY8KwEBIkqzy8zJBiaZT-VGQlqQQKQ0Qdiw0VD0v2pxHhu4WVTfGP-7_bqzTG4pnjhHJfXoMN7NC4Adplg

 

[Evgeny.Makarov]

How can same machine take same machine as input

Consider an arbitrary Turing machine (TM). Do you agree that you can give to it any finite word in the input alphabet as input? The machine may accept it, reject it or loop forever, but it will not burst into flames whatever the word is. There is nothing in the definition of a Turing machine that says, for example, that input words longer than $10^{100}$ or containing the first $10^{10^{10}}$ digits of $\pi$ are prohibited.

Next, do you agree that every Turing machine has a code, which is a finite word?

If you said "yes" to both questions, then it follows by simple logic that for any machine its code can be given to it as input.

A problem could arise if providing an input changed the machine code. This does indeed happen when we are talking about output rather than input. Suppose we want a machine to output a certain word. The simplest way is to include some print instructions or their TM analogs. For example, we may consider a function $\text{print}(\langle M\rangle, w)=\langle M'\rangle$ that takes a machine $M$ and returns a machine $M'$ that behaves just like $M$, but prints $w$ just before $M$ stops. If the function $\text{print}$ is implemented straightforwardly, by adding a sequence of print statements, then the size of $M'$ is greater than the size of $w$ because $M'$ contains $w$.

For this reason it is not obvious if one can make a machine that outputs its own code. Let $S$ be a trivial machine that does nothing and simply stops. Building a TM that outputs its own code asks for finding a fixed point of $\text{print}$, i.e., machine $M$ such that $f(\langle S\rangle, \langle M\rangle)=\langle M\rangle$. Due to the size increase described above such fixed point does not exist. In fact, building a self-reproducing machine (it is called a quine) is possible, but it requires considering a more sophisticated function than $\text{print}$.

In any case, while adding output changes the machine code, feeding an input to a machine doesn't. The input and the machine are completely independent; therefore, there is no paradox or vicious circle in giving its own code to a machine as input.

I like how the document you posted explains the material. Could you say where it is from? Perhaps there is a link to this and similar documents about the theory of computation?

 

[shivajikobardan]

I like how the document you posted explains the material. Could you say where it is from? Perhaps there is a link to this and similar documents about the theory of computation?

https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_21.pdfhere it is. I liked it as well. I googled and found it out.