CSS Turing Machine • Hacker News Board

Re: CSS Turing Machine

#21

Post by roywiggins » Fri, Jan 15, 2021, 5:02 PM UTC

Aardwolf wrote: post #13

saagarjha wrote: post #12

Earlier quoted context omitted.

(This is also why C is not Turing complete.)

Does there exist any formal terminology for "something that is like a Turing machine if it would have infinite memory"? I'm asking because since the true definition of a Turing machine requires infinite memory, in theory nothing can be a Turing machine in the observable universe, so this definition doesn't help describe anything that's used in practice. On the other hand, there's an obvious difference in power of a l…

You can assume that, if the machine runs out of memory, that someone comes along and installs another gigabyte and sets it going again. Predicting whether programs will halt under those conditions is exactly the same as if they really had an infinite tape.

It's a bit tricky with real programs because eventually you might expect you'd run out of address space, so you might have to relax constraints and say that at least some integer types don't have a defined maximum value, or stuff like that.

Re: CSS Turing Machine

#22

Post by ivanbakel » Fri, Jan 15, 2021, 5:35 PM UTC

Item_Boring wrote: post #19

ivanbakel wrote: post #17

Earlier quoted context omitted.

Abstract register machines are normally considered to have infinite memory - because even though the number of registers can be bounded, their size is often not. Unlike the fixed-width registers of a real CPU, abstract registers are typically capable of storing any positive integer.

I’m aware and that’s how they are usually introduced. However, there’s also the model of such that have a further restricted set of instructions and only have limited memory.

Could you please give a reference for such a model, and the proof that it's Turing complete? I don't see it described on the Wikipedia page, which explicitly states that registers are unbounded.

Re: CSS Turing Machine

#23

Post by ivanbakel » Fri, Jan 15, 2021, 5:40 PM UTC

weare138 wrote: post #18

arcticbull wrote: post #8

Earlier quoted context omitted.

Without speaking for the OP, it seems like the case being made is not that the result is executed on a real, finite machine approximation (as all programs are) but that there exists an abstract Python machine wherein the memory does not need to be so described. This does not exist for CSS.

> that there exists an abstract Python machine wherein the memory does not need to be so described This is getting a little esoteric. Python interpreters are created in other languages like C where memory does need to be described. How can this 'abstract Python machine' even be implemented? Python or any higher level interpreted language will always have the same limitations of the language it's implemented in and li…

>How can this 'abstract Python machine' even be implemented?

It wouldn't be - the machine is abstract. It exists only in terms of a mathematical model, that describes how Python code behaves in a defined mathematical way (its semantics). The real implementations of Python should have the same behaviour as the abstract machine, but the property of Turing-completeness really only exists for the abstract version - the real versions, being bounded in memory, are limited to certain sizes of programs.