# Questions tagged [turing-machines]

The turing-machines tag has no usage guidance.

5
questions

**-1**

votes

**0**answers

37 views

### Turing machine equivalent to lambda calculus proof [closed]

how we can prove that the Turing machine is equivalent to lambda calculus?

**3**

votes

**2**answers

474 views

### Are ITTM's necessary to compute Turing's "computable numbers" and what does that mean for ordinary recursion theory?

In his celebrated paper, "On Computable Numbers, With An Application To the Entscheidungsproblem", Turing defines a "computable number" as follows:
The "computable" ...

**27**

votes

**3**answers

3k views

### What sorts of extra axioms might we add to ZFC to compute higher Busy Beaver numbers?

First, some context. Ever since I was a high schooler, I have been fascinated with large numbers. As I have grown in mathematical maturity, I have become both disappointed and fascinated to see that ...

**2**

votes

**0**answers

106 views

### Is Steiner symmetrization "Turing complete"?

This question stems from intuition so it is a little soft. It concerns performing computation using transformations on sets. The idea is that a rearrangement like Steiner symmetrization might be "...

**3**

votes

**1**answer

537 views

### Proof that dynamical systems with bounded Kolmogorov complexity can't emulate all Turing machines

Motivation:
During a discussion with neuroscientists the question arose as to whether the human brain may emulate any Turing machine. If we assume that animal brains may be modelled as deterministic ...