Can a programming language without arrays be turing-complete?

Posted by Ring on Stack Overflow See other posts from Stack Overflow or by Ring
Published on 2010-05-02T15:12:16Z Indexed on 2010/05/02 15:17 UTC
Read the original article Hit count: 138

Filed under:

turing-complete

|

language-agnostic

My question is simple:

There are no arrays possible. That means you can address variables only "statically" by directly using their unique name. (This already throws out the default array syntax variable[ index ] and variable variables)
"Emulated arrays" are counted as arrays and excluded too. Examples: You could basically simulate arrays using strings (quite easily actually) or use variable variables as in PHP.

Can such a language be turing-complete?

Brainf*ck for example has arrays, in fact it is one big array, isn't it?

© Stack Overflow or respective owner

Related posts about turing-complete

Is CSS turing complete?

as seen on Stack Overflow - Search for 'Stack Overflow'
CSS isn't, insofar as I know, Turing complete. But my knowledge of CSS is very limited. Is CSS Turing complete? Are any of the existing draft or committees considering language features that might enable Turing completeness if it isn't right now? >>> More
Turing-Complete language possibilities?

as seen on Stack Overflow - Search for 'Stack Overflow'
In every Turing-Complete language, is it possible to create a working Compiler for itself which first runs on an interpreter written in some other language and then compiles it's own source code? (Bootstrapping) Standards-Compilant C++ compiler which outputs binaries for, e.g.: Windows? Regex Parser… >>> More
Code Golf: Shortest Turing-complete interpreter.

as seen on Stack Overflow - Search for 'Stack Overflow'
I've just tried to create the smallest possible language interpreter. Would you like to join and try? Rules of the game: You should specify a programming language you're interpreting. If it's a language you invented, it should come with a list of commands in the comments. Your code should start… >>> More
Practical non-Turing-complete languages?

as seen on Stack Overflow - Search for 'Stack Overflow'
Nearly all programming languages used are Turing Complete, and while this affords the language to represent any computable algorithm, it also comes with its own set of problems. Seeing as all the algorithms I write are intended to halt, I would like to be able to represent them in a language that… >>> More
What is Turing Complete?

as seen on Stack Overflow - Search for 'Stack Overflow'
What does the expression Turing Complete means? Can you give a simple explanation, without going into too much theoretical details? >>> More

Related posts about language-agnostic

Are there any language agnostic unit testing frameworks?

as seen on Programmers - Search for 'Programmers'
I have always been skeptical of rewriting working code - porting code is no exception to this. However, with the advent of TDD and automated testing it is much more reasonable to rewrite and refactor code. Does anyone know if there is a TDD tool that can be used for porting old code? Ideally you… >>> More
Language Agnostic Basic Programming Question

as seen on Stack Overflow - Search for 'Stack Overflow'
This is very basic question from programming point of view but as I am in learning phase, I thought I would better ask this question rather than having a misunderstanding or narrow knowledge about the topic. So do excuse me if somehow I mess it up. Question: Let's say I have class A,B,C and D… >>> More
Language-agnostic term for typed things that need memory

as seen on Stack Overflow - Search for 'Stack Overflow'
Is there an accepted general term that subsumes the concepts of variables, class instances and arrays? Basically "any typed thing that needs memory". In C++, such a thing is called an object, but I'm looking for a more language-agnostic term. § 1.8 The C++ object model 1 The constructs in… >>> More
Deprecated Methods in Code Base

as seen on Programmers - Search for 'Programmers'
A lot of the code I've been working on recently, both professionally (read: at work) and in other spheres (read: at home, for friends/family/etc, or NOT FOR WORK), has been worked on, redesigned and re-implemented several times - where possible/required. This has been in an effort to make things smaller… >>> More
Coding Competition, language agnostic guidelines?

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi there: I might be doing a coding competition soon, I was wondering if anyone made one and what where the guidelines/ process. I'd like to make the competition appealing to all devs, and I m trying to come up with ideas as to how. the scenario is: There is an event running and we(of the coding… >>> More