Scribd
Upload
4 views4 pages

Turing Machine Halting Problem

The document discusses the Turing Machine Halting Problem, which asks whether a Turing machine will finish computing a given input string in a finite number of steps. It presents a proof by contradiction, demonstrating that if a halting machine exists, it leads to an inverted halting machine that creates a paradox, thus proving the problem is undecidable. The document also includes references to various tutorials and certifications offered by an educational technology company.

Uploaded by

Shubham Vishwakarma
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views4 pages

Turing Machine Halting Problem

The document discusses the Turing Machine Halting Problem, which asks whether a Turing machine will finish computing a given input string in a finite number of steps. It presents a proof by contradiction, demonstrating that if a halting machine exists, it leads to an inverted halting machine that creates a paradox, thus proving the problem is undecidable. The document also includes references to various tutorials and certifications offered by an educational technology company.

Uploaded by

Shubham Vishwakarma
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Page 1 of 4

SQL HTML CSS Javascript Python Java C C++ PHP Scala C#

Turing Machine Halting Problem

Input − A Turing machine and an input string w.

Problem − Does the Turing machine finish computing of the string w in a finite number of steps? The
answer must be either yes or no.

Proof − At first, we will assume that such a Turing machine exists to solve this problem and then we
will show it is contradicting itself. We will call this Turing machine as a Halting machine that produces
a yes or no in a finite amount of time. If the halting machine finishes in a finite amount of time, the
output comes as yes, otherwise as no. The following is the block diagram of a Halting machine −

Now we will design an inverted halting machine (HM) as −

If H returns YES, then loop forever.

If H returns NO, then halt.


Page 2 of 4

The following is the block diagram of an Inverted halting machine −

Further, a machine (HM)2 which input itself is constructed as follows −

If (HM)2 halts on input, loop forever.

Else, halt.

Here, we have got a contradiction. Hence, the halting problem is undecidable.

TOP TUTORIALS

Python Tutorial

Java Tutorial

C++ Tutorial

C Programming Tutorial

C# Tutorial

PHP Tutorial

R Tutorial

HTML Tutorial

CSS Tutorial

JavaScript Tutorial

SQL Tutorial

TRENDING TECHNOLOGIES

Cloud Computing Tutorial

Amazon Web Services Tutorial

Microsoft Azure Tutorial


Page 3 of 4

Git Tutorial

Ethical Hacking Tutorial

Docker Tutorial

Kubernetes Tutorial

DSA Tutorial

Spring Boot Tutorial

SDLC Tutorial

Unix Tutorial

CERTIFICATIONS

Business Analytics Certification

Java & Spring Boot Advanced Certification

Data Science Advanced Certification

Cloud Computing And DevOps

Advanced Certification In Business Analytics

Artificial Intelligence And Machine Learning

DevOps Certification

Game Development Certification

Front-End Developer Certification

AWS Certification Training

Python Programming Certification

COMPILERS & EDITORS

Online Java Compiler

Online Python Compiler

Online Go Compiler

Online C Compiler

Online C++ Compiler

Online C# Compiler

Online PHP Compiler

Online MATLAB Compiler

Online Bash Compiler

Online SQL Compiler

Online Html Editor

ABOUT US | OUR TEAM | CAREERS | JOBS | CONTACT US | TERMS OF USE |


Page 4 of 4

PRIVACY POLICY | REFUND POLICY | COOKIES POLICY | FAQ'S

Tutorials Point is a leading Ed Tech company striving to provide the best learning material on technical
and non-technical subjects.

© Copyright 2025. All Rights Reserved.

Home Whiteboard AI Assistant Online Compilers Jobs Tools Articles

Chapters Categories

You might also like