List Of Undecidable Problems

PROBLEMS RELATED TO ABSTRACT MACHINE S

The Halting Problem (determining whether a specified machine halts or runs forever).

The Busy Beaver problem (determining the length of the longest halting computation among machines of a specified size).

Rice's Theorem states that for all non-trivial properties of partial functions, it is undecidable whether a machine computes a partial function with that property.

OTHER PROBLEMS

The Post Correspondence Problem .

The Word Problem For Groups .

The Word Problem for certain Formal Languages .

The problem of determining if a given set of Wang Tile s can tile the plane.

The problem of determining the Kolmogorov Complexity of a string.

Determination of the solvability of a Diophantine equation, known as Hilbert's Tenth Problem

Determining whether two finite Simplicial Complexes are homeomorphic

Determining whether the Fundamental Group of a finite simplicial complex is trivial

Determining if a Context-free Grammar generates all possible strings, or if it is ambiguous.

Given two context-free grammars, determining whether they generate the same set of strings, or whether one generates a subset of the strings generated by the other, or whether there is any string at all that both generate.

PARTIAL BIBLIOGRAPHY

¹ Appendix C includes impossibility of algorithms deciding if a grammar contains ambiguities, and impossibility of verifying program correctness by an algorithm as example of Halting Problem.

² Discusses intractability of problems with algorithms having exponential performance in Chapter 2, "Mathematical techniques for the analysis of algorithms."

	CATEGORIES ABOUT LIST OF UNDECIDABLE PROBLEMS

	mathematics-related lists

	undecidable problems

	theory of computation

	recursion theory

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

Information About

List Of Undecidable Problems