What will we be doing today?
- Investigate the existance of undecidable problems in computer science
A decidable problem is a decision problem for wich an algorithm can be writen to produce a correct output for all inputs(eg.”Is the number even?”)
An undecidable problem is a problem that has no algorithim that can provide a yes or no answer, An undecidable problem may have an algorithim that works, but it can never fully work, and there are always instances in wich that is the case to make a problem undecidable.
Example
- Decidable problem if n % 3 == 0: print(“n is a multiple of three”) else: print(“n is not a multiple of three”) There is a clear clear algorithim determining if a number is a multilple of three that works for every case.
-
Undecidable problem Halting problem
With any given arbituary computer program, will it run forever or will it stop No yes or no answer to this problem every time, how does a test happen if there is no ending? If ending takes too much time to find ending, does it even exist? what if it does, but computer is not fast enough to find it so it answers the ending as none? There is no algorithim for this that reliably gives a yes or no answer
Where do we see this
When a program crashes, the computer cannot run the program causing backlog leading to the computer stopping the program after a few moments. We refer to this as a crash pro tip, this is not the only reson for a crash, just a possible one
Post Correspondence Problem
The Post Correspondence Problem (PCP) involves a set of tiles, each containing two strings. The problem asks whether it is possible to arrange these tiles in a sequence (repetitions allowed) so that concatenating the top strings of the selected tiles matches the concatenation of the bottom strings.
Tiling Problem
The Tiling Problem deals with determining whether a given shape (arbitrary shape) can be tiled using a finite set of smaller shapes (tiles). It remains undecidable due to the infinite possibilities and arrangements of shapes that would need to be considered to conclusively solve the problem.
Word Problem for Groups
The Word Problem for Groups asks whether, given a group presentation and two words formed from the group’s generators, these words represent the same group element. This problem cannot be solved algorithmically due to the undecidable nature of the word problem for groups in general.
Busy Beaver Problem
The Busy Beaver Problem involves finding the Turing machine with the most significant number of steps executed before halting among all machines with a certain number of states. Due to the vast number of possible configurations and the infinite potential for different Turing machines, determining the Busy Beaver function for a given number of states remains undecidable.
Collatz Conjecture
The Collatz Conjecture follows an iterative sequence for positive integers: if the number is even, divide it by 2; if it’s odd, triple it and add 1. The conjecture posits that regardless of the starting number, this sequence always reaches 1. Despite extensive computational verifications, a proof for all integers remains undetermined.
Post’s Correspondence Problem
Post’s Correspondence Problem (PCP) involves choosing sequences of pairs of strings from a finite set so that the concatenation of the first string in each pair matches the concatenation of the second string. The problem asks whether a sequence can be formed that produces a matching sequence of strings and is undecidable due to its relation to the Halting Problem.
Rice’s Theorem
Rice’s Theorem states that any non-trivial property about the behavior of programs that can be determined by examining their source code is undecidable. It asserts that it’s impossible to create a general algorithm to decide non-trivial semantic properties of programs.
Emptiness Problem for Turing Machines
The Emptiness Problem for Turing Machines aims to determine whether a given Turing machine recognizes any strings in its language. This problem is undecidable since determining whether a Turing machine halts on all inputs (recognizes no strings) is equivalent to solving the Halting Problem.
The Entscheidungsproblem
The Entscheidungsproblem refers to David Hilbert’s problem of finding an algorithm to decide the truth of any mathematical statement by creating a mechanical procedure for solving mathematical problems. This problem was proven undecidable by Turing, Church, and others in their work on computability theory and the limitations of computation.
POPCORN HACK, Create your own undecidable problem
Create a problem that is unsolvable by any single algorithim, for example, this problem could have infinite possibilities
- Problem: Find the point furthest from the origin (0,0) of the function f(x)=x^2.
Example
The “Infinite Sum Sequence Problem (ISSP)”
Problem Statement: Given an infinite sequence of positive integers, can it be determined whether there exists a subsequence that sums up to a specific target value?
Undecidability:
The ISSP is undecidable due to the infinite nature of sequences and the countless possible subsequence combinations, making it impossible to algorithmically determine the existence of a subsequence summing to a target value within a reasonable timeframe.
Homework Due by Friday 11:59, message Daniel Choi, give an explaination for each problem that is one scentence long. Graded on completion and explaination. send popcorn hack as a screenshot
Post Correspondence Problem:
What is the primary concern related to the Post Correspondence Problem (PCP)?
A) It involves matching strings using regular expressions.
B) It deals with finding the shortest path in a graph.
C) PCP revolves around identifying whether a set of strings can be matched in a specific sequence.
D) It’s related to optimizing sorting algorithms.
Tiling Problem
Which statement accurately describes the undecidable nature of the Tiling Problem?
A) The Tiling Problem refers to arranging tiles in a specific pattern which can always be solved using a finite number of steps.
B) There exists an algorithm that can determine if a given shape can be tiled with a specific set of smaller shapes.
C) It’s impossible to ascertain if an arbitrary shape can be tiled using a finite set of smaller shapes.
D) Tiling Problems can only be solved for regular polygons.
Word Problem for Groups
What is the core issue represented by the Word Problem for Groups?
A) It focuses on finding the most efficient algorithm for text processing in groups.
B) This problem pertains to determining if two words representing group elements are equivalent.
C) The Word Problem for Groups refers to solving crossword puzzles collaboratively.
D) It involves identifying the most commonly occurring words in a group.
Busy Beaver Problem
Which statement accurately describes the concept behind the Busy Beaver Problem?
A) It deals with optimizing the performance of multitasking systems.
B) Busy Beaver Problem revolves around finding the most efficient algorithm to sort a list of numbers.
C) It’s about determining the longest-running and most productive Turing machine.
D) Busy Beaver Problem is concerned with scheduling tasks in a time-efficient manner.
Collatz Conjecture
What is the primary characteristic of the Collatz Conjecture?
A) It’s a conjecture related to the distribution of prime numbers.
B) The conjecture revolves around finding the optimal path in a graph.
C) Collatz Conjecture deals with iterating over integers using a specific sequence until reaching the value 1.
D) It’s a hypothesis about the behavior of sorting algorithms.
Post’s Correspondence Problem
Which problem involves matching pairs of strings in a way that no two sequences produce identical combined strings?
A) Traveling Salesman Problem.
B) Knapsack Problem.
C) Post’s Correspondence Problem.
D) Dijkstra’s Shortest Path Problem.
Rice’s Theorem
What does Rice’s Theorem state?
A) It claims that all programming languages are Turing-complete.
B) Rice’s Theorem affirms that any non-trivial property about the behavior of programs is undecidable.
C) It asserts that all recursive functions can be computed using a Turing machine.
D) Rice’s Theorem describes the limitations of parallel computing.
Emptiness Problem for Turing Machines
What does the Emptiness Problem for Turing Machines aim to determine?
A) It checks whether a Turing machine can recognize an empty language.
B) This problem is concerned with finding the smallest Turing machine.
C) Emptiness Problem verifies if a Turing machine has an infinite tape.
D) It examines whether a Turing machine can accept an infinite sequence of input.
The Entscheidungsproblem
Which problem was famously formulated by David Hilbert and aimed to find a procedure that could decide the truth of any mathematical statement?
A) P vs NP Problem.
B) Riemann Hypothesis.
C) The Entscheidungsproblem.
D) Goldbach’s Conjecture.
Homework Answers:
- Post Correspondence Problem: - Solution: C) PCP asks you to figure out whether a group of strings can be matched in a particular order.
- Reasoning: What sets PCP apart from other choices is that it matches strings in a particular order.a
- Tiling Issue:
- Response: C) It is not possible to ascertain whether a given design can be tiled using a limited number of smaller shapes.
- Reasoning: The undecidability of the Tiling Problem stems from the fact that tiling cannot be determined for any given shape.
- Group Word Problem:
- Solution: B) This task ascertains whether two terms that denote group components are interchangeable.
- Reasoning: This involves determining which phrases that indicate group elements are equivalent to one another.
- Impaired Beaver:
- Response: C) The goal is to identify the Turing machine that operates the longest and produces the most.
- Collatz Conjecture: - Solution: C) The Collatz Conjecture repeats an integer sequence until it reaches 1.
- Reasoning: Using a predetermined set of rules, iteratively traverses over integers. The solution for the sixth question,
- Post’s Correspondence Problem:, is C.
- Reasoning: Unlike other well-known issues, PCP requires matching pairs of strings in a unique way.
- Rice’s Theorem: - Response: B) According to Rice’s Theorem, it is impossible to determine any non-trivial aspect of program behavior.
- Reasoning: In terms of non-trivial program properties, it confirms undecidability.
- Turing Machine Emptiness Problem: - Solution: A) It determines if a Turing machine is capable of identifying an empty language. Reasoning: It seeks to ascertain whether a Turing machine is capable of identifying an empty language.
- The Entscheidungsproblem: - Solution: C) The Problem of Decisions.
- Reasoning: It was formulated to find a procedure deciding the truth behind math problems.