In JavaScript (somewhat applicable elsewhere), where you don't know what target implementation your code is running on, is there a way to feature detect if the underlying sorting algorithm (of Arra...

For example, the language of Turing machines that do not accept their own encoding cannot be accepted by any Turing machine.

What is a Turing machine and why do people keep mentioning it? My IBM PC is all I need to do my computation! Why does anyone care about these machines?

Let T = {<M> | M is a TM that accepts wr whenever it accepts w}. Show that T is undecidable. I have two answers to this question - San Diego: 5.9 Let T = { <M> | M is a TM that accep...

I'm trying to wrap my head around lambda calculus, and how it relates to language, compiler and binary code. What it actually means that lambda calculus is equivalent to turing machine, and where i...

As far as I know, a Turing machine can be made to execute loops or iterations of instructions encoded on a Tape. This can be done by identifying Line separators and making the Turing machine go bac...

I read this in a book on computability: (Kleene's Theorem) A language is regular if and only if it can be obtained from finite languages by applying the three operations union, concatenation, ...

An autogram is a sentence which describes the characters it contains, usually enumerating each letter of the alphabet, but possibly also the punctuation it contains. Here is the example given in th...

Is Brainfuck Turing-complete if the cells are bits, and the + and - operations simply flip a bit? Is there a simple proof that Brainfuck-like languages are Turing-complete regardless of the cell si...

How do you argue for the fact that lambda calculus is Turing complete (in the simplest way possible) ?

While doing my own BigInteger implementation, I got stuck with the extended GCD algorithm, which is fundamental for finding modular multiplicative inverse. As the well-known Euclidean approach perf...

I read Ken Thompson's classic paper Reflections on Trusting Trust in which he prompts users to write a Quine as an introduction to his argument (highly recommended read). A quine is a computer p...

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 unders...

AFAIK, turing computable numbers are numbers whose i-th index can be returned by a Turing Machine. So a non-computable number would be something like a number whose decimal points are decided...