Linked Questions

4 votes
0 answers

Is every von neumann machine turing complete? [duplicate]

I understand that TM is a 'Model of Computation' which tells us about the computational power of a machine while Von Neumann Architecture is a 'System Architecture' that tells us about how the machine ...
codecasterz's user avatar
0 votes
0 answers

Is C actually turing complete follow up [duplicate]

I am picking up from this thread for which I have no privileges to comment on: Is C actually Turing-complete? I was wondering if there's any progress on this and what the conclusion actually was. ...
user100814's user avatar
181 votes
13 answers

Why, really, is the Halting Problem so important?

I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine ...
Brent's user avatar
  • 2,543
27 votes
7 answers

Are all turing complete languages interchangeable

Note, while I know how to program, I'm quite a beginner at CS theory. According to this answer Turing completeness is an abstract concept of computability. If a language is Turing complete, then ...
touring's user avatar
  • 289
11 votes
4 answers

Does our PC work as Turing Machine?

Does our PC work as Turing Machine? The model of a Turing Machine consists of infinite memory tape, which means infinite states. But suppose if our PC has 128 MB memory and 30GB disk it would have ...
siddstuff's user avatar
  • 273
4 votes
1 answer

Time complexity of arithmetic operations

I want to calculate the time complexity of the listed algorithms, please correct if I'm doing something wrong: The question is, do some operations like multiplying, dividing, or plus really affect on ...
Michael's user avatar
  • 41
1 vote
4 answers

To what extent is an x86 machine equivalent to a Turing Machine?

To what extent is the abstract model of computation specified by the x86 language Turing complete? The above question is related to this question: Is C actually Turing-complete? In theoretical ...
polcott's user avatar
  • 87
0 votes
4 answers

Grammer Class/Production Rules of Programming Languages

I'd read around on the interwebs, and a lot of the text indicated that many programming languages are generated by a context-free grammar, which leads me to 2 questions: Doesn't variable scoping ...
Mr. Minty Fresh's user avatar
2 votes
1 answer

What was the first Turing-Complete programming language?

What was the first turing-complete language? Know about the first machines and computers, but not the programming language.
MSnts's user avatar
  • 23
2 votes
2 answers

How do we define the term "computation" across models of computation?

How do we define the term computation / computable function generically across models of computation? Beginning with the textbook definitions of: {Linz, Sipser and Kozen} for "computable function&...
polcott's user avatar
  • 87