Undecidability of Word Problems
发布时间:2024年07月07日
浏览次数:718
发布者: Ruixin Li
主讲人: 吴国华(新加坡南洋理工大学)
活动时间: 从 2024-07-17 16:00 到 17:00
场地: 北京国际数学研究中心,镜春园78号院(怀新园)77201室
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.
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.