Stack Overflow
Stack Overflow

Questions tagged [computability]

83 questions
67
votes
5 answers

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…
Ziggy
  • 21,845
  • 28
  • 75
  • 104
47
votes
11 answers

What's a 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?
Claudiu
  • 224,032
  • 165
  • 485
  • 680
24
votes
2 answers

What is the "trick" to writing a Quine?

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 program which takes no input and produces a copy of its…
calebds
  • 25,670
  • 9
  • 46
  • 74
17
votes
4 answers

Is there a black box method to detect if a sorting algorithm is stable?

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 Array.sort) is stable or not, knowing only that it…
forivall
  • 9,504
  • 2
  • 33
  • 58
14
votes
2 answers

Turing completeness of lambda calculus?

How do you argue for the fact that lambda calculus is Turing complete (in the simplest way possible) ?
samsamara
  • 4,630
  • 7
  • 36
  • 66
14
votes
2 answers

What it means lambda calculus is equivalent to turing machine

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 it actually manifest itself? I don't understand how…
Tuomas Toivonen
  • 21,690
  • 47
  • 129
  • 225
11
votes
1 answer

Is PI a turing computable number?

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 if some other program halts on some other input, etc. But…
Gaurav Dadhania
  • 5,167
  • 8
  • 42
  • 61
11
votes
4 answers

An infinite language can't be regular? What is a finite language?

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, repetition a finite number of times. I am…
Roger Costello
  • 3,007
  • 1
  • 22
  • 43
9
votes
2 answers

What are all known languages that Turing machines cannot accept?

For example, the language of Turing machines that do not accept their own encoding cannot be accepted by any Turing machine.
Rose Perrone
  • 61,572
  • 58
  • 208
  • 243
8
votes
2 answers

Turing-completeness of a modified version of Brainfuck

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 size, or do I need to think of a program that…
Eric Yu
  • 161
  • 3
6
votes
1 answer

Let T = { | M is a TM that accepts $w^R$ whenever it accepts w}. Show that T is undecidable

Let T = { | 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 is a TM that accepts wr whenever it accepts w }. Assume T is decidable and…
Intuition
  • 137
  • 1
  • 6
6
votes
1 answer

Lehmer's extended GCD algorithm implementation

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 performs too slow, with hybrid and binary algorithms…
Anton Samsonov
  • 1,380
  • 17
  • 34
5
votes
1 answer

Decidability and Recursive Enumerability

Say there exist Turing Machines M1, M2, M3, the languages they recognize being L(M1), L(M2), and L(M3), respectively. The following language L = {(M1, M2, M3) : L(M1), L(M2), and L(M3) are not equal} Is the language decidable? Recursively…
Glen Marek
  • 75
  • 4
5
votes
1 answer

Ackermann function versus n nested loops

I'm working my way thorugh a book on computation (Minksy 1967) and am having a hard time with relating a recursive function to a function defined in terms of loops. Specifically he asks to find the relationship between two functions: The Ackermann…
pat
  • 301
  • 3
  • 7
4
votes
3 answers

Is poly-time functions class recursively enumerable?

If I define Poly-time functions, the functions that are computable by a turing machine in maximum polynomial(n) time, which n is size of input. Is the class of these functions recursively enumerable?
Saiiiira
  • 191
  • 1
  • 1
  • 4
1
2 3 4 5 6