Why can Conway’s Game of Life be classified as a universal machine?

I was recently reading about artificial life and came across the statement, “Conway’s Game of Life demonstrates enough complexity to be classified as a universal machine.” I only had a rough understanding of what a universal machine is, and Wikipedia only brought me as close to understanding as Wikipedia ever does. I wonder if anyone … Read more

Can a CFG generate an accepting configuration? – or is there a turing-recognizable CFG language that is not decidable

I could not think of a way to concisely write down my question clearly, but I’d like to ask, from Sipser’s book, ALLCFG is an undecidable language (where ALLCFG means that G is a CFG that generates ∑∗). In his textbook, there is a polynomial reduction from ¯ATM (complement of ATM, where ATM is the … Read more


Consider $\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\}$. Let $S$ be the following algorithm, which solves $\mathsf{A_{TM}}$: “On input $\langle M, w \rangle$, where $M$ is a TM and $w$ is a string: Construct the following TM $M_2$: $M_2$ = “On input $x$: If $x$ has … Read more

Is a set B={y,∃x∈A,f(x)=y}B = \{y, \exists x \in A, f(x)=y\} recursive if A is a recursive set and f is a N−>NN->N total computable function?

Obviously, B would be recursive if for every TCF f, there was an inverse fuction that would return all possible values, as we could just take these and then check if any of them is in A. However I cannot find a proof (or counter-proof) that you can invert TCFs this way. AFAIK, all injective … Read more

Mathematical resource material accompanying TAPL

I’m currently reading Types and Programming Languages by Benjamin C. Pierce and just arrived at chapter 21 Metatheory of Recursive Types. Prior to this chapter I found the book challenging but comprehensible, but I’m lost on this chapter. Almost none of the definition make intuitively sense to me. Are there any more accessible resources regarding … Read more

Rice’s theorem applicable to the following language?

Let L={⟨M⟩∣M halts on ⟨M⟩} be a language where ⟨M⟩ is the Code of the TM M. L is undecidable. I’ve heard that I can’t use Rice’s theorem to proof its undecidability. But why? I can construct a set S={fM∣fM(⟨M⟩)∈{0,1}}. It’s clear that S is not empty and S contains not every TM. Answer Because there may … Read more

Reading elements of a countable set with Turing machine

I have a basic question about the behavior of a potential Turing machine. Suppose that S is a countable set of binary strings, so that we can enumerate S as (si)n∈N. Suppose that we want to construct a Turing machine M that, on any input, simply writes each element of S on a tape in … Read more

Is McCarthy Formalism first ever formalism for defining functions recursively in computer science?

McCarthy formalism is a formalism for defining functions recursively, first introduced in classic paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (1960). From Wikipedia: In his 1967 Computation: Finite and Infinite Machines, Marvin Minsky in his § 10.6 Conditional Expressions: The McCarthy Formalism describes the “formalism” as follows: “Practical computer … Read more

Theory for programs that are “embedded” in other programs?

We can make the following distinctions: (I will use the term “program” and “machine” as synonyms). A (baseline) machine. This can be formalized by a Turing machine. It receives an input, and computes an output, fully by itself. An oracle machine T. This is a Turing machine, but with an additional feature: it can use … Read more