Hacker News Reader

Comment by milancurcic | Hacker News Reader

> I haven't touched any later standards after 77; is Fortran still technically not Turing complete?

Fortran has been Turing complete since its inception in 1957 :).

The argument against f77 being Turing-complete is that you can't dynamically allocate memory, or specify infinite arrays, or recurse. You have to declare a finite size for everything. So a program embodies a fixed limit on how big a problem it can handle.

In C (the abstract machine with arbitrary-sized ints) you can allocate an arbitrary amount of memory. It may, of course, not run on any given machine. But the language itself allows it.

If that makes F77 not Turing-complete, nor is C. There is a finite amount of memory you can allocate in C, since a pointer must have finite size, implying there is a finite number of things it can point to.

The C language specification doesn't require a pointer to have finite size. Just because every C implementation has a limit, it doesn't mean the language itself does.

Doesn't it imply that it must be finite, because you can use sizeof() to find its size, which yields something of type size_t, which has maximum size SIZE_MAX?

The idea is that theoretically a perfectly portable C program could be written and work on problems of any size given sufficiently large hardware and a compiler implementation that takes advantage of that hardware.

Unlike a Fortran77 program, a portable C program doesn't have to change to support orders of magnitude changes in problem size.

You did not answer the question of SIZE_MAX being the limit. So here it is once again:

> Doesn't it imply that it must be finite, because you can use sizeof() to find its size, which yields something of type size_t, which has maximum size SIZE_MAX?

You could take the exact same C program and run it on a compiler+computer with sizeof(void *) == 64 or 128 or 1000000, and it should handle a correspondingly huge problem.

I am not sure that would be valid. You could also use a defined constant as the limit in the Fortran program. In other words, you could argue that SIZE_MAX is part of the program, the same as the Fortran array size is defined in the program. But I am not sure it would be invalid either... just wondering.

Wouldn't it be possible to, with a really strange number format for integers, define SIZE_MAX as INFINITY? C doesn't require twos-compliment numbers, after all.

> Wouldn't it be possible to, with a really strange number format for integers, define SIZE_MAX as INFINITY?

That's a very interesting question that got me thinking for quite a while and the only conclusion I reached is that you deserve an upvote.

f90 introduced recursion and allocatable (dynamically sized) arrays.

So (in reference to tombert's comment), f90 and beyond doesn't have those limitations. It also introduced conveniences like operator overloading and element-wise array operations, so I think it's a really simple/convenient language for basic scientific computing, if you want to code up some algorithm. That said, I always reach for Julia instead.

Fortran can read and write arrays to disk so I think that satisfies Turing equivalency.

Reply on news.ycombinator.com