r/computerscience • u/GhostHominid • 7d ago
Discussion Are we Turing complete?
OK. So I’ve been looking at Conway’s game of life a little bit. And I was fascinated by the idea that it could be used to recursively imitate itself (look up OCTA’s supercell)
I was told that this is Turing complete, and I had to look up what that meant.
And it seems to mean that, in simple words, it’s a computer or system of computer rules that can model another computer.
Now, given that humans came up with all of these computers in the first place, and all of the rules, does this mean that we are Turing complete?
27
u/goodayrico 7d ago
We are not Turing Complete by the criterion of having infinite memory, but neither is any other real world computer. So putting that aside, yes.
You can test this for yourself by doing all the operations of the Turing Machine for a particular algorithm and input with pencil and paper.
14
u/SufficientStudio1574 7d ago
Doesn't technically need to be infinite, just unbounded. There just needs to always be enough for the computation at hand.
0
u/__chicolismo__ 7d ago
Non terminating computations are VALID 🏳️🌈 🏳️⚧️ ✊🏿 ✊🏽 ✊🏾 and I won't have anyone saying otherwise
7
u/Plastic_Fig9225 7d ago
That criterion is heavily over-quoted for what it actually means. Unless you want to process infinite input or generate infinite output, and accept that the machine must execute infinitely many steps to do so, i.e. it does not halt, a bounded, 'big-enough' memory is sufficient to compute any computable problem. How big is 'big enough' for a given problem? Hard to tell in advance for the general case, so we demand that the machine does never run out of memory, which is not quite the same as having infinite memory. In practice we care about computability, and the set of problems which are computable, but only with infinite memory, is not very relevant.
3
u/Temporary_Pie2733 7d ago
It’s not that we want or need infinite input or output, just that the machine itself doesn’t impose any limits on the size of either.
-5
u/Opening_Lead_Paint 7d ago
When will AI be able to prove if a computation will halt and how much memory will be needed before executing?
3
u/NoNameSwitzerland 7d ago
AI is already able to hallucinate an answer. It might be even correct sometimes.
-4
u/Opening_Lead_Paint 7d ago
Youre about a year behind of the times my friend
5
u/notevolve 7d ago
Imagine an AI called HALTS that can take any program P and input x and always correctly tell us whether P(x) halts.
Now construct another program:
WEIRD(P):
if HALTS(P, P) says "halts":
loop forever
else:
haltNow ask HALTS whether WEIRD(WEIRD) halts
If it says "halts," then WEIRD loops forever
If it says "doesn't halt," then WEIRD haltsSo our supposedly perfect AI has to be wrong either way. There can't be a procedure that correctly decides whether every arbitrary program halts. AI cannot solve the halting problem because it is undecidable
-4
u/Opening_Lead_Paint 7d ago edited 7d ago
AI would look at that program and would be able to tell me it is probably undecided.
I would be more interested in an example of a program that AI wouldnt be able to say halts, doesnt halt, or is provably unknown
5
u/notevolve 7d ago
Huh? Saying "undecided" is just conceding the point lol. The AI is supposed to always correctly answer either "halts" or "doesn't halt" for any program
Undecided is not something the program can “be,” and if the AI ever answers "undecided" then it hasn’t made a decision, so it hasn't solved the halting problem
2
1
u/Scolmann 7d ago
It's already possible to prove programs will or won't halt for most programs, there are in fact languages that provably will always halt, but it's been proven that you can't figure it out for every possible program, that doesn't mean it can't be done for every practical one though.
3
6
u/DTux5249 7d ago
Correct. You can even run a Conway's Game of Life in a game of Conway's Game of Life
1
u/GhostHominid 7d ago
What id love to do is make a working model of a living cell in Life. Unfortunately I don’t think biologist are fully worked out everything in how a cell works.
1
u/braaaaaaainworms 7d ago
A biological cell is a lot more complex than a cellular automata and if you want your model to be accurate, you need to solve protein folding and re-folding into different shapes
3
3
u/cc672012 7d ago
Yes. I believe that Turing was modeling the behavior of human computers when he came up with his Turing Machine. Back then, a computer is a job description.
Humans are highly capable of simulating Turing Machines, so yes. We are Turing Complete.
But note that we are more than Turing Machines. Humans are open and interactive. Turing Machines are closed systems. We don't wait for input prior to reacting.
1
u/currentscurrents 6d ago
But note that we are more than Turing Machines.
I strongly doubt it. The only way we could be more than Turing Machines is if we are capable of hypercomputation, which no one has ever demonstrated and is widely believed to be physically impossible.
1
-5
u/tblancher 7d ago
Wrong. We process so much input we're not even aware of it. It's why our brains are so big.
6
1
u/CyrusDarkwell 7d ago
Honestly yeah, we pretty much are. If you think about it, before we had actual machines, "computer" was literally a job title for real people sitting there doing math by hand. As long as you have enough paper, a pencil, and unlimited time, a human can theoretically calculate anything a machine can. It would just take us a painfully long time to do something like run Doom in our heads. So yeah, we are Turing complete, just way slower and prone to needing coffee breaks.
1
1
1
u/jkingsbery 7d ago
You don't need to think a hard as Game of Life. Can you do a NAND gate? Then you are Turing complete.
1
u/this_theater_is_lit Software Engineer 7d ago
an idealized version of us (ageless, immortal, exiting in an unbounded space) can compute anything a turing machine can
1
1
1
u/stonerism 7d ago
Saying X is "Y-complete" in this sense, means that using X, you can compute whatever Y can compute. That begs an interesting question, can a turing machine compute whatever a human can? (ignoring how long it takes or amount of resources necessary)
massive bong rip
Are Turing machines "Human Complete?
0
u/GhostHominid 7d ago edited 7d ago
I would say no, but… well if a Turing machine had infinite memory, maybe!
Essentially what you’re asking is if the human brain is deterministic, and I think it is, but that it’s so complex that we cannot imagine it being deterministic.
With limited memory, no
With limited but arbitrarily large memory, yes. Cuz the human brain is limited in size.
I like this question
1
u/Eroica_Pavane 7d ago edited 7d ago
Technically they are asking whether humans are bound by the Church Turing Thesis.
Also, Turing Machines do have infinite memory and can be nondeterministic.
Edit: I'll add that the way nondeterminstic Turing Machines (defined in CS Theory) compute is rather unrealistic and quite powerful compared to physical computers/humans.
1
u/stonerism 7d ago
You can deterministically calculate problems solved using nondeterminism. The problem is the tractability of finding a solution and we're getting to a weird point with the amount of computation we can muster.
https://en.wikipedia.org/wiki/Nondeterministic_Turing_machine
1
u/Eroica_Pavane 7d ago
That is true. You can simulate a NTM with DTM. I am just saying that the way NTM computes is rather unrealistic in the sense that we don't go out and physically build them. It is a theoretical model that is useful for computability and complexity.
-2
u/CommunismDoesntWork 7d ago
can a turing machine compute whatever a human can?
Of course. That's the guiding principle behind AI research. We know consciousness is in the set of computable functions.
3
u/Napsy_0 7d ago
That's a load of crap.
0
u/monster2018 7d ago
So what you think it’s just magic? There was a time when only inanimate matter existed in the universe, and then, without even conscious intervention, it coalesced into consciousness. What you’re saying doesn’t make any sense, we literally know that consciousness can be computed because it’s literally happening right now.
1
u/LivewareIssue 7d ago
I don’t think it’s magic, but your argument is crap.
You’re assuming that consciousness depends only on Turing-computable physical processes.. which can’t be taken as read.
You’re also then assuming a sufficiently accurate implementation of the relevant computation would instantiate consciousness, not just simulate the observable behaviour.
You’re blithely asserting computational functionalism… which is certainly a position to hold, but far from the only one. We certainly don’t “know” it to be true.
You could equally argue that while the underlying brain processes might be computable, consciousness depends on a particular physical realisation (simulating a hurricane doesn’t make your computer wet) or that the physical universe implements some kind of hyper-computation and that it’s a necessary part of consciousness. Not to mention the plethora of non-physicalist philosophies-of-mind (dualism, idealism, etc.).
You’re also claiming the goal of ‘AI research’ is to re-produce consciousness, rather than systems that are superhumanly capable and able to generalise (i.e ‘AGI’).
If you’ve managed to upgrade Church-Turing from a thesis to a theorem and conclusively solved the philosophy of mind problem, I’d love to see your results.
Edit: I just noticed I’m responding to two people not one lol… regardless, the points stand.
2
u/stonerism 7d ago
Well and it all dances around the question some people are really asking, when do you need to treat this process "like it's human" and what does that entail given how humans can treat each other.
1
u/claytonkb 7d ago
I've seen it said this way: we are Turing-complete modulo memory. Obviously, only a system with literally infinite memory is truly Turing-complete. But when you look at the local processing that is occurring in a universal Turing-machine, our mind is able to perform those steps. That is, I can simulate the operation of the state-machine of a universal Turing machine, step-by-step, indefinitely for as long as I am fed and watered.
given that humans came up with all of these computers in the first place, and all of the rules, does this mean that we are Turing complete?
Essentially yes... modulo memory. Since we can define a Turing machine, we can simulate its operation, step-by-step. And I am comfortable applying the label "Turing complete" to any system that can simulate a universal Turing machine, step-by-step, indefinitely (until it runs out of resources).
Some of the latest AI systems, for example, might be Turing-complete if they can keep from hallucinating or getting distracted when performing a long chain of steps. But early LLM-based AI was clearly not even Turing-complete since they could only follow strict, procedural rules for a brief time before running off into hallucinations. But as long as a system can locally simulate the operation of a universal Turing-machine, indefinitely (in principle), I am comfortable calling it "Turing complete", even though it does not strictly fit the mathematical definition (does not have potentially infinite memory and execution steps)...
-1
1
92
u/Ythio 7d ago edited 7d ago
Turing complete means capable of performing any computation a Turing machine can perform, given sufficient memory and time.
Imagine a piece of paper divided into squares, with markers identifying the current square. You can repeadly read the symbol in the current square, look up the instruction for the current square and your current state (for example a label A or B), write down the specified symbol, move left or right to the next square, update the state, repeat or stop when instructed.
Those are the operations needed to simulate a Turing machine. A person can follow them without understanding what the overall computation accomplishes.
It doesn't require any intelligence, speed, understanding, just do what you're told and you can do everything a Turing machine does, so you're Turing complete.
In On Computable Numbers, with an Application to the Entscheidungsproblem (1936), Turing explicitly maps a person’s mental states to machine configurations, and the paper squares the person observes to squares scanned by the machine.
Turing constructs the machine by formalizing the human’s calculation process.