Turing Machine Alternative (Counter Machines) - Computerphile
ฝัง
- เผยแพร่เมื่อ 30 ก.ย. 2024
- Computing with counters. How "counter machines" are as powerful as turing machines, albeit slightly more convoluted! Dr Christopher Hampson, Senior Lecturer in Computer Science Education at KCL explains.
EXTRA BITS: • EXTRA BITS - More on C...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottsco...
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
The other half of this would be to show that every counter machine can turn into a turing machine. That's left as an exercise for the reader.
That's only required if you want to show that Turing machines are at least as powerful as counter machines. The video does show that counter machines are (at least) as powerful as Turing machines.
And all you actually need to show is that any computational model which Turing machines have already been shown to be able to simulate can simulate counter machines - for example, an idealised PC (one with unlimited word size and memory). And it's pretty obvious that an idealised PC can do everything that's required in order to simulate a counter machine - you need to store a finite number of values (the bags) and then each step is either adding 1 to a specified value and going to a specified next step, or attempting to subtract 1 from a specified value, either detecting it's already 0 and going to a specified next step, or actually subtracting 1 and going to a specified next step.
In general, if you can describe a machine well enough for someone else to be able to create and run it without any ambiguity, that's already strong evidence that a Turing machine (or equivalent machine) can simulate it.
I think he already demonstrated everything you need for Turing completeness.
@@rmsgrey If a counting machine can be simulated by a Turing machine, and a Turing machine can be simulated by a counting machine, then is there a way to determine which is simpler, or if both are functionally equivalent, or if, as the title of the video suggests, they are equally valid alternatives?
@@menachemsalomon It depends what you're looking for to count as simplicity.
In terms of what each can calculate, the two are equivalent.
In terms of describing the machine type, a counting machine is simpler - each node either: halts; increments a specific bag and then goes to a specific next node; or attempts to decrement a specific bag and goes to one of two specific next nodes depending on whether there was anything in the bag to remove. Meanwhile for a Turing machine, each state needs to have an entry for each possible symbol, specifying which symbol to write, which direction to move, and which state to enter.
In terms of using them to perform computations, or to prove things about them, in general, which is simpler to use is going to depend on the specific task.
@@jack8n Counter machines can have an infinite number of counters, but only a finite (but arbitrarily large) number of bins - a bin can only be accessed when it's directly named by a specific state of the machine, and a machine is only allowed a finite number of states, so it can only ever make use of a finite number of different bins - at most, as many as there are states.
On the other hand, the video demonstrates how a counter machine can simulate a binary Turing machine with just 4 bins.
I think it's irritating that both the pieces and the containers are called counters.
I tried to count the number of times he said "counter" but suffered an integer overflow.
Haha, you could also try to count the occurences of “so”😄@@SteveAgland
I sounds like a British thing. I suspect Americans would use less-ambiguous word.
Buttons, lentils, shells, matches, drafts, ,bottle tops, raisins...
Bags, cells, boxes, pots, containers, stacks, variables...
I just realised this is literally easier Brainfuck with no i/o:
+ : add a counter
-: remove a counter
[: check if counter is 0
]: a computer friendly way to close the loop in the phase diagram
>
It's so weird to call it "Counter Machine" but we can't actually "count" the number of elements inside every container. I'd rather call it "Stack machine" because its behaviour is similar to a stack ("push" and "pop").
I agree, it's not very counter intuitive. And that in itself makes nonsense of my previous sentence. We seem to have a halting problem just with its name. :)
A stack machine sounds more like a name for a Pushdown Automaton. These don't really have the LIFO property of a stack.
Stack can hold different types of things, not just a number. This is much stricter than stack since there can only be numbers. Since it is just a number, push and pop does not really apply here. So it does not really have LIFO property like @cadekachelmeier7251 said
A stack holds multiple items, this is just one item of which the value is incremented or decremented with each operation. And that is indeed counting (up or down).
@@IngieKerrhaha nice one!
Chris was the single best lecturer that I've ever had (and probably will ever have). Broke down problems in a way that everyone could understand. Glad to see that his streak of amazing teaching continues!
Looking forward to more videos with him!
He supervised my disseration! Was great :)
He was also my lecturer, always explained the hardest concept in the easiest ways and always made the lectures engaging and fun!
He turned my hate towards discrete maths into curiosity
This is sounding more and more like Brain#@(
i think it's literally some brain#@(< dialect
This has been implemented for 30 years as the esoteric language "Brainf*ck".
I was about to comment that this reminds me of brainfuck
Using the right candy as counters, this seems like a delicious alternative, though more prone to data loss.
Turing was amazing. Thanks for this counter example!
Sounds like you need to go to Church.
@@cadekachelmeier7251what?
It is an example using counters not an example that counters some logical statement.
@@keepyoursins It's just adding to the silly pun. Turing machines were developed at the same time as Lambda Calculus, developed by Alonzo Church. The Church-Turing thesis says that they're equivalent.
It can emulate a Turning machine, so it is a Turing machine ... it's not a counter example, it's another type of computing system that has been shown to be Turing compatible
For double, why not double on the write rather than the read? It would be almost half the number of overall operations.
It's like using the Tower of Hanoi to compute!
So both the containers and the value units are "counters"?
I'm another person who immediately thought brainf*ck. The counter machine has some capabilities that bf doesn't have, like 'break'. An interesting tidbit is the isomorphism between bf and a language Corrado Bohm invented in the 1960s while simplifying Turing machines. This language shows up in Bohm and Jacopini's proof of the Structured Programming Theorem.
This looks functionally a bit like the destructive read of core memory in very early computers.
It should be noted that by "outperform" he means "compute a result that a TM can't" -- not "run faster" because TMs are notoriously inefficient.
If it can compute a result that a Turing Machine can't .... that also includes every computer on earth ... and that's not likely ...
TMs are Turing-complete by definition, so it means they can compute anything that is computable.
@@oleonardohn
You seem to have reversed the definitions of "computable" and "Turing machine". A Turing machine is just a particular kind of state machine that operates locally on a mutable string of arbitrary size. The term "computable" is defined to mean "can be computed by a Turing machine", not "can be computed". In practice, these two definitions seem to be equivalent because -- despite decades of trying -- nobody has ever devised a state machine that cannot be simulated (however slowly) by some Turing machine, but to the best of my knowledge, nobody has actually proven that no such machine could exist.
@@dragonrider7225 We can also go with the definition that something is computable if and only if there is an algorithm that describes it. Despite being equivalent to the definition you provided, it also implies that supercomputation would require at least an infinite amount of steps.
@@oleonardohn okay than, please compute while(true){}; for me then. I mean, it's certainly an algorythm that describes something, just not a very useful or interesting one.
Best lecturer I had at KCL. Always a pleasure listening to him!
In the video, it was stated that the tape of a Turing machine is infinite. If so, how would a counter machine be able to hold decimal representations of the binary numbers to the left and right of the current location?
The formal definition of a Turing machine states that its initial state (the initial content of its tape) is a finite sequence of symbols. Hence, while the tape is defined as "infinitely extendable left and right" and the content of the tape can grow arbitrarily large, the tape cannot hold an infinite sequence of symbols, since generating such a sequence from a finite initial sequence would require an infinite number of steps. There will always be a finite sequence of symbols left and right of the head.
23:30 It can slide to the left, and it can slide to the right, but can it do three hops this time?
How he describesld a counter machine works kind of reminds me of when I built an 8bit binary adder with a 1bit carry out with Redstone NOR gates in my survival world. It was so tiring and resource intensive I didn't want to added hardware bitshit or bitwise operators, so I looked up the Arithmetic algorithms and converted the multiplies/divides to repeated add instructions before working on a clock, program counter, and memory.
I never got around to connecting the components up, but I think with the 10hz limit of redstone bitwise not would be slow since the algorithm was (X*-1)-1 either required adding 255 (-1 in 2s complement) X number of times the easiest to program (this took X+1 number of add instructions) or faster if you knew it was an even or odd number you'd perform a series of left bitshift by doing X = X + X and interwoven between those bitshifts you add either 1 if it was an odd number or 2 if it was even either way once you got -X you'd add -1 or 255 to get X's bitwise not (worst case for this was 14 add instructions to get -X not including any method to determine odd or even before hand the best I could figure was copying the value you want to bitwise not and bitsifting it 7 times to left and seeing if the output was zero for even or 127 for which took another 7 add instructions plus memory instructions, then it took a final add instruction of -1 or 255 for at least 22 instructions).
That's very similar to the Brainfuck programming language.
You could check if it's 0, if it's not it is 1, as de actual register can only contain a 1 or a 0 in a touring machine, I don't get the extra step of subtracting one and adding it again...
It's a quirk of the formalism that wasn't well explained. There isn't actually an "empty?" operation. Instead, every operation must either add or remove a count, and for a remove operation you can go to a different state depending on if it succeeded or failed.
Because a Counter Machine has no way of simply reading data, it must see a zero or move the bit somewhere, otherwise it would be lost.
Remember, this is only a theoretical concept, not meant to be used in the real world, and would be worse than useless if you ever tried.
@@l0zerth I am familiar with this kind of theoretical computation, just took the rules from what was said in the video. If you could check for 0, you can check for something, but not knowing how much it is(if checking for 0 fails, or it's false).
As I understand now that's not the case, it's only after changing the value that it could be done, or something like that, not just checking by itself.
Of course it's ridiculous to implement, to then try to do with millions of states what a SIMD can do in one execution...
@@joaquins90 I've heard of counter machines before, and gone through a similar primer to this, many years ago, so I only vaguely remember the rules and properties, of which this only introduces the most basic.
A Turing Machine can directly store a discreet value, which can be non-destructively read at any time, as the data is on magnetic tape in the fundamental concept.
Counter Machines store "actual" tokens in discreet batches and performs operations on them, and has to count them every time, with the desired or questioned answer being the exit of the operation. Those tokens have to be moved or they are lost, just like counting the glass drops if you can't see them, which a CM cannot, as the data would be stored in more of a modern solid state concept.
I'm not sure I understand read. If it is a state machine, you read a 0, and you know it is 0. Answers is 0. If you are reading a 1, subtract 1, add to the temp, check if 0... is that part of a loop? If it isn't 0, how do you handle that bad state? If after moving to temp you move temp back to the head, you now branch how? The state of zero or one isn't really maintained as far as I can tell, so there isn't a branching which isn't part of the read subroutine.
I believe the example of copy from c2 into c4 has a slight error. At the beginning of the procedure there is no garuntee that c4 is empty so we must begin by emptying that counter using reset(c4).
It was implied that the counter is reset before use. This is true in a computer - one needs to reset or write a fixed number to the register(s)/memory before use.
These models assume that all counters / registers are initialized to 0.
@wybird666 thanks for the clarification, I must have missed that
one thin i didnt understand is, why cant you just check if a counter is in it instead of taking one out, checking if it is empty and then adding it back, especially if there is only one or zero
You can, but you need an extra elementary instruction. There is no fundamental difference. These machines are meant to be simple, efficiency is not a criterion. Anyway he showed that you do not need this type of 'how many are in the bag' instructions because the elementary instructions and one temporary bag are enough for an algorithm to perform that function.
In order to save that counter element, you have to move it somewhere else, thus the temp counter "bag", just like if you're cutting and pasting, the days had to be stored in RAM during the process.
This way of emulating a Turing machine does not preserve polynomiality of algorithms. Is there a way to use counter machines that does?
If we're looking for simplicity in hardware and want to implement logic gates the single gate, NAND, is enough. All the 2-input 1-output logic gates can be built by composing NAND gates. So all the Turing machine (or counter machine) logic can be done with NAND.
If looking or simplicity in software one logic will do. The "While ( is true) DO END" is sufficient. All the if, if-then, do while, do until, case, and so on can be constructed from this one logic.
The logic for the human condition:
While (Alive) If not content do something else.
When I saw the title I thought that it was a machine to 'counter' the Turing machine.
Turns out that that is about the only meaning of 'counter' _not_ used in the video.
This counter machine has the same analogy for the axiom of choice with bags and marbles like the the axiom of choice. In a way this counter machine assumes the axiom the choice by being able to collect any element from each set to form a new set even if temporarily.
The axiom of choice is only needed for infinite sets though.
This looks very similar to a Petri net
I wonder if there's any use for a probabilistic version of this, where you do indeed have different colours of counters, and you pull out a random counter from each bag and can make choices based on the colour of the counter too.
why would you do that
@@MrDobozwhy, for the glory of Satan of course!
@@OlliWilkman probably
How many people wanted to mark that last empty counter as "P0" ?
This is basically Brainf*** but without the explicit pointer movement.
Everybody likes brainf*ck. They should teach it in schools. It is also pretty doable to make hardware that can run a bf program stored in memory.
When I was learning computational theory, the way I distinguished regular from context free, and context free from other decidable languages was always by thinking of how many things could be counted (and uncounted). An NFA or CFL can count and uncount one thing, meaning a^k b^k is a CFL because you count k a's then uncount k a's, a^k b^k c^k needs to count k a's then uncount k a's, and also count k c's, therefore not a CFL.
...so how many fellows at the Computing Dept are regulars at the local garden store (with all these pebbles around)? ;)
So in simpler terms, a counter machine just uses a series of queues
Interesting concept, buy please, check BEFORE subtracting.
enjoyed the vid, but couldn't stop clenching every time Chris' sleeve came close to the marker tip.
that's just brainfck lol! just named states instead of [ square bracket loops ]
Did I just watch an academic program a BrainFu*k analog with glass pieces?
This feels like the middle connection between a regular turing machine and brainf*ck
Reminds me of Church numerals.
4 minutes in, and I'm pretty sure he's describing brainfuck.
The problem with this machine is that most operations on a computer are counting and comparing operations. Here this is the slowest operation of them all :D
The point is to have a model as simpel as possible while being defined with mathematical rigour so one is able to apply mathematical reasoning to it.
Here you have only three operations: addition by 1, (arithmetical) substraction by 1 (you can not go below 0) and test for 0 with two different jumps depending on the result.
@@lovealien43so it's a mathematician's language: theoretically bulletproof, beautiful in its simplicity, and absolutely and completely useless in reality.
@@l0zerthit’s not useless it’s for studying the nature of computation itself. Which is very useful.
The main complication that really isn't explained is you need a counters to keep track of which state the turning machine is in and then move left/right and add depending on what is there. You could just have a routine that keeps on taking off counters from a stack c4 and shunts of at say count 1 etc depending if it is empty, that then does a move left/right and add or remove from c2 and then sets the next state by adding x counters back to c4 and looping again.
As someone else asked already, isn't a counter machine just a turing machine with a different encoding?
Yes. And they're both Lambda Calculus with a different encoding. And the Game of Life with different encoding. And Rule 110 with different encoding.
You have no tapes and moving tape heads. Both models can be mapped by enumerations between natural numbers and words of finite length over some alphabet, which you probably mean by encoding.
isn't everything?
A lot of such research is not to find anything vitally novel or "better", but to find models that might identify those in the wild which we didn't know were already Turing complete, and therefore programmable or hackable.
My personal favourite "machine" of this type is the railway layout using a single train, two types of points, and track capable of connecting them, which is Turing complete.
The points have a root and two branches. Entering from either branch always leaves by the root. For lazy points, that also sets the point so entering from the root will leave by that branch (in the initial state they will be preset to one or other direction). Sprung points always send the train to the same branch when entered from the root.
So the counter I built in Minecraft is actually turing complete haha
Doesn’t this only work if you’re using a finite tape for the TM though? With an infinite tape you wouldn’t be able to reverse the digits to the right of the read head to know how many counters to put in C3…
The tape starts with all zeros.
This means that after a finite amount of steps there are finitely many ones, and finitely far away.
Another way to put it: let's say a Turing machine writes a 1 then goes forever to the left. In the first step to the left, a counter will move from C2 to C3. Then after each subsequent step to the left, C3 will be doubled.
the infinite tape is the reason you have to "flip" the right side. you read from left to right, and write it down from right to left. but if you don't get it, just fold the tape over where the read head is and see how it changes the machine. spoiler, it doesn't
Time to make a bag building boardgame out of this XD
mancala is almost there already
This reminds me of "The Little Man Computer". I came across it last year. It was a paper computer concept used to explain how computers work.
There is one thing I didn't understand, so the Turing Machine has usually a well defined set of n states, that decides on reading a cell and if it should change the value, what state change to, and where to move. How does the counter machine do that? I see that you can map 1:1 the actions of a turing machine to a counter machine, but how do you translate the states of the turing machine into the states of the counter machines?
I guess you can have extra bins representing each state and you can read the current state by checking which one is empty, change state by adding 1 to the current state and clearing another bin, now that's the active state, and there you have it.
also if you really don't like wasting an infinite bin for every state, you cold multiplex a few bins, to have let's say 16 different states with just 4 extra bins, although that would make changing states a little bit more difficult.
the state bins tho really don't need to be infinite, they can be just binary flags as you would use them like so anyways
To me it seems that a counter machine is a programming language for a Turing machine.
Or the other way around. That just wasn't shown.
...but what's the advantage of Counter Machines??
XKCD: 2556
Usually with such computational models, it's about the ability to _recognise_ some arbitrary system S as being Turing complete.
i.e. if you have a model such as the above, and then you realise some emergent system has the capability of being such a Counter-machine, then that system is likely programmable, then you can extrapolate that this system S might be able to operate as a malware.
Or you might be able to play Doom on it. :)
Imagine, say, a situation by which some exploratory user of a device, could by entering an erroring value, increases some counter somewhere - and if that counter overflows then _something_ happens somewhere else. Maybe there's a few of these situations due to some developer oversight of overflow or something.... then by a series of "cunning moves" some user _might_ if the conditions were right, find a counter machine, and then, somehow program this counter machine to perform an operation....
So I'd say the moral is to look for machines everywhere... and then ponder about who might be able to program them, for bad reasons, or perhaps for good :)
Sometimes it's easier to prove things in counter machine. Same way we have thousands of programming language, each is turing complete yet tacking the same problem differently.
It's purely a theoretical thought experiment, only useful for analyzing other thought experiments.
This would be worse than useless in reality.
I used to use those counters to play Magic the Gathering
I think he made a Turing Machine emulator using a Counter Machine, and its performance is probably bad.
That was literally the whole point of the video, and no probably about it, Counter Machines are a purely theoretical thing that would be worse than useless in reality.
If a counter machine can emulate a Turing machine then it is Turing compatible ... and is universal
....this video shows, in depth, it is ...
The advantage of a counter machine is in at least some cases it is more efficient
It is pretty easy to make a Turing machine behave like a Counter machine (especially a Counter machine with given finite number of counters). There is a little catch that your counters need to be able to count to infinity on the infinite Turing tape. This can be arranged, for example, by interlacing the bits of the various counters.
Efficiency play no role in these examples. If you want efficiency you first have to define a measure of efficiency which will greatly vary depending on potential hardware and the type of problems to solve.
@@richardbloemenkamp8532 I agree efficiency makes no theoretical difference ...
and efficiency depends on what you are measuring ...
Which is why I said that in some cases a counter machine is more efficient than a turning machine... Turning machines are notoriously inefficient, and counter machines are often more so ..
But both are inefficient for real world problems
@@davidioanhedges yeah neither can make me sleep in time. if anything, they keep me awake lol
A turing machine also has a set of states it is in (start state, end states and as many others as needed) as well as a transition function that moves the machine between the states and the head. This aspect was completely ignored in the video and its pretty big. Obviously it does not change the fact that a counter machine is equivalent to a turing machine but it would have been nice to see how the reduction really works. A followup video?
Yeah the video kinda sweeps that completely under the rug, which is weird because without the controller state machine the Turing Machine would just be a big dumb infinite hard disk with absolutely no logic at all.
It appears that the video implies the Counter Machine also has a finite state machine, since the lecturer starts drawing one when he explains the various procedures. You translate each state of the Turing Machine into a set of states in the Counter Machine that transforms the Counter Machine's set of counters in the same way the original state transformed the Turing Machine's tape.
The Turing machine states directly map to counting machine states. The counting machine would just have a few additional intermediate states for each Turing machine state transition in order to perform the necessary operations.
You would basically take the state graph of the Turing machine, translate each state transition operation as shown in the video and then use the end states of one translated operation as starting states for the next ones.
I thought double can be copy, then adding the copies
That would have the same effect, but the implementation in the video only requires one additional register. Using copy requires two.
I find the Turing machine argument compelling because it makes the point that universal computation is possible. But... once you've got such a proof of concept, you don't really need another one. Once you've established "possibility," then the goal becomes "efficiency," and this certainly doesn't seem to buy you much there. It's so easy to just "clear" a counter, and so easy to just add and subtract, etc.
3:58 and again 4:20 and 5:12, why does the reset operation start with subtraction, and not check whether the counter is empty first?
The same question applies to most of the other algorithms presented, too.
agreed - in binary if !empty, you know it is a 1 ....
It's just a representation that you also see on state machines. You do not have a clear comparison step, you just follow the path that's possible. In this case you always check the "if" part, then do the "else", so decrement/increment.
All of the state machines he wrote down are while…do loops. The first step was always to check if it was empty.
The thought in my mind while watching this was that this works okay on an 8 bit tape, but the tape of a Turing machine is infinite in extent, so C1 and C3 would have to be able to hold an infinite number of counters in order to completely implement a Turing machine...
To have it filled with 1's all the way to the right will took infinite time.
The equivalent of the potentially infinite tape is indeed a potentially infinite set of counters / registers.
For a computation to succeed you must finish in finite many steps and this means you can only traverse a finite part of a tape and change or test only a finite many counters / registers.
If you're going to simulate an infinite thing, you're going to need another infinite thing, to be fair.
@@lovealien43 Actually, with this implementation of a general Turing machine, you only need 4 "bags", three of which require unlimited capacity.
Yes, the definition of the machine appears to be saying that the counter can count arbitrarily to any integer.
You can't escape infinity in any Turing Complete model of computation, it has to manifest one way or the other.
Its much easier to implement the rules of kalah with a counter machine than with a turing machine, it already gets a point for that.
I dont know if its just me but I hate the sound that the marker makes on paper.
(Love the videos otherwise)
Isn't the counter example just a really elaborate implementation example of the Turing machine itself? In that regards, does this prove anything other than that the Turing Machine is great?
Turing machines are just an elaborate form of Lambda Calculus.
These counter machines (I know them as register machines) implement machine functions from the natural numbers to the natural numbers, while Turing machines map words to words. Because you can map natural numbers to (finite length) words they can be compared and turn out to have the same computation power.
Well, no, but it is Turing Complete, which means it is precisely equivalent to a Turing Machine, but as Turing & Church proved that Lambda Calculus is equivalent to a Turing Machine. They’re all capable of computing the same things (i.e. anything computable), but that doesn’t make them the same thing.
Counter #4 was not used in mapping. Could opposite transformation work? 🤔
But what are it's real world applications
If i understood correctly, if number of counters is inf, it’s basically “2d” tape from Turing machine
Nah. They only need 3 counters for this to work (ignoring the temporary one used for some operations). They represent the entire length of the tape in one direction as a number of beads in one counter (the 1's and 0's on the tape are interpreted as a binary number with as many digits as the tape has squares in that direction) and the entire length of the tape in the other direction is similarly stored as a number of beads in another counter. The "middle" counter is only used to contain the value of the square in the middle of the tape. And then they halve or double the contents of the counters to mimic moving the tape left or right, plus some extra steps to maintain the middle counter.
On a Turing tape you can also interlace the bits of the numbers in the multiple bags. This is a bit like a 2D-array being stored in a linear address space by using a stride length. If you grow the number of bags you may need to re-layout your bags but that is doable. So there is no need for a fixed maximum number of bags.
its a sort of "Jugaad" for turing machine in our local language.
So, this is basically useless in any real application. Cool.
I think a calculator is faster
That's just a Turig machine with extra steps.
Core question is: Which one is more simple?
this is basically just assembly
Is there something similar to Turing completness in counter machines?
Yes, it's called turing completeness.
Almost the entire video you just watched was about counter and Turing machines being equally powerful.
@@antonf.9278 Thank you!!
Sounds a bit like a SUBLEQ machine.
Mirroring the bit pattern on the right will get nasty if the tape is infinite. (which means: there is no End-of-Tape)
How do you store the program though? Is there a some kind of list like a list of instructions and a program counter and stuff? How do you loop and jump and stuff?
I'd think a Counter Machine is just Turing Machine that allows more than 0 and 1.
Just what I am thinking all the time. Alternatively like using a tape that's not just infinite in length but also in width. TM is still more elegant, using just a single dimension.
I really don't feel the counting machine is as profound as is portrayed here.
Turing Machines are not exclusive to 1s and 0s. Turing Machines can have any arbitrary alphabet.
2:10, 1st thought is semaphores, very much looks like them to me
This reminds me of a great Zachtronics game: TIS-100
This seems to replicate a finite turning machine. I’m having a hard time imagining how this would look like for an infinite turning tape. It seems like the counter wouldn’t be able to replicate that.
How so? There is no imposed limit on the number of pebbles. There is an imposed limit of counters per program, but for each turing program there is an imposed limit of cards/instructions as well. Theoretically the counter system can scale infinitely
@@ionarevampvery simple, when you move forward, you halve C3. If you don't have a finite value for C3, you can't really halve it.
In order for the math to make any sense or even be possible, counter machines can only be used on finite "tapes".
@@l0zerth I'm still not sure I really understand... Can you give me an example program which is computable via turing machine but not counters?
Edit: Also, there is no case where any counter n (Cn) can have an infinite value. Literally impossible. A turing machine can't store or compute infinite values; we can only ever see a snapshot point of a potentially infinite algorithm or function.
@@ionarevamp in the proper Turing Machine, the tape is, in fact, infinite.
Also, the values in each counter are, by definition, functionally random. The only way to know how many counter tokens there are in each counter slot is to count them one by one, each slot as you go.
It's the world's most simple emulator.
This sounds like a instruction set inside a CPU
Churing machine, OK.
Always glad to see the fan-fold come out of the closed--then I know we'll be getting into something really interesting.
Very interesting. Is there a practical use or computational advantage of this concept? Conventional computers are essentially Turin machines, except each position on the tape is a 64-bit binary number (in the case of a modern PC), so there is almost a 1:1 mapping between the ticker-tape concept and a PC.
Please don't use the P word around theoretical computer scientists.
Turing machines work with words (finite length strings of symbols), counter / register machines work with natural numbers. Your PC memory has addresses (this is equivalent to the number of a counter / register) and contains a finite number (the content of a counter / register is potentially infinite) in each cell. You can work with strings on your PC because there is a map between natural numbers and symbols at work, e.g ASCII encoding.
As far as I can tell, it's time of the the most useless things in all of computing.
Mike Pound's Twin???
I didn't understand a single thing, but I also wasn't paying attention
But whyyyy
Why tho?
Thanks
Java developers when they realize what this guy is describing. . .
The first 10 minutes explain how to count, reset, add, subtract, and copy tiddlywinks. we know. you could teach this to 3rd graders. the schematics for simple math is not helping anybody.
luckily I don't have ADHD or I would fail his class
Is this crackpot stuff? Is this lad a theorist?
How can the Counter system be as powerful as a Turing system when this Counter system is not Turing complete?
This system requires more operations and explicit loops to do the same thing? Surely this system falls off massively in performance compared to a Turing system?
1 is only computable in the sense that it can be subtracted from and you have to temporarily transition the bit in order to do that? Does this serve any other purpose than, existing as a known way of testing algorithms that is separate from a Turing system?
Is the counter system useful?
Nobody uses a Turing machine as a model to build an actual computer. These are all theoretical models of computation. There is really no need for your hostility.
Saying that 2 systems are equivalent isn't usually about efficiency. It's just about the problems that they're theoretically able to solve. Mathematicians do it for all sorts of things. It's theory, so it might not have many direct applications.
One thing I can think of though is just possibly being an easier way to show a system is Turning Complete. Maybe it's easier to show that it's equivalent to this counter machine in some cases. And maybe that could be useful in showing that we can't be sure if it will ever finish.
Both models of computation are equivalent. The counter machines (register machines) are a nicer fit for recursion theory in my humble opinion.
@@unvergebeneid While they are theoretical constructs, they are not considered theoretical until proven correct, in the same way that scientific hypotheses are tested and validated through empirical experimentation.
I don't think it's hostile to ask if someone is a crackpot, people usually admit if they are.
If the counter machine is useful, it is useful only in explaining the commonalities and foundations of the theory itself.
@@unvergebeneid Do not feed... :D
When was it that society decided that nearly every sentence in English needed to start with a "So"? I wanted to watch this interesting topic, but was getting more and more irritated with the "So"s as time went on....
Have you counted them?
He ran out of glass beads
Society didn't, but scientific theory _which this is_ has long used this style as it's about leading on in a theory of connected ideas.
So, getting upset with that is like getting upset with too many = signs on a maths blackboard.
@@IngieKerr As someone who has to mark maths homework, it is possible to have too many equals signs (some students treat them as though they mean "so" rather than "is equal to")
@@rmsgrey Hehe. No, I get that.
I wasn't meaning to assert that "So" is identical to "=" in its function, just that it will likely be as common in scientific fields, and that unless it's _incorrectly_ used [as per your example perhaps] - then it's a perfectly correct linguistic token, as the video isn't an English Literature stylistic writing guide :)
Are there any advantages to counter machines vs turing machines?
No, as they are both computationally equivalent. Meaning that any counter machine has a corresponding Turing machine and vice versa.
No, like a Turing machine, these are abstract, theoretical computation machines.
@@squashedoranges7949 if there are no ad advantages for a counting machine, why would you ever use one? A turing machine seems simpler. Secondly, the video only discussed a counting machine which is equivalent to a single symbol turing machine (1 and empty). How would you make a counting machine that is equivalent to a turing machine that has a larger alphabet?
I suppose they
1- Validate the Church-Turing hypotheses, since they are yet another model of computation that appears superficially different yet turns out to be exactly the same as Turing Machines
2- Presumably make some proofs of Turing-Completness easier, if the thing you're proving is closer to them than Turing Machines
3- Presumably makes certain algorithms easier to express
2 and 3 are hypothetical because that's the first time I had heard of the machines, somebody posting examples would be interesting.
I guess, you could use them for some proof, where they would be simpler to use. Also it's good to just remember that there isn't anything special about Turing machines
Faux velvet jacket over a t-shirt?!?