Decidability (Undecidable or Decidable problem)

Card Puncher Data Processing

About

Decidability is the question of what can or cannot be done by a computer.

  • Problems that cannot be solved by computation are called undecidable
  • Problems that can be solved by computer are called decidable

Example

undecidable

There is no way to tell whether a program will ever print a particular word, or even whether it will ever print anything at all.




Discover More
Sorting Quicksort Anim
Algorithm - Problem

A problem in algorithm is what need to be solved. Problems that cannot be solved by computation are called undecidable Problems that can be solved by computer are called decidable Tractable:...
Card Puncher Data Processing
Turing Machine

are automata that model the power of real computers They allow: the study of decidabilty to distinguish tractable problems
Card Puncher Data Processing
What is an Automaton? State Machine

Automata theory is the study of abstract computing devices or machines. The word automata (the plural of automaton) comes from the Greek word αὐτόματα, which means self-acting An automaton consists...



Share this page:
Follow us:
Task Runner