Scribd
Upload
10 views2 pages

ASS Format

The document contains an assignment by Rati Antapurkar on implementing a Turing machine to increment a binary number using C++. It includes an algorithm and a program that demonstrates how to increment a binary number, as well as a discussion on the P=NP problem, which explores the relationship between problems that can be solved efficiently and those whose solutions can be verified efficiently. The P=NP question remains unsolved and is a significant topic in theoretical computer science.

Uploaded by

ratiantapurkar001
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
10 views2 pages

ASS Format

The document contains an assignment by Rati Antapurkar on implementing a Turing machine to increment a binary number using C++. It includes an algorithm and a program that demonstrates how to increment a binary number, as well as a discussion on the P=NP problem, which explores the relationship between problems that can be solved efficiently and those whose solutions can be verified efficiently. The P=NP question remains unsolved and is a significant topic in theoretical computer science.

Uploaded by

ratiantapurkar001
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

Department of Information Technology

Assignment
Name: Rati Antapurkar
Roll no : 3

Q.1) Implementation of a Turing machine for “Problem statement Increment


Binary Number By 1 using c/c++.

Algorithm:
1. Start from the rightmost bit.
2. If bit is `0`, change to `1` and stop.
3. If bit is `1`, change to `0` and move left.
4. If all bits are `1`, add `1` at the start.
5. Output the result.

Program:
#include <iostream>
#include <string>
using namespace std;
string incrementBinary(string binary) {
int n = [Link]();
for (int i = n - 1; i >= 0; i--) {
if (binary[i] == '0') {
binary[i] = '1'; // Change '0' to '1' and stop (no carry)
return binary;
} else {
binary[i] = '0'; // Change '1' to '0' and continue (carry over)
}
}
return "1" + binary;
}
int main() {
string binary;
cout << "Enter a binary number: ";
cin >> binary;
string incrementedBinary = incrementBinary(binary);
cout << "Incremented binary number: " << incrementedBinary << endl;
return 0;
}
Output:
Enter a binary number: 1101
Incremented binary number: 1110

Q.2) Justify the statement P=NP?

The question "P = NP?" is a foundational unsolved problem in computer science that explores
the relationship between two classes of problems: those that can be solved efficiently (P) and
those whose solutions can be verified efficiently (NP). Specifically, **P** is the set of problems
that can be solved by an algorithm in polynomial time, meaning as the input size grows, the
time it takes to solve the problem remains manageable. **NP**, on the other hand, includes
problems for which, if given a solution, we can verify its correctness in polynomial time, even
though finding that solution might be hard. The big question "Is P = NP?" asks whether every
problem for which a solution can be quickly verified (NP) can also be quickly solved (P). If P
were equal to NP, it would mean that many problems we currently find computationally
hard—such as complex scheduling, optimization, and cryptographic problems—could be
solved as efficiently as they are verified, revolutionizing fields that rely on computation.
However, no one has yet been able to prove or disprove that P equals NP, making it one of the
greatest mysteries in theoretical computer science and mathematics.

You might also like