Abstract: Turing proposed a computational model in his paper published in 1936. This model is now well-known as Turing machines. In the paper, Turing considered the halting problem and proved that it is not solvable. By coding the halting problem into the word problem, in 1955, Novikov constructed a finitely presentable group G such that the word problem of G is not solvable. It is the first unsolvable problem in algebra. Boone provided a different construction in 1958. After all these, Higman proved his famous embedding theorem: a finitely generated group G is recursively presentable if and only if it can be embedded into a finitely presentable group. Higman’s theorem gave a close link between algebra and recursion theory. Higman proved that his embedding theorem implies the Novikov-Boone theorem. In this talk, we will review basic ideas involved in theorems, and we will also show recent work on undecidability in algebra, with examples and techniques.


Bio Sketch: Wu Guohua received his PhD from Victoria University of Wellington,New Zealand in 2002. Subsequently, he became a FRST postdoc fellow at VUW, and joined Nangyang Technological University in 2005. His research is in the area of logic, computability and topological aspects of computation theory. He has publications in renowned journals in logic, including APAL, JML, JSL, etc.