Few confusions about halting problem is unsolvable proof-:

  • MHB
  • Thread starter shivajikobardan
  • Start date
  • Tags
    Proof
In summary, the conversation discusses the concept of a Turing machine taking its own code as input. It is possible for a machine to take its code as input without changing the code itself. However, adding output instructions to the machine may change its code, making it impossible for the machine to output its own code. The conversation also touches on the idea of self-reproducing machines and provides a link to additional resources for understanding the theory of computation.
  • #1
shivajikobardan
674
54
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
 
Technology news on Phys.org
  • #2
shivajikobardan said:
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?
 
  • #3
Evgeny.Makarov said:
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.
 

Related to Few confusions about halting problem is unsolvable proof-:

What is the halting problem?

The halting problem is a mathematical problem that deals with determining whether a computer program will eventually stop or continue to run forever. It was first introduced by Alan Turing in 1936 and has been a topic of study in the field of computer science ever since.

Why is the halting problem considered unsolvable?

The halting problem is considered unsolvable because there is no algorithm or computer program that can accurately predict whether any given program will halt or run forever. This was proven by Alan Turing in his 1936 paper, where he showed that a solution to the halting problem would lead to a contradiction.

What is the proof of the unsolvability of the halting problem?

The proof of the unsolvability of the halting problem is a mathematical proof that was first presented by Alan Turing in his 1936 paper. It involves creating a hypothetical program that would be able to solve the halting problem, and then showing that this program leads to a contradiction, thus proving that the halting problem is unsolvable.

Are there any limitations to the proof of the unsolvability of the halting problem?

One limitation of the proof of the unsolvability of the halting problem is that it only applies to general computer programs. This means that there may be specific cases where the halting problem can be solved, but these cases are exceptions rather than the norm.

How does the unsolvability of the halting problem impact the field of computer science?

The unsolvability of the halting problem has had a significant impact on the field of computer science. It has influenced the development of programming languages and the design of computer systems, as well as areas such as artificial intelligence and security. It has also led to the discovery of other unsolvable problems in computer science.

Similar threads

  • Programming and Computer Science
Replies
1
Views
796
  • Programming and Computer Science
Replies
1
Views
982
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
1
Views
757
  • Programming and Computer Science
Replies
29
Views
3K
  • Programming and Computer Science
Replies
2
Views
893
  • Programming and Computer Science
Replies
1
Views
656
  • Programming and Computer Science
Replies
1
Views
543
  • Programming and Computer Science
Replies
2
Views
623
  • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
Back
Top