Talk:Turing-complete

Computing the Ackermann function doesn't ensure Turing-completeness

I've removed the following incorrect statements from the article:

"In order to compute the Ackermann function for any values of m and n, however, a Turing-complete system is required. It is this meaning of Turing-complete which is more significant; if some computational system that can solve problems of size n can also always solve the same problems for size n+1, that system is Turing-complete."

One counterexample is the existence of languages in which all programs halt — so the language cannot be Turing-complete — yet can compute the Ackermann function (which is total). E.g., see Functions computable by total Turing machines.

Other counterexamples are languages constructed by modifying a Turing-complete language so it can only compute functions that never exceed some selected very-fast-growing computable function that everywhere exceeds the Ackermann function. Then it can compute Ackermann's function, but is not Turing-complete (because there are recursive functions, growing faster than the selected one, that it can't compute). --r.e.s. (Talk) 08:49, 17 November 2007 (UTC)

Or, of course, HQ9+ modified to add an Ackermann command. --ais523 13:13, 19 November 2007 (UTC)

Since HQ9+ is a joke language, I suppose you meant that as a joke (in the same sense as "add an Omega command" to magically compute Chaitin's Omega, for example. OTOH, it does suggest trivial counterexamples (which is what you might have intended); e.g., just take any language that has an Ack program in it, and restrict the language to that program alone — a one-program language. --r.e.s. (Talk) 19:54, 20 November 2007 (UTC)

I was trying to bring up the point of trivial counterexamples. HQ9+ is a joke, but it is quite mathematically interesting as a model for trivial counterexamples. Likewise, that sort of program gives a trivial proof that there are an infinite number of computational classes (some of which are more interesting than others). --ais523 10:35, 21 November 2007 (UTC)

incorrect description in terms of C

In the middle of the "Overspecification" section, we have:

"An interesting example of this is the C programming language; if, as the specification would seem to entail, sizeof(void*) must be finite, then it cannot be Turing-complete, because it cannot address an unbounded storage space."

This is an error. First, while it's true that a "void *" is a pointer, it points to nothing. Second, sizeof() on a pointer returns the size of the pointer, not the size of what the pointer points to. This author seems to be confusing the size of a regions of memory allocated to a type with the size of the type itself. It is true that sizeof() must return an integer value (an unsigned integer size_t for ANSI C, int or long for traditional C) which is of a limited range. This proves the inability of a C implementation to address an unbounded storage space. --(this comment by [[User:{{{2}}}|{{{2}}}]] at 00:27, 11 November 2009 98.243.106.85 UTC; please sign your comments with ~~~~)

There's nothing about C itself that says it needs to use two's complement integers (sign-magnitude and one's compliment can work, dc's source code even has a routine for that), or 8-bit bytes (the PDP-10 used bytes from 1-36 bits, usually 9), or even binary bytes (ternary, quinary, and decimal also work). For example, the IBM 1401 used decimal numbers not only for math, but for memory addresses. The "Tunguska" emulator has 3CC, a ternary C compiler. There's also no reason why sizeof(void *) has to equal sizeof(int) or sizeof(long) or why pointers can't be floats. Nvidia GPUs actually use float pointers[1] see: "Chapter 32 of this book discusses important limitations and errors associated with using floating-point rather than integer addresses, and those problems apply to the techniques presented in this section." The only problem is that C's pointer size depends on the size of the underlying computer, not the C language. Another possibility, if a computer supported bignum bytes, then it could still have a sizeof(void *) of 1, but that one "byte" can hold any integer value. An array of void * would then have a size of 1*(number of array elements), which can be infinity if it contained an infinite number of elements. And this is a rather interesting discussion about C pointers. Ian 22:21, 12 September 2010 (UTC)

Yes, I too have concluded that C is Turing-complete without the standard library, and with infinite-sized chars. (Of course, this only proves one particular variant of C Turing-complete -- C is actually a hugely varied family of languages in disguise, parametrised on a whole host of things.) Unfortunately, this cannot prove hosted C Turing-complete, because the standard library has the CHAR_BIT macro in limits.h. —ehird 18:32, 24 May 2011 (UTC)

Also, if you include the standard library, C is Turing-complete, even with a finite pointer size. The standard library is defined as part of the C standard, but itself cannot be implemented in pure C without inline assembly or non-portable compiler intrinsics (e.g. the <tgmath.h> and <setjmp.h> functions). With a file as a "tape" (on an unbounded storage medium) you can simulate a Turing Machine with FILE stream functions like fseek(), fread() and fwrite(). Functions like ftell() and fstat() are allowed to return EOVERFLOW if the file size or current position can't fit into the return data type. The only difficulty is that you can't fit the entire tape in memory at once (limited by SIZE_MAX) or seek to an absolute position. Ian 06:13, 24 May 2011 (UTC)

Yes, indeed, this is a viable way of proving hosted C Turing-complete. I think you can prove both unhosted and hosted C potentially Turing-complete (i.e. two members of the family, whose only difference is that one is hosted and one is unhosted, Turing-complete) using recursion and possibly setjmp/longjmp, but I'm not sure. —ehird 18:32, 24 May 2011 (UTC)

More incorrect

C is Turing-complete (but not its any implementation) because:

1. It is possible to write an interpreter of a universal Turing machine in C

OR

2. It is TC because its subset (e.g. without sizeof) is TC

Here is from http://www.iwriteiam.nl/Ha_bf_Turing.html

A language is said to be 'Turing-complete', if for each functions that can be calculated with a Turing Machine, it can be shown that there is a program in this language that performs the same function. There are basically three approaches to proof that a language is Turing-complete. These are:

1. Show there is some mapping from each possible Turing machine to a program in the language.

2. Show that there is a program in the language that emulates a Universal Turing Machine.

3. Show that the language is equivalent with (or a superset of) a language that is known to be Turing-complete.

--Oleg 06:28, 11 November 2009 (UTC)

Unbounded program length

If a language stores information in the programs source code (self-modifying) and is turing-complete except for the memory, and allows unbounded program length ("infinite"-stream too), is it turing-complete? --TehZ

If memory other than the source-code is limited, but in that case the read/write memory is in fact, unbounded, if it can read/write its unbounded source-codes? --Zzo38 19:58, 23 January 2011 (UTC)

I do not understand what is this

I know that a language is Turing-complete if you can compute any function with it. I thought that a function includes addition, substraction, multiplication and division. I was right?

A function reaches pretty far beyond the basic operations of mathematics. For example F(x) = x'th fibbonanci number or string concatenation is a function, which is computable, and so simulatable(as in, its result can be found, with some encoding of the data most of the time, since a turing machine itself only works on strings/symbols) in some form by anything turing complete. but im not the best explainer but I hope this helps. --Yayimhere2(school) (talk) 08:24, 30 May 2026 (UTC)

Ok, but now i not understand, what can do Turing-complete languages and how users create it.

a language is "Turing-complete" when it is able to simulate anything a Turing machine can. I don't know enough about TM's myself to give a good explanation, but there are ways to determine TC-ness:

• one way is to look at the language and see what it can't do. is it able to loop? does it have infinite memory (either space-wise or value-wise)? does it have multiple stacks? importantly, input/output and what exactly the functions do aren't necessarily important, just so long as you can prove that it isn't able to do something which a Turing-machine can—as a simple example, subtracting means you can't directly add numbers, but you can still add numbers in a roundabout way by subtracting a value from 0 and then subtracting by that negative number
• another way is to instead try and prove that a language can be translated to another already Turing-complete language—that is, there is some way of using its operations to emulate the existing behavior of another language. QX for example can be translated to brainfuck through clever usage of its commands; therefore, any brainfuck program can be emulated in QX, and since brainfuck is TC, QX is TC
• similar to above, you can instead try and interpret an existing TC language in the target language. I like to use Bitwise Cyclic Tag as a target language since it's very simple to implement across languages, but you can use whatever like Rule 110 or, again, brainfuck. for example, Countable has a program which is able to interpret Bitwise Cyclic Tag programs, and since BCT is TC, Countable is also TC (even if it is only through this one program, which it most likely isn't)

I hope this helps! other editors may be able to give a better explanation, but this is how I view it —aadenboy (talk|contribs) 14:25, 30 May 2026 (UTC)