Using Go in teaching the theory of computation

Research output: Contribution to journalArticleResearch

Abstract

With increased public interest in the ancient game of Go since 2016, it is an especially good time to use it in teaching. The game is an excellent source of exercises in the theory of computation. We give some exercises developed during our research on Go which were then used when teaching this subject at Monash University. These are based on One-Dimensional Go (1D-Go) which uses a path graph as its board. They are about determining whether or not a position is legal and counting the number of legal
positions. Curriculum elements that may be illustrated and practised using 1D-Go include: regular expressions, linear recurrences, proof by induction, finite automata, regular grammars, context-free grammars and languages, pushdown automata, and Turing machines.
Original languageEnglish
Pages (from-to)65-78
Number of pages14
JournalSIGACT News
Volume50
Issue number1
DOIs
Publication statusPublished - Mar 2019

Keywords

  • theory of computation
  • Go
  • Weiqı
  • Baduk
  • game
  • legal position

Cite this

@article{746c008e88bf4d45bf73ee1feaf317e8,
title = "Using Go in teaching the theory of computation",
abstract = "With increased public interest in the ancient game of Go since 2016, it is an especially good time to use it in teaching. The game is an excellent source of exercises in the theory of computation. We give some exercises developed during our research on Go which were then used when teaching this subject at Monash University. These are based on One-Dimensional Go (1D-Go) which uses a path graph as its board. They are about determining whether or not a position is legal and counting the number of legalpositions. Curriculum elements that may be illustrated and practised using 1D-Go include: regular expressions, linear recurrences, proof by induction, finite automata, regular grammars, context-free grammars and languages, pushdown automata, and Turing machines.",
keywords = "theory of computation, Go, Weiqı, Baduk, game, legal position",
author = "Farr, {Graham Ernest}",
year = "2019",
month = "3",
doi = "10.1145/3319627.3319639",
language = "English",
volume = "50",
pages = "65--78",
journal = "SIGACT News",
issn = "1943-5827",
publisher = "Association for Computing Machinery (ACM)",
number = "1",

}

Using Go in teaching the theory of computation. / Farr, Graham Ernest.

In: SIGACT News, Vol. 50, No. 1, 03.2019, p. 65-78.

Research output: Contribution to journalArticleResearch

TY - JOUR

T1 - Using Go in teaching the theory of computation

AU - Farr, Graham Ernest

PY - 2019/3

Y1 - 2019/3

N2 - With increased public interest in the ancient game of Go since 2016, it is an especially good time to use it in teaching. The game is an excellent source of exercises in the theory of computation. We give some exercises developed during our research on Go which were then used when teaching this subject at Monash University. These are based on One-Dimensional Go (1D-Go) which uses a path graph as its board. They are about determining whether or not a position is legal and counting the number of legalpositions. Curriculum elements that may be illustrated and practised using 1D-Go include: regular expressions, linear recurrences, proof by induction, finite automata, regular grammars, context-free grammars and languages, pushdown automata, and Turing machines.

AB - With increased public interest in the ancient game of Go since 2016, it is an especially good time to use it in teaching. The game is an excellent source of exercises in the theory of computation. We give some exercises developed during our research on Go which were then used when teaching this subject at Monash University. These are based on One-Dimensional Go (1D-Go) which uses a path graph as its board. They are about determining whether or not a position is legal and counting the number of legalpositions. Curriculum elements that may be illustrated and practised using 1D-Go include: regular expressions, linear recurrences, proof by induction, finite automata, regular grammars, context-free grammars and languages, pushdown automata, and Turing machines.

KW - theory of computation

KW - Go

KW - Weiqı

KW - Baduk

KW - game

KW - legal position

U2 - 10.1145/3319627.3319639

DO - 10.1145/3319627.3319639

M3 - Article

VL - 50

SP - 65

EP - 78

JO - SIGACT News

JF - SIGACT News

SN - 1943-5827

IS - 1

ER -