Games Site GitHub LinkedIn CV Old Academic Website
Logo Alex's notes
  • Alex Wendland
  • Online Masters of Science in Computer Science Notes
  • CS6215 Introduction to Graduate Algorithms
  • Week 1 - Dynamic Programming
  • Week 1 - Knapsack Problem
  • Week 2 - Chain Matrix Multiply
  • Week 2 - Shortest Paths
  • Week 3 - Fast Integer Multiplication
  • Week 3 - Linear-Time Median
  • Week 3 - Solving Recurrences
  • Week 4 - Fast Fourier Transforms
  • Week 6 - 2-Satisfiability
  • Week 6 - Graph algorithms - strongly connected components
  • Week 6 - Minimum Spanning Tree
  • Week 7 - Edmonds-Karp algorithm
  • Week 7 - Ford-Fulkerson Algorithm
  • Week 7 - Image Segmentation
  • Week 7 - Max-flow Generalizations
  • Week 7 - Max-Flow Min-Cut
  • Week 8 - Bloom Filters
  • Week 8 - Modular Arithmetic
  • Week 8 - RSA
  • Week 9 - Algorithms for the exam
  • Week 10 - Graph problem complexity
  • Week 10 - NP overview
  • Week 10 - NP-completeness
  • Week 11 - Linear Programming
  • Week 12 - Halting problem
  • Week 12 - Knapsack complexity
  • Week 12 - Max-SAT approximation algorithm
  • Week 13 - Known NP-complete problems
  • Week 15 - Markov Chains

# Week 12 - Halting problem

Last edited: 2023-11-13

Statement

We want to show that that this problem is computationally impossible or in other words it is undecidable .

undecidable

The Halting problem is undecidable

Made by Alex powered by Hugo